排序算法总结

本文中默认对数组从小到大排序，数组大小为 $n$ 。

基于比较的排序算法

基于比较的排序算法最坏时间复杂度下界是 $O(nlgn)$ ，这是钛合金天花板，突破不了。

插入排序

算法思想：每次从未排序的序列中选择一个元素插入到已排序好的序列中。初始所有元素都处于未排序序列中，当未排序序列为空时，序列已排好。

时间复杂度：每个元素都会被选择一次，时间是 $O(n)$ ，为每个元素寻找一个合适位置可以用二分查找，时间复杂度为 $O(lgn)$ ，但是需要移动数组元素，时间复杂度为 $O(n)$ ，所以总体时间复杂度为 $O(n^2)$ 。如果是要对链表排序的话，不能使用二分查找寻找位置，时间复杂度为 $O(n)$ ，插入的时间为 $O(1)$ ，总体时间复杂度依然为 $O(n^2)$ 。数组完全正序时有最优时间复杂度 $O(n)$ （希尔排序利用这一点对插入排序进行改进），完全逆序时有最坏复杂度 $O(n^2)$

额外开销：需要 $O(1)$ 的存储空间存放当前要插入的元素，以方便元素移动。

稳定性分析：数组中排在前面的元素先被选择；每个元素被插入到第一个小于等于它的元素的后面（从后往前），故插入排序是稳定的。

代码如下：

void insertSort(vector<int> &array) {
    int len = array.size();
    for (int i = 1; i < len; i++) {
        int key = array[i], j = i - 1;
        while (j >= 0 && key < array[j]) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

归并排序

算法思想：分治。将数组分成等长的两部分，分别对两部分使用归并排序排序。然后将排序好的两部分合并。

时间复杂度：归并排序的递归式可以表示为 $T(n) = 2T(\frac{n}{2}) + O(n)$ ，这里的 $O(n)$ 为合并时间复杂度，运用主定理知复杂度为 $O(nlgn)$ 。由于归并排序每次都是均等划分，不会有像快排一样的退化问题。所以归并排序是一个渐进最优排序算法。

顺便说一下主定理，对于递归式 $T(n)=aT(\frac{n}{b})+f(n)$ ，其时间复杂度为：

若 $n^{lg_ba}>f(n)$ ，则复杂度为 $n^{lg_ba}$

若 $n^{lg_ba}=f(n)$ ，则复杂度为 $n^{log_ba}lgn$

若 $n^{lg_ba}<f(n)$ ，则复杂度为 $f(n)$

这里的大小是指阶数的大小

直观证明：

上述递归式的递归树深度为 $log_bn$ ，叶子节点的个数为 $a^{log_bn}$ 。

因为叶子节点的时间复杂度 $T(1) = O(1)$ ，故所有叶子节点复杂度之和为 $O(a^{log_bn})=O(n^{log_ba})$ (这个的证明方法是两边对 $b$ 取 $lg$ )。

每一层都有合并操作。第 $i$ 层的合并复杂度为 $a^if(\frac{n}{b^i})$ ，则所有合并操作的复杂度为 $O(f(n))$ 。

总体时间复杂度为这两部分的加和，哪部分的阶数高总体复杂度就由哪部分决定。至于第二种情况，记住就可以了（算法导论上有数学证明）。

在归并排序中， $n^{lg_ba}=n^{lg_22}=n$ ，与 $f(n)$ 相同，则复杂度为 $O(nlgn)$

额外开销：采用不用回写的方法实现，开销为 $O(n)$ ，每次从一个数组导到另一个数组。

稳定性分析：合并两个数组的时候，因前一个数组的元素均出现在后一个数组之前，两者头节点取小于等于的那个可保证相同元素保持原始顺序，故是稳定的。

递归代码（回写）如下：

void merge(vector<int> &array, int begin, int mid, int end) {
    vector<int> tmp;
    int i = begin, j = mid;
    while (i < mid && j < end) {
        if (array[i] <= array[j]) tmp.push_back(array[i++]);
        else tmp.push_back(array[j++]);
    }
    while (i < mid) tmp.push_back(array[i++]);
    while (j < end) tmp.push_back(array[j++]);
    for (int i = 0; i < tmp.size(); i++) {
        array[begin + i] = tmp[i];
    }
}
void mergeSortRecursive(vector<int> &array, int begin, int end) {
    if (begin == end - 1) return;
    int mid = (end - begin) / 2 + begin;
    mergeSortRecursive(array, begin, mid);
    mergeSortRecursive(array, mid, end);
    merge(array, begin, mid, end);
}

非递归代码（不回写）如下：

void mergeToArray(vector<int> &from, vector<int> &to, int begin, int mid, int end) {
    int i = begin, j = mid, k = begin;
    while (i < mid && j < end) {
        if (from[i] < from[j]) to[k++] = from[i++];
        else to[k++] = from[j++];
    }
    while (i < mid) to[k++] = from[i++];
    while (j < end) to[k++] = from[j++];
}

void mergeSortNonRecursive(vector<int> &array) {
    int step = 1, len = array.size();
    vector<int> tmp_array(len, 0);
    bool inArray = true;
    while (step < len) {
        // i <= len - step 保证 m 不会大于 len
        for (int i = 0; i <= len - step; i += step * 2) {
            int l = i, m = l + step, r = m + step;
            if (inArray) mergeToArray(array, tmp_array, l, m, min(r, len));
            else mergeToArray(tmp_array, array, l, m, min(r, len));
        }
        step <<= 1;
        inArray = !inArray;
    }
  	// important
    if (!inArray) array.swap(tmp_array);
}

快速排序

算法思想：也是分治的思想，和归并排序的不同在于他的划分方法。快排是每次选择一个元素，将小于这个它的元素放在它左边，大于它的放右边，然后再分别对两边使用快排。两边排好之后就整个数组就排好了。

时间复杂度：快排的递归式为 $T(n) = T(a)+T(n-a-1)+O(n)$ ，其中 $a$ 为左边数组的大小， $O(n)$ 为划分问题的代价。如果 $a=\frac{n}{2}$ ，则快排可取得和归并问题一样的复杂度 $O(nlgn)$ 。但是如果每次划分不均匀，快排会退化。特别是每次划分 $a=0$ 时，快排会取得最坏时间复杂度 $O(n^2)$ （如果原始数组有序，每次取最后一个元素作为枢轴，最坏情况就会出现）。但每次点都这么背概率也是极小的，而且只要划分不是偏差太离谱（或者说，两边的数组长度比例是常数），快排也是渐进 $O(nlgn)$ 的（证明见算法导论）。所以快排的平均时间复杂度为 $O(nlgn)$

改进：当然你不能保证你的点没有那么背（人品坏了什么都不好说），所以还是要有个保障手段。快排的一种改进就是每次随机选择枢轴。

额外开销：快排划分的时候，需要两个指针，如果是填坑法还需要一个变量保存key，所以空间复杂度为 $O(1)$

稳定性分析：当枢轴取相同元素中的一个元素时，就有可能出现不稳定。

代码如下：

inline int randIndex(const int &begin, const int &end) {
	return rand() % (end - begin + 1) + begin;
}
void quickSort(vector<int> &array, int begin, int end) {
	if (begin >= end) return;
	int index = partion2(array, begin, end);
	quickSort(array, begin, index - 1);
	quickSort(array, index + 1, end);
}

partition的实现有两种方法：

前后俩指针想中间移动，停在不符合元素的位置上，然后交换两个元素。重复上述动作直到相遇。

int partion2(vector<int> &array, int begin, int end) {
	int pivot = randIndex(begin, end);
	swap(array[pivot], array[end]);
	int l = begin, r = end, key = array[end];
    while (l < r) {
        while (l < r && array[l] <= key) l++;
        if (l < r) array[r--] = array[l];
        while (l < r && array[r] >= array[l]) r--;
        if (l < r) array[l++] = array[r];
    }
    array[l] = key;
    return l;
}

一快一慢俩指针，均向前移动，慢指针指向最后一个小于枢轴元素的位置，快指针寻找小于枢轴的元素，当找到后放到慢指针后面。下面代码中small是慢指针,i是快指针。

int partion(vector<int> &array, int begin, int end) {
	int small = begin - 1;
	int pivot = randIndex(begin, end);
	swap(array[pivot], array[end]);
	for (int i = begin; i <= end; i++) {
      	// 如果是小于号，for循环结束后还需要交换array[end]和array[++small]
		if (array[i] <= array[end]) {
			small++;
			if (i == small) continue;
			swap(array[i], array[small]);
		}
	}
	return small;
}

由于这种方法都是向一个方向前进，可以用这种方法实现单链表快排。

堆排序

算法思想：利用大顶堆的性质，每次从堆顶取出一个元素，同时堆的大小减一，当堆为空时数组排好序。

时间复杂度：

首先是建堆，有两种建堆方式：

筛选法建堆（向下调整）：从最后一个元素的父节点开始由下网上，由右往左调整，保持当前子树的大顶堆性质。使用这种方法，当前节点的左右两棵子树满足大顶堆的性质。比较当前元素与左右子树的根节点，如果不满足堆的性质，与最大的那个根交换。然后递归地调整那棵子树。如果当前子树的高度为 $h$ ，则调整的复杂度为 $lgh$ ，直观上这种方法建堆的复杂度为 $nlgn$ ，但由于低层节点的树高度小于 $lgn$ ，可以证明这种方法建堆的复杂度近似线性 $O(n)$ （证明见算法导论）。
插入法建堆（向上调整）：初始堆大小为0，每次向堆里插入一个元素，该元素想上冒泡直到到达根或父节点元素比它大。最坏情况下（完全有序，每次都需要将插入节点冒泡到根），这种建堆方法的复杂度为 $nlgn$ 。

看到这里你可能就觉得奇怪了，插入法建堆前面的元素冒泡的层数不也是小于 $n$ 吗，为什么复杂度不是 $O(n)$ 呢。数学公式的证明这里就不给出了，我来讲一下直观的理解。

考虑每个元素，最坏的情况下它会既向上移动又会向下移动。一开始插入进来的时候觉得自己是最大的，就冒泡到根节点，后来发现有比自己更大的，就被更大的挤下去了。如果序列一开始完全有序，考虑第 $x$ 号元素，刚插入进去时它会向上冒泡 $lgx$ 层，最后它前面应该有 $n-x$ 号元素，它又会向下移动 $lg(n-x)$ 层。总共移动层数为 $lgx+lg(n-x)$ ，这个是 $lg(n)$ 量级。所以插入法建堆的最坏复杂度是 $O(nlgn)$ 而不是 $O(n)$ 。

建完堆后才开始排序过程：每次将堆顶元素与最后一个元素交换，将堆的大小减1，调整堆。需这样做 $n-1$ 次，每次调整的时间为 $lgn$ ，时间复杂度为 $O(nlgn)$ 。

额外开销：堆排序所有只涉及交换，不需要额外存储空间

稳定性分析：因为每次都会和最后一个元素交换，可能会将最后一个元素提前。可以假设堆里元素全是一样的，这样最后一个元素会被提前。

代码如下（筛选法建堆）：

inline int parent(int i) {
	return (i - 1) >> 1;
}
inline int lChild(int i) {
	return (i << 1) + 1;
}
inline int rChild(int i) {
	return (i << 1) + 2;
}
/*
节点i的子树上最多有2n/3的节点（左子树，最后一层满，右子树最后一层没有节点）
则T(n) <= T(2n/3) + O(1), 运用主定理知复杂度为O(lgn)
*/
void maxHeapify(vector<int> &heap, int i, int heap_size) {
	int l = lChild(i), r = rChild(i), largest = i;
	if (l < heap_size && heap[l] > heap[i]) largest = l;
	if (r < heap_size && heap[r] > heap[largest]) largest = r;
	if (largest != i) {
		swap(heap[i], heap[largest]);
		maxHeapify(heap, largest, heap_size);
	}
}

/*
可以证明时间复杂度上界是O(n)
*/
void buildHeap(vector<int> &heap) {
	int heap_size = heap.size();
	int last_parent = parent(heap_size - 1);
	for (int i = last_parent; i >= 0; i--) {
		maxHeapify(heap, i, heap_size);
	}
}

void heapSort(vector<int> &heap) {
	buildHeap(heap);
	int heap_size = heap.size();
	while (heap_size > 1) {
		swap(heap[heap_size - 1], heap[0]);
		heap_size--;
		maxHeapify(heap, 0, heap_size);
	}
}

非基于比较的排序算法

下面这些算法的复杂度渐进线性，挣脱了 $nlg(n)$ 的束缚，但是它们都有各自的缺陷或因基于一些假设有各自的限制。

计数排序

算法思想：

元素 $x$ 的独白：我为什么要比呢，我只要知道有多少个元素排在我前面不就可以找到我的位置了吗？

假设待排序数组里每个数出现在一个小范围内，如 $[0,k)$ ，则我们可以开辟一个长度为 $k$ 的数组count，统计每个数出现的次数，count[i]表示数字i出现的次数。然后做一遍累加： $count[i]=\sum_{j=0}^icount[j]$ 。这样i就应该排在count[i]这个位置（如果只有一个i的话，多个稍作处理）。根据count数组，将原数组排到另一数组中即可排好序。

时间复杂度：统计次数 $O(n)$ ，累加 $O(k)$ ，排序 $O(n)$ 。总体时间复杂度为 $O(n+k)$

限制与缺陷：这种方法必须知道 $k$ ，且 $k$ 要较小，否则会占用大量空间。这种方法不能原地排序。

额外开销：count数组 $O(k)$ ，排好序的数组 $O(n)$ ，总体 $O(n+k)$

稳定性分析：最后排序的时候，从后往前扫，后面的元素先放下来，所以是稳定排序。

代码如下：

void countingSort(vector<int> &array, int k) {
    int len = array.size();
    vector<int> tmp_array(len, 0), count(k, 0);
    for (int i = 0; i < len; i++) {
        count[array[i]] += 1;
    }
    for (int i = 1; i < k; i++) {
        count[i] += count[i - 1];
    }
    // 注意, tmp_array数组是从0开始
    for (int i = len - 1; i >= 0; i--) {
        tmp_array[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }
    array.swap(tmp_array);
}

基数排序

算法思想：类似于字符串的字典序排序，将数字的每一位（可以是多位）看做一个键，从低位到高位（这与字典序不同）依次根据键排一遍后就排好了。对每个键排序可以用计数排序，毕竟知道范围了。

时间复杂度：假设数字有 $d$ 位， $r$ 位为一个键，则复杂度为 $O(\frac{d}{r}O(n+2^r))$ ，选择 $r=lgn$ 可取得线性时间复杂度。

限制与缺陷：使用了计数排序，不能原地排序；虽然渐进时间复杂度为 $O(n)$ ，但常数因子很大。不说你需要获取到每一位键所需要的时间，但就上面的复杂度公式而言，当 $r=lgn$ 时，时间复杂度为 $O(\frac{2d}{lgn}n)$ 。

额外开销：主要是计数排序消耗的空间， $O(n+2^r)$

稳定性分析：计数排序是稳定的，所以基数排序也是稳定的

桶排序

算法思想：和分治有些类似，将长度为 $n$ 的数组分配到 $n$ 个桶里，分别对 $n$ 个桶排序，再将所有桶连起来就排好序了。

时间复杂度：假设 $m$ 个桶，时间复杂度为 $O(n+nlg\frac{n}{m})$ ，当 $m$ 接近 $n$ 时，接近线性

限制与缺陷：要求数据均匀分布，如果数据都到一个桶里了就退化成普通排序了。算法导论上说这个限制可以放宽：只要每个桶的尺寸的平方和与元素总个数呈线性关系即可。虽然不懂它在说啥，大概应该是要求数据尽可能均匀分布。

额外开销：需要将数据都放到桶里，总的空间为 $O(n)$

稳定性分析：用链表的话，用尾插法，可以保证稳定

总结

	时间复杂度	额外开销	是否稳定	优点	缺点	改进
插入排序	$O(n^2)$	$O(1)$	是	数组有序时会很快	数组有序很难满足，平均复杂度也是 $O(n^2)$	希尔排序
归并排序	$O(nlgn)$	$O(n)$	是	最坏时间复杂度渐进最优	额外开销大
快速排序	$O(nlgn)$	$O(1)$	否	可以原地排序	划分不均匀会退化	随机选择枢轴
堆排序	$O(nlgn)$	无	否	最坏时间复杂度渐进最优	时间常数大（需要建堆，只能想到这点了）
计数排序	$O(n+k)$	$O(n+k)$	是	稳定，线性复杂度	额外开销大，不能原地排序，要求 $k$ 较小
基数排序	$O(\frac{d}{r}O(n+2^r))$	$O(n+2^r)$	是	稳定，线性复杂度	时间常数大，额外开销大，不能原地排序
桶排序	$O(n+nlg\frac{n}{m})$	$O(n)$	是	稳定，线性复杂度	要求数据尽可能均匀分布