排序算法总结

发表于   |   分类于   |     |   阅读次数

本文中默认对数组从小到大排序，数组大小为$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)$的存储空间存放当前要插入的元素，以方便元素移动。

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
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)$，其时间复杂度为：

  1. 若$n^{lg_ba}>f(n)$，则复杂度为$n^{lg_ba}$
  2. 若$n^{lg_ba}=f(n)$，则复杂度为$n^{log_ba}lgn$
  3. 若$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)$，每次从一个数组导到另一个数组。

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

递归代码（回写）如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)$

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

代码如下：

1
2
3
4
5
6
7
8
9
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的实现有两种方法：

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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;
    }

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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;
    }

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

堆排序

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

时间复杂度：

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

  1. 筛选法建堆（向下调整）：从最后一个元素的父节点开始由下网上，由右往左调整，保持当前子树的大顶堆性质。使用这种方法，当前节点的左右两棵子树满足大顶堆的性质。比较当前元素与左右子树的根节点，如果不满足堆的性质，与最大的那个根交换。然后递归地调整那棵子树。如果当前子树的高度为$h$，则调整的复杂度为$lgh$，直观上这种方法建堆的复杂度为$nlgn$，但由于低层节点的树高度小于$lgn$，可以证明这种方法建堆的复杂度近似线性$O(n)$（证明见算法导论）。
  2. 插入法建堆（向上调整）：初始堆大小为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)$。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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)$

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)$ 是 稳定，线性复杂度 要求数据尽可能均匀分布