内省排序

前置知识

插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理为将待排列元素划分为“已排序”和“未排序”两部分,每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。

插入排序在序列已部分有序的情况下效率很高。

插入排序的最优时间复杂度为 O(n)O(n) ,最差与平均时间复杂度为 O(n2)O(n^2)

快速排序

快速排序的工作原理是通过 分治 的方式来将一个数组排序。

快速排序分为三个过程:

将数列划分为两部分(要求保证相对大小关系);
递归到两个子序列中分别进行快速排序;
不用合并,因为此时数列已经完全有序。
和归并排序不同,第一步并不是直接分成前后两个序列,而是在分的过程中要保证相对大小关系。具体来说,第一步要是要把数列分成两个部分,然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度,一般是随机选择一个数 xx 来当做两个子数列的分界。

之后,维护一前一后两个指针 iijj ,依次考虑当前的数是否放在了应该放的位置(前还是后)。如果当前的数没放对,比如说如果后面的指针 jj 遇到了一个比 xx 小的数,那么可以交换 iijj 位置上的数,再把 jj 向后移一位。当前的数的位置全放对后,再移动指针继续处理,直到两个指针相遇。

其实,快速排序没有指定应如何具体实现第一步,不论是选择 xx 的过程还是划分的过程,都有不止一种实现方法。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数,所以直接拼接起来就好了。

普通快排的最优与平均时间复杂度为 O(nlogn)O(n\log n) 最差情况下为 O(n2)O(n^2)

堆排序

堆排序的工作原理为对所有待排序元素建堆,然后依次取出堆顶元素,就可以得到排好序的序列。

堆排序的时间复杂度为 O(nlogn)O(n\log n)

注:为了缩短代码长度,本文章内堆排序使用STL优先队列实现。

正文

这是朴素的双路快排:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quickSort(int l, int r) {
if(l >= r) return;
int i = l, j = r;
int pivot = arr[l];
while(i < j) {
while(i < j && arr[j] >= pivot) j--;
while(i < j && arr[i] <= pivot) i++;
if(i < j)
swap(arr[i], arr[j]);
}
swap(arr[l], arr[i]);
quickSort(l, i - 1);
quickSort(i + 1, r);
}

在一些极端情况下,普通的快速排序会退化为 O(n2)O(n^2) 的冒泡排序,这通常会导致用时大幅提升,为了避免这种情况,在实际实现时会做优化。

Step 1:基准点的选择

基准点的选择对快速排序的性能有极大的影响。在上文的代码中,始终选择区间的最左侧数据作为基准点。

基准点若选成区间的最大/最小值会导致退化(遍历区间时pivot始终大于或小于其他所有元素,这会导致第6和7行的循环把区间遍历两遍);最好的情况应选择区间内元素的中位数(每次恰好将区间内元素分割成大于、小于基准点的两部分,只需遍历一遍),但这通常无法实现,会导致时间常数大幅增高。

一种常见的方法是使用随机基准点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void quickSort(int l, int r) {
if(l >= r) return;
int i = l, j = r;
swap(arr[l], arr[rd() % (r - l + 1) + l]);//随机选择基准点
int pivot = arr[l];
while(i < j) {
while(i < j && arr[j] >= pivot) j--;
while(i < j && arr[i] <= pivot) i++;
if(i < j)
swap(arr[i], arr[j]);
}
swap(arr[l], arr[i]);
quickSort(l, i - 1);
quickSort(i + 1, r);
}

随机选择基准点情况下,几乎不可能每次都选中区间的极值。

另一种方法是从区间最左侧,区间中央,区间最右侧取中位数做基准点(三数取中法),这种方法只需少量比较即可获得(不那么准确的)中位数,在序列已有序时获得良好的效果,STL中采用此种方法。

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
int getPivot(int l, int r) {
int ix = l, iy = r - 1, iz = (l + r - 1) >> 1;
int x = arr[ix], y = arr[iy], z = arr[iz];
if(x > y) {
if(x > z) {
if(y > z) {
return iy;
} else {
return iz;
}
} else {
return ix;
}
} else {
if(x > z) {
return ix;
} else {
if(y > z) {
return iz;
} else {
return iy;
}
}
}
}
void quickSort(int l, int r) {
if(l >= r) return;
int i = l, j = r;
swap(arr[l], arr[getPivot(l,r)]);//三数取中法
int pivot = arr[l];
while(i < j) {
while(i < j && arr[j] >= pivot) j--;
while(i < j && arr[i] <= pivot) i++;
if(i < j)
swap(arr[i], arr[j]);
}
swap(arr[l], arr[i]);
quickSort(l, i - 1);
quickSort(i + 1, r);
}

Step 1.5:

经过优化的快排在遇到大量相同数据时还是会超时,所以可以使用三路快速排序,它将区间分割成大于基准点,等于基准点,小于基准点三部分。但是因为我不会写实现难度大,而且在后续优化后效果不明显,本文章不采用此方法。

Step 2:

当区间长度很小(如 rl16r-l \le 16 )时,再让快排去分割没有意义。如果使用插入排序进行小范围排序,反而能得到更好的效果。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int getPivot(int l, int r) {
int ix = l, iy = r - 1, iz = (l + r - 1) >> 1;
int x = arr[ix], y = arr[iy], z = arr[iz];
if(x > y) {
if(x > z) {
if(y > z) {
return iy;
} else {
return iz;
}
} else {
return ix;
}
} else {
if(x > z) {
return ix;
} else {
if(y > z) {
return iz;
} else {
return iy;
}
}
}
}
void insertSort(int l, int r) {
for(int i = l + 1; i <= r; i++) {
int j = i;
while(j > l) {
if(arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
j--;
} else {
break;
}
}
}
}
void quickSort(int l, int r, int deep) {
if(l >= r) return;
if(r - l <= 16) {
insertSort(l,r);
return;
}
int i = l, j = r;
swap(arr[l], arr[getPivot(l, r)]);
int pivot = arr[l];
while(i < j) {
while(i < j && arr[j] >= pivot) j--;
while(i < j && arr[i] <= pivot) i++;
if(i < j)
swap(arr[i], arr[j]);
}
swap(arr[l], arr[i]);
quickSort(l, i - 1, deep + 1);
quickSort(i + 1, r, deep + 1);
}

Step 3:

在递归深度大于 2logn2\log n 时,如果再使用快速排序分割会导致退化为冒泡排序。可以在递归深度大于 2logn2\log n 时切换为堆排序,这样就得到内省排序。

内省排序(英语:Introsort 或 Introspective sort)是快速排序和 堆排序 的结合,由 David Musser 于 1997 年发明。内省排序其实是对快速排序的一种优化,保证了最差时间复杂度为 nlognn \log n

内省排序将快速排序的最大递归深度限制为 2logn2\log n ,超过限制时就转换为堆排序。这样既保留了快速排序内存访问的局部性,又可以防止快速排序在某些情况下性能退化为 n2n^2

2000 年 6 月,SGI C++ STL 的 stl_algo.h 中 sort()函数的实现采用了内省排序算法。

完整代码(可通过P1177 【模板】快速排序):

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int n, maxdeep;
int arr[100010];
priority_queue<int, vector<int>, greater<int> > pq;
void insertSort(int l, int r) {
for(int i = l + 1; i <= r; i++) {
int j = i;
while(j > l) {
if(arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
j--;
} else {
break;
}
}
}
}
int getMaxDeep(int x) {
int k;
for(k = 0; x > 1; x >>= 1) k++;
return k * 2;
}
int getPivot(int l, int r) {
int ix = l, iy = r - 1, iz = (l + r - 1) >> 1;
int x = arr[ix], y = arr[iy], z = arr[iz];
if(x > y) {
if(x > z) {
if(y > z) {
return iy;
} else {
return iz;
}
} else {
return ix;
}
} else {
if(x > z) {
return ix;
} else {
if(y > z) {
return iz;
} else {
return iy;
}
}
}
}
void heapSort(int l, int r) {
for(int i = l; i <= r; i++) pq.push(arr[i]);
for(int i = l; i <= r; i++) {
arr[i] = pq.top();
pq.pop();
}
}
void introSortLoop(int l, int r, int deep) {
if(l >= r) return;
if(r - l <= 16) {
return;//经测试,在排序完成后直接执行一次插入排序更快
}
if(deep >= maxdeep) {
heapSort(l, r);
return;
}
int i = l, j = r;
swap(arr[l], arr[getPivot(l, r)]);
int pivot = arr[l];
while(i < j) {
while(i < j && arr[j] >= pivot) j--;
while(i < j && arr[i] <= pivot) i++;
if(i < j)
swap(arr[i], arr[j]);
}
swap(arr[l], arr[i]);
introSortLoop(l, i - 1, deep + 1);
introSortLoop(i + 1, r, deep + 1);
}
void introSort(int l, int r) {
introSortLoop(l, r - 1, 0);
insertSort(l, r - 1);//经测试,在排序完成后直接执行一次插入排序更快(STL实现)
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
maxdeep = getMaxDeep(n);
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
introSort(0, n);
for(int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
return 0;
}

Q/A:

Q:为什么不直接使用归并排序或堆排序等时间复杂度为 O(nlogn)O(n \log n) 的排序?

A:快速排序的分治算法在大多数情况下内存访问效率极高,虽然都是 O(nlogn)O(n\log n) 但是快排比其他的快。

Q:为什么还是没有STL快?

A:STL做了许多特殊优化,比如插入排序有“带边界保护”和“无边界保护”的两个版本。这导致比较次数更少,在数据范围大时造成显著影响。


内省排序
https://www.d0j1a1701.cc/p/2904365f/
作者
d0j1a_1701
发布于
2020年10月17日
许可协议
CC-BY-SA