排序算法总结

搜索文档…
排序算法总结
0x00 排序算法
在Wikipedia上一共列举了11种排序算法，分为4大类，如下
Simple sorts 简单排序
Insertion sort 插入排序
Selection sort 选择排序
Efficient sorts 高效排序
Merge sort 归并排序
Heapsort 堆排序
Quicksort 快速排序
Bubble sort and variants 冒泡排序及其变体
Bubble sort 冒泡排序
Shell sort 希尔排序
Comb sort 梳排序
Distribution sort 分配排序
Counting sort 计数排序
Bucket sort 桶排序
Radix sort 基数排序
0x01 术语
先来说说术语，有些术语确实理解起来比较晦涩
0x00 比较型排序算法和非比较型排序算法
比较型排序算法（Comparison sorts）
比较型排序算法就是我们一般常用的那几个排序算法，通过直接比较数列中两个数的大小来完成排序。
摘自维基百科：
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list.
非比较型排序算法（Non-comparison sorts）
不通过直接比较序列中两个数的大小来完成排序，所有能用非比较型排序算法的序列都能用比较型排序算法完成排序，但反过来不成立。
0x01 稳定性(Stability)
假定在待排序的序列中，有两个值是相等的，排序过后，如果这两个相等的值在排序后序列的相对次序保持不变，那么就是稳定的，否则就是不稳定的，如下图：
Could not load image
0x02 内部排序和外部排序
内部排序指的是排序在内存中进行，而许多实际应用中，经常需要对大文件进行排序，因为文件很大，无法装入内存，所以引入了外部排序，外部排序过程中需要多次进行内存和外存直接的交换，对外存文件中的记录进行排序后的结果仍然放在源文件中。
外部排序算法的时间代价主要考究访问磁盘的次数，即I/O次数，因为往往其I/O的时间要远超在内存中计算的时间。
0x02 排序算法比较
仅给出比较型排序算法(Comparison sorts)
算法
最佳
平均
最坏
空间
稳定性
插入排序
​nnn
 
​n2n^2n2
 
​n2n^2n2
 
1
稳定
选择排序
​n2n^2n2
 
​n2n^2n2
 
​n2n^2n2
 
1
不稳定
归并排序
 nlog⁡nn\log{n}nlogn
 
​nlog⁡nn\log{n}nlogn
 
​nlog⁡nn\log{n}nlogn
 
n
稳定
堆排序
​nnn
 
​nlog⁡nn\log{n}nlogn
 
​nlog⁡nn\log{n}nlogn
 
1
不稳定
快速排序
​nlog⁡nn\log{n}nlogn
 
​nlog⁡nn\log{n}nlogn
 
​n2n^2n2
 
​log⁡n\log{n}logn
 
都有
冒泡排序
​nnn
 
​n2n^2n2
 
​n2n^2n2
 
1
稳定
希尔排序
​nlog⁡nn\log{n}nlogn
 
-
​n43n^{\frac{4}{3}}n34​
 
1
不稳定
梳排序
​nlog⁡nn\log{n}nlogn
​
​n2n^2n2
 
​n2n^2n2
 
1
不稳定
无论输入序列如何，插入排序和选择排序的排序趟数始终为n-1，快速排序的排序趟数始终为n。只有冒泡排序可以在一趟排序后检查是否有元素交换，如果有则不再进行下一趟排序。
0x03 内部排序算法实现
0x00 插入排序（Insertion sort）
下面这个图来自维基百科，已经把插入排序算法的基本原理阐述地很清楚了：
顺便做一个LeetCode题，题目地址: 147. Insertion Sort List​
1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode * insertionSortList(ListNode *head) {
12
        if (head == NULL || head->next == NULL)
13
            return head;
14
        for (ListNode *p = head->next, *pLeft = head; p != NULL; pLeft = p, p = p->next)
15
        {
16
            if (p->val >= pLeft->val)
17
                continue;
18
            for (ListNode *q = head, *qLeft = NULL; q != p; qLeft = q, q = q->next)
19
            {
20
                if (p->val < q->val)
21
                {
22
                    pLeft->next = p->next;
23
                    if (qLeft != NULL)
24
                    {
25
                        ListNode* tmp = qLeft->next;
26
                        qLeft->next = p;
27
                        p->next = tmp;
28
                    }
29
                    else
30
                    {
31
                        p->next = head;
32
                        head = p;
33
                    }
34
                    break;
35
                }
36
            }
37
        }
38
        return head;
39
    }
40
};
Copied!
上面这个写法耗时52ms，当然不是最快的，最快的一个实现是这样的
1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode* insertionSortList(ListNode* head) {
12
        ListNode *h = new ListNode(0);
13
        ListNode *cur = head;
14
        ListNode *prev = h;
15
        ListNode *next = NULL;
16
        while (cur)
17
        {
18
            next = cur->next;
19
            if (!prev || !prev->next || prev->next->val >= cur->val)
20
                prev = h;
21
            while (prev->next && prev->next->val < cur->val)
22
                prev = prev->next;
23
            cur->next = prev->next;
24
            prev->next = cur;
25
            cur = next;
26
        }
27
        return h->next;
28
    }
29
};
Copied!
它这个算法将原来的链表拆分成2段，左边一段排序好了的，右边一段未排序的。
他这个算法精妙的地方在于他这个prev这个指针的使用
这个prev在左边经过排序的那一段链表内又将其分为两段，当从右边链表过来一个未排序的数的时候，通过与prev这个指针所指向的值进行大小比较，如果小，这个新值插入的位置就在右边开始(h指针)到prev指针所指向的位置，如果大，prev这个指针不动，从prev后面开始找插入点，实现了一个类似于二分查找的方法来进一步缩小了插入点的位置区间。
0x01 选择排序（Selection sort）
维基百科上同样有一个图把这个算法描绘的比较清晰：
再来一个LeetCode题目
1
class Solution {
2
public:
3
    void sortColors(vector<int>& nums) {
4
        for (int i = 0; i < nums.size(); ++i)
5
        {
6
            int iMin = nums[i], pos = i;
7
            for (int j = i + 1; j < nums.size(); ++j)
8
            {
9
                if (iMin >= nums[j])
10
                {
11
                    iMin = nums[j];
12
                    pos = j;
13
                }
14
            }
15
            swap(nums[i], nums[pos]);
16
        }
17
    }
18
};
Copied!
这个算法有着 O (n2)O\,(n^2)O(n2)
 的时间复杂度，不过提交上去之后，居然，居然，居然：
击败了100%的人，不过我个人认为这个题目用计数排序会好很多，在下面计数排序的部分，我也打算用这个题来作为示例。
0x02 归并排序（Merge sort）
维基百科上的图是真的有意思：
归并排序首先依赖的是归并算法，归并算法用于归并两个排序过的序列。
在此处提一个概念即为m路平衡归并，m路平衡归并就是将m个有序表组成一个新的有序表，经过一趟归并后，剩下的记录数是原来的 1m\frac{1}{m}m1​
 ，
归并算法可以用LeetCode上的题目来练习一下：
1
class Solution {
2
public:
3
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4
        std::vector<int> result;
5
        int i{}, j{};
6
        nums1.erase(nums1.begin() + m, nums1.end());
7
        while (i < m && j < n)
8
        {
9
            result.push_back(nums1[i] < nums2[j] ? nums1[i++] : nums2[j++]);
10
        }
11
        result.insert(result.end(), nums1.begin() + i, nums1.begin() + m);
12
        result.insert(result.end(), nums2.begin() + j, nums2.begin() + n);
13
        nums1 = result;
14
    }
15
};
Copied!
归并数组没什么意思，也比较简单，来一个归并链表的，上LeetCode题目，这个题目要求你归并N个有序链表，这些有序链表的头指针放在了一个vector中。我想到了两种解法：
解法1：
不断遍历这个vector中的头指针，然后找这些头指针所指向值的最小值，然后放入一个新的链表中作为返回结果，直到这个vector中的指针全部指向空，在此题中这种解法耗时198ms，代码如下：
1
class Solution {
2
    int getSmallestValue(std::vector<ListNode*>& lists)
3
    {
4
        int ret = lists[0]->val;
5
        int minRank = 0;
6
        for (int i = 0; i < lists.size(); ++i)
7
        {
8
            if (lists[i]->val < ret)
9
            {
10
                ret = lists[i]->val;
11
                minRank = i;
12
            }
13
        }
14
        lists[minRank] = lists[minRank]->next;
15
        if (lists[minRank] == NULL)
16
            lists.erase(lists.begin() + minRank);
17
        return ret;
18
    }
19
public:
20
    ListNode * mergeKLists(std::vector<ListNode*>& lists) {
21
        ListNode * result = new ListNode(0);
22
        ListNode * prev = result;
23
        ListNode * current = NULL;
24
        for (int i = 0; i < lists.size(); ++i)
25
        {
26
            if (lists[i] == NULL)
27
                lists.erase(lists.begin() + i--);
28
        }
29
        while (lists.size() > 0)
30
        {
31
            current = new ListNode(getSmallestValue(lists));
32
            prev->next = current;
33
            prev = current;
34
        }
35
        return result->next;
36
    }
37
};
Copied!
解法2：
解法2就是两两归并，把N个有序链表两两一伙进行归并得到一些中间链表，然后再对这些中间链表进行两两归并直至归并成一个大的链表。一开始的时候我写下了如下的代码，Accept了，但是370ms的运行时间却不怎么令人满意：
1
class Solution {
2
    ListNode * merge(ListNode *lhs, ListNode *rhs)
3
    {
4
        ListNode *head = new ListNode(0);
5
        ListNode *cur = head;
6
        while (lhs != nullptr || rhs != nullptr)
7
        {
8
            if (lhs != nullptr && rhs != nullptr)
9
            {
10
                ListNode ** smallest = lhs->val < rhs->val ? &lhs : &rhs;
11
                cur->next = *smallest;
12
                *smallest = (*smallest)->next;
13
                cur = cur->next;
14
            }
15
            else
16
            {
17
                cur->next = lhs != nullptr ? lhs : rhs;
18
                break;
19
            }
20
        }
21
        return head->next;
22
    }
23
public:
24
    ListNode * mergeKLists(std::vector<ListNode*>& lists)
25
    {
26
        if (lists.size() == 0)
27
            return NULL;
28
        if (lists.size() == 1)
29
            return lists[0];
30
        ListNode *result = lists[0];
31
        for (int i = 1; i < lists.size(); ++i)
32
            result = merge(result, lists[i]);
33
        return result;
34
    }
35
};
Copied!
看了某大牛的写法之后，我对上述代码进行了改良，仅改动了一下mergeKLists函数，就将运行时间减小到了24ms，超过100%的人，代码如下：
1
class Solution {
2
    ListNode * merge(ListNode *lhs, ListNode *rhs)
3
    {
4
        ListNode *head = new ListNode(0);
5
        ListNode *cur = head;
6
        while (lhs != nullptr || rhs != nullptr)
7
        {
8
            if (lhs != nullptr && rhs != nullptr)
9
            {
10
                ListNode ** smallest = lhs->val < rhs->val ? &lhs : &rhs;
11
                cur->next = *smallest;
12
                *smallest = (*smallest)->next;
13
                cur = cur->next;
14
            }
15
            else
16
            {
17
                cur->next = lhs != nullptr ? lhs : rhs;
18
                break;
19
            }
20
        }
21
        return head->next;
22
    }
23
public:
24
    ListNode * mergeKLists(std::vector<ListNode*>& lists)
25
    {
26
        int sz = lists.size();
27
        while (sz > 1) {
28
            int j = sz - 1;
29
            for (int i = 0; i < sz / 2; i++) {
30
                lists[i] = merge(lists[i], lists[j]);
31
                j--;
32
            }
33
            if (sz % 2 == 1)
34
                sz = sz / 2 + 1;
35
            else
36
                sz = sz / 2;
37
        }
38
        return sz > 0 ? lists[0] : NULL;
39
    }
40
};
Copied!
我总结了一下原因，在一开始的解法中，我不断让结果链表与vector中的下一个链表进行归并，随着归并过程的不断进行，这个结果链表会越来越大，归并的过程也会越来越耗时。而第二种解法，vector中的链表两两归并，一开始的几次归并都是小链表与小链表之间的归并，只有最后几次是大链表之间的归并，减少了大链表参与归并的次数和规模，从而极大程度上缩短了算法的时间。
归并排序就是在归并算法的基础上，不断地讲一个未排序的序列进行拆分，最后两两一伙，对其中的一伙进行排序后，再不断归并，直至整个数列完全有序，上LeetCode - Sort List 题目，此题要求在 O(n⋅log⁡(n))O(n\cdot\log(n))O(n⋅log(n))
 的时间内对单项链表进行排序，代码如下：
1
class Solution {
2
    ListNode * merge(ListNode *lhs, ListNode *rhs)
3
    {
4
        ListNode *head = new ListNode(0);
5
        ListNode *cur = head;
6
        while (lhs != nullptr || rhs != nullptr)
7
        {
8
            if (lhs != nullptr && rhs != nullptr)
9
            {
10
                ListNode ** smallest = lhs->val < rhs->val ? &lhs : &rhs;
11
                cur->next = *smallest;
12
                *smallest = (*smallest)->next;
13
                cur = cur->next;
14
            }
15
            else
16
            {
17
                cur->next = lhs != nullptr ? lhs : rhs;
18
                break;
19
            }
20
        }
21
        return head->next;
22
    }
23
public:
24
    ListNode * sortList(ListNode* head)
25
    {
26
        std::vector<ListNode*> sortedLists;
27
        ListNode *helper = head;
28
        for (ListNode *i = head; i != nullptr; )
29
        {
30
            if (i->next != nullptr && i->val > i->next->val)
31
            {
32
                sortedLists.push_back(helper);
33
                helper = i->next;
34
                i->next = nullptr;
35
                i = helper;
36
            }
37
            else
38
            {
39
                i = i->next;
40
            }
41
        }
42
        sortedLists.push_back(helper);
43
        int sz = sortedLists.size();
44
        while (sz > 1) {
45
            int j = sz - 1;
46
            for (int i = 0; i < sz / 2; i++) {
47
                sortedLists[i] = merge(sortedLists[i], sortedLists[j]);
48
                j--;
49
            }
50
            if (sz % 2 == 1)
51
                sz = sz / 2 + 1;
52
            else
53
                sz = sz / 2;
54
        }
55
        return sz > 0 ? sortedLists[0] : NULL;
56
    }
57
};
Copied!
以上代码运行时间48ms超过97.44%的人，还不错，我的一个基本想法就是，对于一个无序序列而言，其中难免会出现些许的有序部分，例如无序序列-1->5->3->4->0，我们可以找到-1->5、3->4、0三个有序序列，首先通过一趟for循环将其中的有序部分拆分开来，然后将这些有序序列的头指针地址放入一个vector中，然后再依据上题归并N个有序链表的代码进行归并。
参考了LeetCode大神的解法，最快的解法耗时43ms，代码如下，不过这种方法有种作弊的感觉就是它先将链表里面的数据放在一个vector中，然后用vector的sort函数进行排序，然后再将排过序的vector中的值重新写回单向链表。
1
// LeetCode 最快43ms解法
2
class Solution {
3
public:
4
   ListNode* sortList(ListNode* head)
5
    {
6
        vector<int> vec;
7
        ListNode *ln = head;
8
        for (; ln != NULL; ln = ln->next)
9
        {
10
            vec.push_back(ln->val);
11
        }
12
        sort(vec.begin(), vec.end());
13
        ln = head;
14
        for (auto i : vec)
15
        {
16
            ln->val = i;
17
            ln = ln->next;
18
        }
19
        return head;
20
    }
21
};
Copied!
第二快的方法耗时45ms，使用的是快速排序算法，这点等到下一节快速排序时再讲，第三快的方法使用归并排序耗时46ms：
1
class Solution {
2
    ListNode* merge(ListNode *l1, ListNode *l2) {
3
        ListNode dummy(INT_MIN);
4
        ListNode *node = &dummy;
5
        while(l1 && l2)
6
        {
7
            if(l1->val <= l2->val)
8
            {
9
                node->next = l1;
10
                l1 = l1->next;
11
            }
12
            else
13
            {
14
                node->next = l2;
15
                l2 = l2->next;
16
            }
17
            node = node->next;
18
        }
19
        node->next = l1 ? l1 : l2;
20
        return dummy.next;
21
    }
22
public:
23
    ListNode* sortList(ListNode* head) {
24
        if(head == NULL || head->next == NULL)
25
            return head;
26
        ListNode *slow = head;
27
        ListNode *fast = head->next;
28
        while(fast && fast->next)
29
        {
30
            slow = slow->next;
31
            fast = fast->next->next;
32
        }
33
        fast = slow->next;
34
        slow->next = NULL;
35
        return merge(sortList(head),sortList(fast));
36
    }
37
};
Copied!
他这个算法比较有意思，尤其是那个查找中点切分数列的算法上，我画了个图：
其中短箭头是slow那个指针，长箭头代表的是fast那个指针
当链表序列长度为 NNN
 时，这个方法可以用 N2\frac{N}{2}2N​
 的复杂度来找到二分时中点
归并排序后，我又发现了一个LeetCode题目适合用归并算法来解，就是Median of Two Sorted Arrays，这个题目要求你在 O(log⁡(m+n))O(\log{(m+n)})O(log(m+n))
 的复杂度内，在两个长度分别为m和n的经排序的数组内找出中位数。这个可以用归并的思路去解，代码如下：
1
class Solution {
2
public:
3
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
4
        const unsigned m{ nums1.size() }, n{ nums2.size() };
5
        unsigned size{ m + n };
6
        if (size == 0)
7
            return 0;
8
        const bool sizeIsEven{ (size & 1) == 0 };
9
        unsigned medianPosition{ sizeIsEven ? size >> 1 : (size >> 1) + 1 };
10
        unsigned i{}, j{};
11
        int dummy{};
12
        while (medianPosition && i < m && j < n)
13
        {
14
            dummy = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
15
            --medianPosition;
16
        }
17
        if (medianPosition == 0)
18
        {
19
            if (!sizeIsEven)
20
                return dummy;
21
            if (i < m && j < n)
22
                return (dummy + (nums1[i] < nums2[j] ? nums1[i] : nums2[j])) / 2.0;
23
            return (dummy + (i < m ? nums1[i] : nums2[j])) / 2.0;
24
        }
25
        std::vector<int>& tmp = i < m ? nums1 : nums2;
26
        const int p = i < m ? i : j;
27
        dummy = tmp[p + medianPosition - 1];
28
        return sizeIsEven ? (dummy + tmp[p + medianPosition]) / 2.0 : dummy;
29
    }
30
};
Copied!
这份代码耗时38ms击败98.80%的人，二路归并算法思路，对这两个数组进行模拟归并，直到其中位数所在的位置。
0x03 堆排序（Heap sort）
堆排序算法是一种对选择排序的改进算法，与选择排序相似的是，他同样将一个输入序列划分为一个有序段和一个无序段，并通过不断缩减无序段的长度来进行排序，与选择排序不同的是堆排序使用堆来查找最大值而不是像选择排序中那样通过线性时间的查找来完成（出自维基百科）。
YouTube上有一个Geeks for Geeks出品的视频有关堆排序的原理，只有2分钟很不错可以看一下：Heap Sort | GeeksforGeeks​
排序过程（动态流程可看上述视频）：
1.使用输入数据创建一个最大堆（Max Heap），最大堆的特点是父节点始终大于等于子节点
2.此时，最大堆的根节点成为整组数据的最大值，将其与堆的最后一个节点交换，并将最大堆的最后一个节点从堆中移除
3.直到堆中仅存一个元素，算法结束
还是那个LeetCode - Sort List题目，用堆排序来实现一下链表的排序：
1
class Solution {
2
    void swap(ListNode *lhs, ListNode *rhs)
3
    {
4
        lhs->val = lhs->val ^ rhs->val;
5
        rhs->val = lhs->val ^ rhs->val;
6
        lhs->val = lhs->val ^ rhs->val;
7
    }
8
​
9
    ListNode *tail = NULL;
10
    bool record_tail = false;
11
    int walked = 0;
12
    int total = 0;
13
​
14
    void heapify(ListNode* current, ListNode* parent)
15
    {
16
        // This algorithm has bugs.
17
        if (current == tail)
18
        {
19
            return;
20
        }
21
        if (current->next != NULL)
22
        {
23
            if (++walked == 3)
24
            {
25
                parent = parent->next;
26
                walked = 0;
27
            }
28
            heapify(current->next, parent);
29
        }
30
        if (record_tail)
31
        {
32
            total++;
33
        }
34
        if (record_tail && current->next == tail)
35
        {
36
            tail = current;
37
            record_tail = false;
38
        }
39
        if (current->val > parent->val)
40
        {
41
            swap(current, parent);
42
        }
43
    }
44
public:
45
    ListNode * sortList(ListNode *head) {
46
        if (head == NULL || head->next == NULL)
47
            return head;
48
        tail = NULL;
49
        total = 0;
50
        walked = 0;
51
        do
52
        {
53
            record_tail = true;
54
            heapify(head->next, head);
55
            swap(head, tail);
56
        } while (head->next != tail);
57
        return head;
58
    }
59
};
Copied!
一开始着实是试图用堆排序实现链表的排序，写了一段时间，上述代码依然是一份有bug的代码，写着写着，我觉得这样做并不合适，堆排序的时间复杂度在 O(N⋅log⁡(N))O(N\cdot \log(N))O(N⋅log(N))
 的原因很大一部分其实得益于数组的随机访问，对于一个单向链表而言，随机访问第K个元素其所花费的时间为 O(K)O(K)O(K)
 ，如果我们想在原链表的基础上建堆的话（也就是空间复杂度为 O(1)O(1)O(1)
 的情况下），你并没有数组随机访问某一号元素来得那么快，我认为，如果对于链表来说，使用堆排序的时间复杂度将为 O(N2⋅log⁡(N))O(N^2\cdot \log(N))O(N2⋅log(N))
 ，随着N的增长，其所花费的时间甚至比时间复杂度为 O(N2)O(N^2)O(N2)
 的选择排序还要高。所以使用堆排序排序单向链表是不合适的。
那排序单向链表怎么做快呢，答案就是上一小节所讲的归并排序，归并排序可以在排序单向链表时依然稳定 O(N⋅log⁡(N))O(N\cdot \log(N))O(N⋅log(N))
 的时间复杂度。读者可自行分析上一小节归并排序的倒数第二个代码片的时间复杂度。
下面给出用堆排序排序数组的代码，来做一个ACM题，出自山东理工大学ACM，简单题，给定一个数组，然后将其升序排序后输出即可，使用堆排序算法代码如下：
1
#include <iostream>
2
#include <vector>
3
​
4
void heapify(std::vector<int>& vec, int end)
5
{
6
    for (int i = end; i > 1;)
7
    {
8
        int *p = !(i & 1) && vec[i] < vec[i - 1] ? &vec[i - 1] : &vec[i];
9
        int parent = (i >> 1) - 1;
10
        if (*p > vec[parent])
11
        {
12
            std::swap(*p, vec[parent]);
13
        }
14
        i -= 2 - (i & 1);
15
    }
16
}
17
​
18
void sort(std::vector<int>& vec)
19
{
20
    int i = vec.size() - 1;
21
    // No need for sorting an array with only one element
22
    if (i)
23
    {
24
        while (i > 1)
25
        {
26
            heapify(vec, i);
27
            std::swap(vec[0], vec[i--]);
28
        }
29
        if (vec[0] > vec[1])
30
            std::swap(vec[0], vec[1]);
31
    }
32
}
33
​
34
int main()
35
{
36
    int n{};
37
    std::cin >> n;
38
    std::vector<int> input;
39
    while (n--)
40
    {
41
        int dummy{};
42
        std::cin >> dummy;
43
        input.push_back(dummy);
44
    }
45
    sort(input);
46
    for (int i = 0; i < input.size() - 1; ++i)
47
    {
48
        std::cout << input[i] << " ";
49
    }
50
    std::cout << input[input.size() - 1] << std::endl;
51
    system("pause");
52
    return 0;
53
}
Copied!
0x04 快速排序（Quick sort）
快速排序有时又被成为分区交换排序（partition-exchange sort），快速排序是对冒泡排序的一种改进，其最坏情况下时间复杂度为 O(N2)O(N^2)O(N2)
 ，平均时间复杂度为 O(N⋅log⁡(N))O(N\cdot \log(N))O(N⋅log(N))
 。
YouTube上有一个Geeks for Geeks出品的视频有关快速排序的原理，只有3分钟很不错可以看一下：Quick Sort | GeeksforGeeks​
快速排序算法首先选择一个pivot，然后将比pivot小的数全部移到pivot左边，比它大的数全部移动到器右边，然后对左半段和右半段递归调用快排算法。
有关pivot的选择，在早期的实现中，往往选择最左边的数为pivot，然而如果这样，对于一个已经排过序的数组来说，将会导致最坏的时间复杂度 O(N2)O(N^2)O(N2)
 ，后来人们通过选取随机位置或者最右边的数作为pivot以解决此问题。此处详见英文维基百科Choice of pivot。
还是那道ACM题目，出自山东理工大学ACM，简单题，给定一个数组，然后将其升序排序后输出即可，使用快速排序算法代码如下：
1
#include <iostream>
2
#include <vector>
3
​
4
void sort(std::vector<int>& vec, int begin, int end)
5
{
6
    if (begin + 1 >= end)
7
    {
8
        return;
9
    }
10
    int pivot{ end - 1 };
11
    int i{ begin - 1 };
12
    for (int j{ begin }; j < pivot; ++j)
13
    {
14
        if (vec[j] <= vec[pivot])
15
        {
16
            std::swap(vec[++i], vec[j]);
17
        }
18
    }
19
    std::swap(vec[i + 1], vec[pivot]);
20
    sort(vec, begin, i + 1);
21
    sort(vec, i + 2, end);
22
}
23
​
24
int main()
25
{
26
    int n{};
27
    std::cin >> n;
28
    std::vector<int> input;
29
    while (n--)
30
    {
31
        int dummy{};
32
        std::cin >> dummy;
33
        input.push_back(dummy);
34
    }
35
    sort(input, 0, input.size());
36
    for (int i = 0; i < input.size() - 1; ++i)
37
    {
38
        std::cout << input[i] << " ";
39
    }
40
    std::cout << input[input.size() - 1] << std::endl;
41
    return 0;
42
}
Copied!
0x05 冒泡排序（Bubble sort）
冒泡排序有时候也被称为sinking sort（下沉排序），是一个简单排序算法，在最好情况下拥有时间复杂度 O(N)O(N)O(N)
 ，最坏情况下 O(N2)O(N^2)O(N2)
 ，平均时间复杂度为 O(N2)O(N^2)O(N2)
。算法原理如下图：
上面这个图慢了，同样在Geeks for Geeks的YouTube Channel上找到了一个描述算法的小视频很不错，时长只有1分钟：Bubble Sort | GeeksforGeeks​
实现代码如下：
1
void sort(std::vector<int>& vec, int begin, int end)
2
{
3
    for (int i{ begin }; i < end; ++i)
4
    {
5
        for (int j{ begin }; j < end; ++j)
6
        {
7
            if (vec[i] < vec[j])
8
            {
9
                std::swap(vec[i], vec[j]);
10
            }
11
        }
12
    }
13
}
Copied!
0x06 希尔排序（Shell sort）
希尔排序可以看做是插入排序或者冒泡排序的改进算法，其实我看这个算法并不是很好，其在最坏情况下的时间复杂度可以高达 O(N2)O(N^2)O(N2)
（最坏gap序列）或者 O(N⋅log⁡2N)O(N\cdot \log^2{N})O(N⋅log2N)
 （最好gap序列），其最佳情况下的时间复杂度为 O(N⋅log⁡N)O(N\cdot \log{N})O(N⋅logN)
 ，由此可见这个算法相对于归并排序、堆排序以及快速排序还是慢一些的。而且这个货最后一趟的排序过程完全就是个插入排序。
San Diego State University有一个关于Shell sort的课程讲得很好，大约7分钟，地址：Sorts 5 Shell Sort。Geeks for Geeks也有一个相关的视频，但是其做得并不是很好，对于算法的理解不是很直观，所以此处就不放置那个视频的地址了。
代码如下：
1
void sort(std::vector<int>& vec, int begin, int end)
2
{
3
    for (int gap{ end - begin >> 1 }; gap > 0; gap >>= 1)
4
    {
5
        for (int i{ gap }; i < end; ++i)
6
        {
7
            int tmp{ vec[i] };
8
            int j{ i };
9
            for (; j >= gap && vec[j - gap] > tmp; j -= gap)
10
            {
11
                vec[j] = vec[j - gap];
12
            }
13
            vec[j] = tmp;
14
        }
15
    }
16
}
Copied!
0x07 梳排序（Comb sort）
梳排序是一种冒泡排序的改良算法，整体的算法原理和步骤我感觉跟希尔排序差不多，无非就是梳排序使用的gap与希尔排序不一样，梳排序使用的gap初始值为待排序的序列的大小，每次循环完成gap/1.3，其在最坏情况下的时间复杂度和在最好情况下的时间复杂度与希尔排序是一致的，但其平均时间复杂度为 O(N22p)O(\frac{N^2}{2^p})O(2pN2​)
 ，其中p的取值为待排序序列中递增元素的个数。
放一个Geeks for Geeks出品的梳排序的教程视频：Comb Sort | GeeksforGeeks​
同时，我们可以轻易地将上一节所述的希尔排序的算法改为梳排序，如下：
1
void sort(std::vector<int>& vec, int begin, int end)
2
{
3
    for (int gap{ int((end - begin) / 1.3) }; gap >= 1; gap /= 1.3)
4
    {
5
        for (int i{ gap }; i < end; ++i)
6
        {
7
            int tmp{ vec[i] };
8
            int j{ i };
9
            for (; j >= gap && vec[j - gap] > tmp; j -= gap)
10
            {
11
                vec[j] = vec[j - gap];
12
            }
13
            vec[j] = tmp;
14
        }
15
    }
16
}
Copied!
0x08 计数排序（Counting sort）
如果需要排序的东西是一个有限的小的可提前预知的集合的话，那就可以使用计数排序。例如，我现在有一个由枚举类型组成的序列，这个枚举类型是由10个整数值组成的，那我们就可以通过计数这10个值在待排序的序列中一共有多少个，然后将其按个数重新写回序列，即为实现计数排序。
例如，这个LeetCode题目就可以使用计数排序的方法实现，代码如下：
1
class Solution {
2
public:
3
    void sortColors(vector<int>& nums) {
4
        int helper[3]{};
5
        for (int i = 0; i < nums.size(); ++helper[nums[i]], ++i);
6
        for (int i = 0; i < nums.size(); ++i)
7
        {
8
            if (helper[0]-- > 0)
9
                nums[i] = 0;
10
            else if (helper[1]-- > 0)
11
                nums[i] = 1;
12
            else
13
                nums[i] = 2;
14
        }
15
    }
16
};
Copied!
上面的这个实现是我写的，使用了两个for循环，在题设中有这样一句话：
Could you come up with a one-pass algorithm using only constant space?
意思是你能用一趟for循环实现吗？想了想，实现代码如下：
1
class Solution {
2
public:
3
    