排序算法总结

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)

假定在待排序的序列中，有两个值是相等的，排序过后，如果这两个相等的值在排序后序列的相对次序保持不变，那么就是稳定的，否则就是不稳定的，如下图：

0x02 内部排序和外部排序

内部排序指的是排序在内存中进行，而许多实际应用中，经常需要对大文件进行排序，因为文件很大，无法装入内存，所以引入了外部排序，外部排序过程中需要多次进行内存和外存直接的交换，对外存文件中的记录进行排序后的结果仍然放在源文件中。

外部排序算法的时间代价主要考究访问磁盘的次数，即I/O次数，因为往往其I/O的时间要远超在内存中计算的时间。

0x02 排序算法比较

仅给出比较型排序算法(Comparison sorts)

算法	最佳	平均	最坏	空间	稳定性
插入排序	$n$	$n^2$	$n^2$	$1$	稳定
选择排序	$n^2$	$n^2$	$n^2$	1	不稳定
归并排序	$n\log{n}$	$n\log{n}$	$n\log{n}$	n	稳定
堆排序	$n$	$n\log{n}$	$n\log{n}$	1	不稳定
快速排序	$n\log{n}$	$n\log{n}$	$n^2$	$\log{n}$	都有
冒泡排序	$n$	$n^2$	$n^2$	1	稳定
希尔排序	$n\log{n}$	-	$n^{\frac{4}{3}}$	1	不稳定
梳排序	$n\log{n}$	$n^2$	$n^2$	1	不稳定

无论输入序列如何，插入排序和选择排序的排序趟数始终为n-1，快速排序的排序趟数始终为n。只有冒泡排序可以在一趟排序后检查是否有元素交换，如果有则不再进行下一趟排序。

0x03 内部排序算法实现

0x00 插入排序（Insertion sort）

下面这个图来自维基百科，已经把插入排序算法的基本原理阐述地很清楚了：

顺便做一个LeetCode题，题目地址: 147. Insertion Sort List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	ListNode * insertionSortList(ListNode *head) {
		if (head == NULL || head->next == NULL)
			return head;
		for (ListNode *p = head->next, *pLeft = head; p != NULL; pLeft = p, p = p->next)
		{
			if (p->val >= pLeft->val)
				continue;
			for (ListNode *q = head, *qLeft = NULL; q != p; qLeft = q, q = q->next)
			{
				if (p->val < q->val)
				{
					pLeft->next = p->next;
					if (qLeft != NULL)
					{
						ListNode* tmp = qLeft->next;
						qLeft->next = p;
						p->next = tmp;
					}
					else
					{
						p->next = head;
						head = p;
					}
					break;
				}
			}
		}
		return head;
	}
};

上面这个写法耗时52ms，当然不是最快的，最快的一个实现是这样的

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *h = new ListNode(0);
        ListNode *cur = head;
        ListNode *prev = h;
        ListNode *next = NULL;
        while (cur)
        {
            next = cur->next;
            if (!prev || !prev->next || prev->next->val >= cur->val)
                prev = h;
            while (prev->next && prev->next->val < cur->val)
                prev = prev->next;
            cur->next = prev->next;
            prev->next = cur;
            cur = next;
        }
        return h->next;
    }
};

它这个算法将原来的链表拆分成2段，左边一段排序好了的，右边一段未排序的。

他这个算法精妙的地方在于他这个prev这个指针的使用

这个prev在左边经过排序的那一段链表内又将其分为两段，当从右边链表过来一个未排序的数的时候，通过与prev这个指针所指向的值进行大小比较，如果小，这个新值插入的位置就在右边开始(h指针)到prev指针所指向的位置，如果大，prev这个指针不动，从prev后面开始找插入点，实现了一个类似于二分查找的方法来进一步缩小了插入点的位置区间。

0x01 选择排序（Selection sort）

维基百科上同样有一个图把这个算法描绘的比较清晰：

再来一个LeetCode题目

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i)
		{
			int iMin = nums[i], pos = i;
			for (int j = i + 1; j < nums.size(); ++j)
			{
				if (iMin >= nums[j])
				{
					iMin = nums[j];
					pos = j;
				}
			}
			swap(nums[i], nums[pos]);
		}
    }
};

这个算法有着$O\,(n^2)$的时间复杂度，不过提交上去之后，居然，居然，居然：

击败了100%的人，不过我个人认为这个题目用计数排序会好很多，在下面计数排序的部分，我也打算用这个题来作为示例。

0x02 归并排序（Merge sort）

维基百科上的图是真的有意思：

归并排序首先依赖的是归并算法，归并算法用于归并两个排序过的序列。

在此处提一个概念即为m路平衡归并，m路平衡归并就是将m个有序表组成一个新的有序表，经过一趟归并后，剩下的记录数是原来的$\frac{1}{m}$，

归并算法可以用LeetCode上的题目来练习一下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		std::vector<int> result;
		int i{}, j{};
		nums1.erase(nums1.begin() + m, nums1.end());
		while (i < m && j < n)
		{
			result.push_back(nums1[i] < nums2[j] ? nums1[i++] : nums2[j++]);
		}
		result.insert(result.end(), nums1.begin() + i, nums1.begin() + m);
		result.insert(result.end(), nums2.begin() + j, nums2.begin() + n);
		nums1 = result;
    }
};

归并数组没什么意思，也比较简单，来一个归并链表的，上LeetCode题目，这个题目要求你归并N个有序链表，这些有序链表的头指针放在了一个vector中。我想到了两种解法：

解法1：

不断遍历这个vector中的头指针，然后找这些头指针所指向值的最小值，然后放入一个新的链表中作为返回结果，直到这个vector中的指针全部指向空，在此题中这种解法耗时198ms，代码如下：

class Solution {
	int getSmallestValue(std::vector<ListNode*>& lists)
	{
		int ret = lists[0]->val;
		int minRank = 0;
		for (int i = 0; i < lists.size(); ++i)
		{
			if (lists[i]->val < ret)
			{
				ret = lists[i]->val;
				minRank = i;
			}
		}
		lists[minRank] = lists[minRank]->next;
		if (lists[minRank] == NULL)
			lists.erase(lists.begin() + minRank);
		return ret;
	}
public:
	ListNode * mergeKLists(std::vector<ListNode*>& lists) {
		ListNode * result = new ListNode(0);
		ListNode * prev = result;
		ListNode * current = NULL;
		for (int i = 0; i < lists.size(); ++i)
		{
			if (lists[i] == NULL)
				lists.erase(lists.begin() + i--);
		}
		while (lists.size() > 0)
		{
			current = new ListNode(getSmallestValue(lists));
			prev->next = current;
			prev = current;
		}
		return result->next;
	}
};

解法2：

解法2就是两两归并，把N个有序链表两两一伙进行归并得到一些中间链表，然后再对这些中间链表进行两两归并直至归并成一个大的链表。一开始的时候我写下了如下的代码，Accept了，但是370ms的运行时间却不怎么令人满意：

class Solution {
	ListNode * merge(ListNode *lhs, ListNode *rhs)
	{
		ListNode *head = new ListNode(0);
		ListNode *cur = head;
		while (lhs != nullptr || rhs != nullptr)
		{
			if (lhs != nullptr && rhs != nullptr)
			{
				ListNode ** smallest = lhs->val < rhs->val ? &lhs : &rhs;
				cur->next = *smallest;
				*smallest = (*smallest)->next;
				cur = cur->next;
			}
			else
			{
				cur->next = lhs != nullptr ? lhs : rhs;
				break;
			}
		}
		return head->next;
	}
public:
	ListNode * mergeKLists(std::vector<ListNode*>& lists)
	{
		if (lists.size() == 0)
			return NULL;
		if (lists.size() == 1)
			return lists[0];
		ListNode *result = lists[0];
		for (int i = 1; i < lists.size(); ++i)
			result = merge(result, lists[i]);
		return result;
	}
};

看了某大牛的写法之后，我对上述代码进行了改良，仅改动了一下mergeKLists函数，就将运行时间减小到了24ms，超过100%的人，代码如下：

class Solution {
	ListNode * merge(ListNode *lhs, ListNode *rhs)
	{
		ListNode *head = new ListNode(0);
		ListNode *cur = head;
		while (lhs != nullptr || rhs != nullptr)
		{
			if (lhs != nullptr && rhs != nullptr)
			{
				ListNode ** smallest = lhs->val < rhs->val ? &lhs : &rhs;
				cur->next = *smallest;
				*smallest = (*smallest)->next;
				cur = cur->next;
			}
			else
			{
				cur->next = lhs != nullptr ? lhs : rhs;
				break;
			}
		}
		return head->next;
	}
public:
	ListNode * mergeKLists(std::vector<ListNode*>& lists)
	{
		int sz = lists.size();
		while (sz > 1) {
			int j = sz - 1;
			for (int i = 0; i < sz / 2; i++) {
				lists[i] = merge(lists[i], lists[j]);
				j--;
			}
			if (sz % 2 == 1)
				sz = sz / 2 + 1;
			else
				sz = sz / 2;
		}
		return sz > 0 ? lists[0] : NULL;
	}
};

我总结了一下原因，在一开始的解法中，我不断让结果链表与vector中的下一个链表进行归并，随着归并过程的不断进行，这个结果链表会越来越大，归并的过程也会越来越耗时。而第二种解法，vector中的链表两两归并，一开始的几次归并都是小链表与小链表之间的归并，只有最后几次是大链表之间的归并，减少了大链表参与归并的次数和规模，从而极大程度上缩短了算法的时间。

归并排序就是在归并算法的基础上，不断地讲一个未排序的序列进行拆分，最后两两一伙，对其中的一伙进行排序后，再不断归并，直至整个数列完全有序，上LeetCode - Sort List 题目，此题要求在$O(n\cdot\log(n))$的时间内对单项链表进行排序，代码如下：

class Solution {
	ListNode * merge(ListNode *lhs, ListNode *rhs)
	{
		ListNode *head = new ListNode(0);
		ListNode *cur = head;
		while (lhs != nullptr || rhs != nullptr)
		{
			if (lhs != nullptr && rhs != nullptr)
			{
				ListNode ** smallest = lhs->val < rhs->val ? &lhs : &rhs;
				cur->next = *smallest;
				*smallest = (*smallest)->next;
				cur = cur->next;
			}
			else
			{
				cur->next = lhs != nullptr ? lhs : rhs;
				break;
			}
		}
		return head->next;
	}
public:
	ListNode * sortList(ListNode* head)
	{
		std::vector<ListNode*> sortedLists;
		ListNode *helper = head;
		for (ListNode *i = head; i != nullptr; )
		{
			if (i->next != nullptr && i->val > i->next->val)
			{
				sortedLists.push_back(helper);
				helper = i->next;
				i->next = nullptr;
				i = helper;
			}
			else
			{
				i = i->next;
			}
		}
		sortedLists.push_back(helper);
		int sz = sortedLists.size();
		while (sz > 1) {
			int j = sz - 1;
			for (int i = 0; i < sz / 2; i++) {
				sortedLists[i] = merge(sortedLists[i], sortedLists[j]);
				j--;
			}
			if (sz % 2 == 1)
				sz = sz / 2 + 1;
			else
				sz = sz / 2;
		}
		return sz > 0 ? sortedLists[0] : NULL;
	}
};

以上代码运行时间48ms超过97.44%的人，还不错，我的一个基本想法就是，对于一个无序序列而言，其中难免会出现些许的有序部分，例如无序序列-1->5->3->4->0，我们可以找到-1->5、3->4、0三个有序序列，首先通过一趟for循环将其中的有序部分拆分开来，然后将这些有序序列的头指针地址放入一个vector中，然后再依据上题归并N个有序链表的代码进行归并。

参考了LeetCode大神的解法，最快的解法耗时43ms，代码如下，不过这种方法有种作弊的感觉就是它先将链表里面的数据放在一个vector中，然后用vector的sort函数进行排序，然后再将排过序的vector中的值重新写回单向链表。

// LeetCode 最快43ms解法
class Solution {
public:
   ListNode* sortList(ListNode* head)
	{
		vector<int> vec;
		ListNode *ln = head;
		for (; ln != NULL; ln = ln->next)
		{
			vec.push_back(ln->val);
		}
		sort(vec.begin(), vec.end());
		ln = head;
		for (auto i : vec)
		{
			ln->val = i;
			ln = ln->next;
		}
		return head;
	}
};

第二快的方法耗时45ms，使用的是快速排序算法，这点等到下一节快速排序时再讲，第三快的方法使用归并排序耗时46ms：

class Solution {
    ListNode* merge(ListNode *l1, ListNode *l2) {
        ListNode dummy(INT_MIN);
        ListNode *node = &dummy;
        while(l1 && l2)
        {
            if(l1->val <= l2->val)
            {
                node->next = l1;
                l1 = l1->next;
            }
            else
            {
                node->next = l2;
                l2 = l2->next;
            }
            node = node->next;
        }
        node->next = l1 ? l1 : l2;
        return dummy.next;
    }
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *slow = head;
        ListNode *fast = head->next;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        return merge(sortList(head),sortList(fast));
    }
};

他这个算法比较有意思，尤其是那个查找中点切分数列的算法上，我画了个图：

其中短箭头是slow那个指针，长箭头代表的是fast那个指针

当链表序列长度为$N$时，这个方法可以用$\frac{N}{2}$的复杂度来找到二分时中点

归并排序后，我又发现了一个LeetCode题目适合用归并算法来解，就是Median of Two Sorted Arrays，这个题目要求你在$O(\log{(m+n)})$的复杂度内，在两个长度分别为m和n的经排序的数组内找出中位数。这个可以用归并的思路去解，代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		const unsigned m{ nums1.size() }, n{ nums2.size() };
		unsigned size{ m + n };
		if (size == 0)
			return 0;
		const bool sizeIsEven{ (size & 1) == 0 };
		unsigned medianPosition{ sizeIsEven ? size >> 1 : (size >> 1) + 1 };
		unsigned i{}, j{};
		int dummy{};
		while (medianPosition && i < m && j < n)
		{
			dummy = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
			--medianPosition;
		}
		if (medianPosition == 0)
		{
			if (!sizeIsEven)
				return dummy;
			if (i < m && j < n)
				return (dummy + (nums1[i] < nums2[j] ? nums1[i] : nums2[j])) / 2.0;
			return (dummy + (i < m ? nums1[i] : nums2[j])) / 2.0;
		}
		std::vector<int>& tmp = i < m ? nums1 : nums2;
		const int p = i < m ? i : j;
		dummy = tmp[p + medianPosition - 1];
		return sizeIsEven ? (dummy + tmp[p + medianPosition]) / 2.0 : dummy;
    }
};

这份代码耗时38ms击败98.80%的人，二路归并算法思路，对这两个数组进行模拟归并，直到其中位数所在的位置。

0x03 堆排序（Heap sort）

堆排序算法是一种对选择排序的改进算法，与选择排序相似的是，他同样将一个输入序列划分为一个有序段和一个无序段，并通过不断缩减无序段的长度来进行排序，与选择排序不同的是堆排序使用堆来查找最大值而不是像选择排序中那样通过线性时间的查找来完成（出自维基百科）。

YouTube上有一个Geeks for Geeks出品的视频有关堆排序的原理，只有2分钟很不错可以看一下：Heap Sort | GeeksforGeeks

排序过程（动态流程可看上述视频）：

1. 使用输入数据创建一个最大堆（Max Heap），最大堆的特点是父节点始终大于等于子节点
2. 此时，最大堆的根节点成为整组数据的最大值，将其与堆的最后一个节点交换，并将最大堆的最后一个节点从堆中移除
3. 直到堆中仅存一个元素，算法结束

还是那个LeetCode - Sort List题目，用堆排序来实现一下链表的排序：

class Solution {
    void swap(ListNode *lhs, ListNode *rhs)
    {
        lhs->val = lhs->val ^ rhs->val;
        rhs->val = lhs->val ^ rhs->val;
        lhs->val = lhs->val ^ rhs->val;
    }

    ListNode *tail = NULL;
    bool record_tail = false;
    int walked = 0;
    int total = 0;

    void heapify(ListNode* current, ListNode* parent)
    {
        // This algorithm has bugs.
        if (current == tail)
        {
            return;
        }
        if (current->next != NULL)
        {
            if (++walked == 3)
            {
                parent = parent->next;
                walked = 0;
            }
            heapify(current->next, parent);
        }
        if (record_tail)
        {
            total++;
        }
        if (record_tail && current->next == tail)
        {
            tail = current;
            record_tail = false;
        }
        if (current->val > parent->val)
        {
            swap(current, parent);
        }
    }
public:
    ListNode * sortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return head;
        tail = NULL;
        total = 0;
        walked = 0;
        do
        {
            record_tail = true;
            heapify(head->next, head);
            swap(head, tail);
        } while (head->next != tail);
        return head;
    }
};

一开始着实是试图用堆排序实现链表的排序，写了一段时间，上述代码依然是一份有bug的代码，写着写着，我觉得这样做并不合适，堆排序的时间复杂度在$O(N\cdot \log(N))$的原因很大一部分其实得益于数组的随机访问，对于一个单向链表而言，随机访问第K个元素其所花费的时间为$O(K)$，如果我们想在原链表的基础上建堆的话（也就是空间复杂度为$O(1)$的情况下），你并没有数组随机访问某一号元素来得那么快，我认为，如果对于链表来说，使用堆排序的时间复杂度将为$O(N^2\cdot \log(N))$，随着N的增长，其所花费的时间甚至比时间复杂度为$O(N^2)$的选择排序还要高。所以使用堆排序排序单向链表是不合适的。

那排序单向链表怎么做快呢，答案就是上一小节所讲的归并排序，归并排序可以在排序单向链表时依然稳定$O(N\cdot \log(N))$的时间复杂度。读者可自行分析上一小节归并排序的倒数第二个代码片的时间复杂度。

下面给出用堆排序排序数组的代码，来做一个ACM题，出自山东理工大学ACM，简单题，给定一个数组，然后将其升序排序后输出即可，使用堆排序算法代码如下：

#include <iostream>
#include <vector>

void heapify(std::vector<int>& vec, int end)
{
    for (int i = end; i > 1;)
    {
        int *p = !(i & 1) && vec[i] < vec[i - 1] ? &vec[i - 1] : &vec[i];
        int parent = (i >> 1) - 1;
        if (*p > vec[parent])
        {
            std::swap(*p, vec[parent]);
        }
        i -= 2 - (i & 1);
    }
}

void sort(std::vector<int>& vec)
{
    int i = vec.size() - 1;
    // No need for sorting an array with only one element
    if (i)
    {
        while (i > 1)
        {
            heapify(vec, i);
            std::swap(vec[0], vec[i--]);
        }
        if (vec[0] > vec[1])
            std::swap(vec[0], vec[1]);
    }
}

int main()
{
    int n{};
    std::cin >> n;
    std::vector<int> input;
    while (n--)
    {
        int dummy{};
        std::cin >> dummy;
        input.push_back(dummy);
    }
    sort(input);
    for (int i = 0; i < input.size() - 1; ++i)
    {
        std::cout << input[i] << " ";
    }
    std::cout << input[input.size() - 1] << std::endl;
    system("pause");
    return 0;
}

0x04 快速排序（Quick sort）

快速排序有时又被成为分区交换排序（partition-exchange sort），快速排序是对冒泡排序的一种改进，其最坏情况下时间复杂度为$O(N^2)$，平均时间复杂度为$O(N\cdot \log(N))$。

YouTube上有一个Geeks for Geeks出品的视频有关快速排序的原理，只有3分钟很不错可以看一下：Quick Sort | GeeksforGeeks

快速排序算法首先选择一个pivot，然后将比pivot小的数全部移到pivot左边，比它大的数全部移动到器右边，然后对左半段和右半段递归调用快排算法。

有关pivot的选择，在早期的实现中，往往选择最左边的数为pivot，然而如果这样，对于一个已经排过序的数组来说，将会导致最坏的时间复杂度$O(N^2)$，后来人们通过选取随机位置或者最右边的数作为pivot以解决此问题。此处详见英文维基百科Choice of pivot。

还是那道ACM题目，出自山东理工大学ACM，简单题，给定一个数组，然后将其升序排序后输出即可，使用快速排序算法代码如下：

#include <iostream>
#include <vector>

void sort(std::vector<int>& vec, int begin, int end)
{
    if (begin + 1 >= end)
    {
        return;
    }
    int pivot{ end - 1 };
    int i{ begin - 1 };
    for (int j{ begin }; j < pivot; ++j)
    {
        if (vec[j] <= vec[pivot])
        {
            std::swap(vec[++i], vec[j]);
        }
    }
    std::swap(vec[i + 1], vec[pivot]);
    sort(vec, begin, i + 1);
    sort(vec, i + 2, end);
}

int main()
{
    int n{};
    std::cin >> n;
    std::vector<int> input;
    while (n--)
    {
        int dummy{};
        std::cin >> dummy;
        input.push_back(dummy);
    }
    sort(input, 0, input.size());
    for (int i = 0; i < input.size() - 1; ++i)
    {
        std::cout << input[i] << " ";
    }
    std::cout << input[input.size() - 1] << std::endl;
    return 0;
}

0x05 冒泡排序（Bubble sort）

冒泡排序有时候也被称为sinking sort（下沉排序），是一个简单排序算法，在最好情况下拥有时间复杂度$O(N)$，最坏情况下$O(N^2)$，平均时间复杂度为$O(N^2)$。算法原理如下图：

上面这个图慢了，同样在Geeks for Geeks的YouTube Channel上找到了一个描述算法的小视频很不错，时长只有1分钟：Bubble Sort | GeeksforGeeks

实现代码如下：

void sort(std::vector<int>& vec, int begin, int end)
{
    for (int i{ begin }; i < end; ++i)
    {
        for (int j{ begin }; j < end; ++j)
        {
            if (vec[i] < vec[j])
            {
                std::swap(vec[i], vec[j]);
            }
        }
    }
}

0x06 希尔排序（Shell sort）

希尔排序可以看做是插入排序或者冒泡排序的改进算法，其实我看这个算法并不是很好，其在最坏情况下的时间复杂度可以高达$O(N^2)$（最坏gap序列）或者$O(N\cdot \log^2{N})$（最好gap序列），其最佳情况下的时间复杂度为$O(N\cdot \log{N})$，由此可见这个算法相对于归并排序、堆排序以及快速排序还是慢一些的。而且这个货最后一趟的排序过程完全就是个插入排序。

San Diego State University有一个关于Shell sort的课程讲得很好，大约7分钟，地址：Sorts 5 Shell Sort。Geeks for Geeks也有一个相关的视频，但是其做得并不是很好，对于算法的理解不是很直观，所以此处就不放置那个视频的地址了。

代码如下：

void sort(std::vector<int>& vec, int begin, int end)
{
    for (int gap{ end - begin >> 1 }; gap > 0; gap >>= 1)
    {
        for (int i{ gap }; i < end; ++i)
        {
            int tmp{ vec[i] };
            int j{ i };
            for (; j >= gap && vec[j - gap] > tmp; j -= gap)
            {
                vec[j] = vec[j - gap];
            }
            vec[j] = tmp;
        }
    }
}

0x07 梳排序（Comb sort）

梳排序是一种冒泡排序的改良算法，整体的算法原理和步骤我感觉跟希尔排序差不多，无非就是梳排序使用的gap与希尔排序不一样，梳排序使用的gap初始值为待排序的序列的大小，每次循环完成gap/1.3，其在最坏情况下的时间复杂度和在最好情况下的时间复杂度与希尔排序是一致的，但其平均时间复杂度为$O(\frac{N^2}{2^p})$，其中p的取值为待排序序列中递增元素的个数。

放一个Geeks for Geeks出品的梳排序的教程视频：Comb Sort | GeeksforGeeks

同时，我们可以轻易地将上一节所述的希尔排序的算法改为梳排序，如下：

void sort(std::vector<int>& vec, int begin, int end)
{
    for (int gap{ int((end - begin) / 1.3) }; gap >= 1; gap /= 1.3)
    {
        for (int i{ gap }; i < end; ++i)
        {
            int tmp{ vec[i] };
            int j{ i };
            for (; j >= gap && vec[j - gap] > tmp; j -= gap)
            {
                vec[j] = vec[j - gap];
            }
            vec[j] = tmp;
        }
    }
}

0x08 计数排序（Counting sort）

如果需要排序的东西是一个有限的小的可提前预知的集合的话，那就可以使用计数排序。例如，我现在有一个由枚举类型组成的序列，这个枚举类型是由10个整数值组成的，那我们就可以通过计数这10个值在待排序的序列中一共有多少个，然后将其按个数重新写回序列，即为实现计数排序。

例如，这个LeetCode题目就可以使用计数排序的方法实现，代码如下：

class Solution {
public:
	void sortColors(vector<int>& nums) {
		int helper[3]{};
		for (int i = 0; i < nums.size(); ++helper[nums[i]], ++i);
		for (int i = 0; i < nums.size(); ++i)
		{
			if (helper[0]-- > 0)
				nums[i] = 0;
			else if (helper[1]-- > 0)
				nums[i] = 1;
			else
				nums[i] = 2;
		}
	}
};

上面的这个实现是我写的，使用了两个for循环，在题设中有这样一句话：

Could you come up with a one-pass algorithm using only constant space?

意思是你能用一趟for循环实现吗？想了想，实现代码如下：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int zero_index = 0;
	    int two_index = nums.size() - 1;
		for (int i = 0; i <= two_index; i++) {
			if (nums[i] == 0)
				swap(nums[i], nums[zero_index++]);
			else if (nums[i] == 2)
				swap(nums[i--], nums[two_index--]);
        }
    }
};

这段代码需要注意的一个地方就是当当前的数字为2的时候，与后面的数字交换后需要将i-1使其重新判断当前i值所在的元素，反例如下，当输入数据为[1,2,0]时，且循环走到i=1，第一遍交换后得[1,0,2]，如果不将i=1重新置换一次，这个循环就走到头了，然后就出错啦！！！在这个地方花了一点时间，有点日狗。

同样，LeetCode题目Custom Sort String也可以通过计数排序的方法快速解决，代码如下：

class Solution {
public:
    std::string customSortString(std::string S, std::string T) {
        int ss[26]{};
        std::string ret = "";
        for (char t : T)
        {
            ++ss[t - 'a'];
        }
        for (char s : S)
        {
            while (ss[s - 'a']-- > 0)
            {
                ret.push_back(s);
            }
        }
        for (int i = 0; i < 26; ++i)
        {
            while (ss[i]-- > 0)
            {
                ret.push_back(i + 'a');
            }
        }
        return ret;
    }
};

0x09 桶排序（Bucket sort）

桶排序通过将待排序的元素按照一定的规则，放在一个个的桶里面，然后将这些桶中的元素使用其他的排序算法（比如快速排序）或者递归使用桶排序进行排序，最后，将这些桶中元素按照大小排列依次取出即可得到有序的序列。

YouTube上有一个视频，形象而又生动地说明了桶排序的流程，很不错，地址如下：Bucket Sort | GeeksforGeeks

0x04 外部排序算法

0x00 归并排序

首先将外存上的n个记录的文件分成若干长度为h的子文件，先依次读入内存并利用有效的内部排序方法对其进行排序，然后将排序后得到的有序子文件重新写回外存，这些有序子文件称之为归并段，归并趟数$S=\lceil \log_mr\rceil$，其中m为归并路数，r为初始归并段的个数，同时归并趟数也即为归并树的高度。

m-路归并可以用一棵m叉树来表示，因为每做一次m路归并都要有m个归并段参加，因此归并树是一棵只有度为0和度为m的结点的严格m叉树。归并时可以将Huffman树的思想推广到m叉树上，在归并树中，让记录少的初始归并段最先归并，记录数多的初始归并段最晚归并，此时就可以建立I/O次数最少的最佳归并树，如果初始段不足以构成一棵严格m叉树，则需要添加长度为0的虚段，规则如下，设度为0的结点的个数为$n_0$（也即为初始归并段的个数），度为m的个数为$n_m$，则对于严格二叉树来说，有$n_0=(m-1)n_m+1$：

• 如果$(n_0-1)\%(m-1)==0$的话，则这$n_0$个叶节点正好可以构造m叉归并树，此时，内结点有$n_m$个
• 如果$(n_0-1)\%(m-1)=u\ne0$的话，说明有u个顶点多余，不能包含在m叉归并树中，此时应在原有$n_m$个内结点的基础上再增加一个内结点，在归并树中替代一个叶节点的位置，被代替的叶节点加上刚才多出的u个叶节点，再加上m-u-1个空归并段，就建成归并树。