排序算法
快速排序
快速排序算法也是一种分治递归算法，它在 𝑵 值的输入数组上的最坏情况运行时间为 𝜽(𝑵^𝟐)
它的平均运行时间为𝜽(𝑵𝐥𝐠𝑵)，但它的平均效率非常高，因为𝜃 𝑁lg𝑁 符号中的常数因子非常小（高度优化的内循环）
而且它的最坏情况在简单的优化后可以很可能的避免
它具有就地排序的优点，即在不使用辅助数据结构的情况下转换输入（比如归并排序就需要一个辅助数组，否则操作会负责/开销会增大）
在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
该算法的关键是分区过程，它将子数组重新排列到位
The key to the algorithm is the partition procedure, which rearranges
subarrays in place
如果您不想被伪代码折磨的话，请跳至：“简易实现”
理论实现
分：
1.选择一个数组中的元素，所选元素被称为轴/基准pivot
2.根据所选的轴将数组分为两个子数组，称为data1[l->p-1],data2[p+1->r],其中在data1中的元素一定小于等于轴，而在data2中的元素一定大于等于轴
治：
递归调用方法来排序子数组
组合：
在快排中，不需要合并过程，因为两个子数组已经排序，并且分区方案(即左边都是小的，右边都是大的)确保两个子数组是有序的。
注：现在您已经知道基础的知识了，可以选择直接从“快速排序——基于书本的再推进与优化”开始阅读，不过下面的内容不会占用您多少时间。
分割区域
该算法的关键是分区过程，它将子数组重新排列到位,我们可以利用下面的方法来进行分区：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public void partition(data,l,r){
pivot = data[r] ;
i = l - 1 ;
for j=l to r-1 {
if(data[j] <= pivot){
i++ ;
swap(data[i] , data[j]);
}
swap(data[i+1],data[r]) ;
}
}
|
分区策略
分区的策略总体而言还是十分明显的：
1.选择轴，一种想法是随机选择三个元素，然后以三个的中位数作为轴；或者取left、right和center的值，然后用三者的中位数作为pivot。不管怎么样，得到一个中位数
轴的选择对于算法实质执行的时候的速度是十分重要的
2.按照下方的策略进行分区(伪代码)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| HOARE-PARTITION(data, 𝑙, 𝑟)
pivot = data[𝑙 ]
𝑖 = 𝑙 – 1
𝑗 = 𝑟 + 1
while TRUE
repeat
𝑗 = 𝑗 − 1
until data[ 𝑗 ] > pivot
repeat
𝑖 = 𝑖 + 1
until data[ 𝑖 ] < pivot
if 𝑖 < 𝑗
SWAP(data[ 𝑖 ], data[ 𝑗 ])
else
return
|
简易实现
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
| private void quickSort(int[] src, int begin, int end) {
if (begin < end) {
int key = src[begin];
int i = begin;
int j = end;
while (i < j) {
while (i < j && src[j] > key) {
j--;
}
if (i < j) {
src[i] = src[j];
i++;
}
while (i < j && src[i] < key) {
i++;
}
if (i < j) {
src[j] = src[i];
j--;
}
}
src[i] = key;
quickSort(src, begin, i - 1);
quickSort(src, i + 1, end);
}
|
快速排序——基于书本的再推进与优化
简单的快速排序实现
它实在太简单了：pivot直接选择终点，在分割和比较上不作优化，依旧采用了临时数组等等。这些问题在后文会被逐步优化掉
不过，基于这个代码，可以迅速明白快速排序需要干什么
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
|
public static void quickSort(List<Integer> items){
if(items.size() > 1){
List<Integer> smaller = new ArrayList<>();
List<Integer> larger = new ArrayList<>();
List<Integer> same = new ArrayList<>();
Integer chosenItem = items.get(items.size() / 2) ;
for(Integer i : items){
if(i < chosenItem){
smaller.add(i);
}else if(i > chosenItem){
larger.add(i) ;
}else{
same.add(i) ;
}
}
quickSort(smaller);
quickSort(larger) ;
items.clear() ;
items.addAll(smaller) ;
items.addAll(same) ;
items.addAll(larger) ;
}
}
|
经典的快速排序步骤
分为四步，其中二三两步我们会在后面优化。经典的快速排序不会产生额外的数组，直接在原有数组的基础上进行修改
1.如果数组S的元素个数是0或1，直接返回
2.取S中任意元素，作为枢纽元pivot
3.将S分为两个不相交的集合S1,S2.有一个共同不属于二者的部分v(可能是相等的一组等等)
4.返回“S1+v+S2”
书本原文如下：
优化：选取合适的pivot
不想看理论的可以跳到“代码实现”
理论
1.首先之首先，使用“第一个/最后一个”等作为pivot是十分危险的，因为你面对的数组是未知的
2.安全的做法：获得一个随机数，这种策略十分安全，但是获得随机数的开销略大
3.三数中值分割法：使用左端、右端、中心位置对应的三个数的中值作为pivot。这种做法能以小的开销，减少程序的调用次数。而由此过程中得到的分割策略是十分优秀的，并且在分割过程中的优化可以为后面程序的运行铺垫（这部分解释起来篇幅有点大，见P220-P202）
书中的原文：
![M0LKJZA2U]6[(IF`UQP@TWY.png](https://s2.loli.net/2022/04/19/XVz39NL5WkbMmGC.png)
代码实现
三值分割法是开销小且好用的一种方法：
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
|
private static Anytype median3(Anytype[] a , int left , int right){
int center = (left+right)/2 ;
if(a[center].compareTo(a[left]) < 0 ){
SwapReferences(a,left,center);
}
if(a[right].compareTo(a[left]) < 0){
SwapReferences(a,left,right) ;
}
if(a[right].compareTo(a[center]) < 0 ){
SwapReferences(a,center,right);
}
SwapReferences(a,center,right - 1);
return a[right - 1] ;
}
public void SwapReferences(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
|
优化：小数组处理
理论
个人认为，只是应试的话（比如强制使用快排），可以不看这部分的优化
起因对于“小数组”，快排不如插入排序，通常的解决办法是在数组较小时不递归调用快排，转而使用插入排序
那么，多“小”是小呢，一般认为，一种好的截止范围Cutoff Range是10，即CUTOFF=10。事实上5到20都可以，但是为了避免各种极端情况的发生时的“有害退化出现”，我们选择10
书中原文的阐述如下：
代码实现
其实就是一个if-else的事情，这部分直接写到最终的实现代码里面去了
最终代码
由上分析综合得出以下代码（含注释）：
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
|
private static void quickSort(Anytype[] a){
quickSort(a,0,a.length-1);
}
private static Anytype median3(Anytype[] a , int left , int right){
int center = (left+right)/2 ;
if(a[center].compareTo(a[left]) < 0 ){
SwapReferences(a,left,center);
}
if(a[right].compareTo(a[left]) < 0){
SwapReferences(a,left,right) ;
}
if(a[right].compareTo(a[center]) < 0 ){
SwapReferences(a,center,right);
}
SwapReferences(a,center,right - 1);
return a[right - 1] ;
}
public void SwapReferences(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void quickSort(Anytype[] a , int left , int right){
if(left + CUTOFF <= right){
Anytype pivot = median3(a,left,right) ;
int i = left ;
int j = right - 1;
for(;;){
while(a[++i].compareTo(pivot)<0){
}
while(a[--j].compareTo(pivot)>0){
}
if(i<j){
SwapReferences(a,i,j);
}else{
break;
}
}
SwapReferences(a,i,right-1);
quickSort(a,left,i-1);
quickSort(a,i+1,right) ;
}else{
insertionSort(a,left,right);
}
}
|
