复杂排序之归并、快速、三向切分、堆排序 详细总结

归并排序(MergeSort)

复杂度O(nlogn).

核心思想就是采用分而治之的方法,递归的合并两个有序的数组。效率比较高,缺点是空间复杂度高,会用到额外的数组。

原理

核心代码是合并的函数。合并的前提是保证左右两边的数组分别有序,在合并之前和之后在Java中我们可以用断言来保证数组有序。

合并的原理其实也很简单,先把a数组中的内容复制到额外储存的temp数组中去。分别用两个index指向a数组的起始位置和中间位置,保证a数组左右两边有序,比如ij。现在开始从头扫描比较左右两个数组,若a[i]<=a[j],则把a[i]放到temp数组中去,且i向前走一步。反正则放a[j],且j走一步。若其中一个数组走完了,则把另一个数组剩余的数直接放到temp数组中。

我们用递归的方式来实现左右两边有序。递归到数组只有1个数时肯定是有序的,再合并2个数,再退出来合并4个数,以此类推。


实现

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
public class MergeSort extends BaseSort {
Comparable[] temp ;
private void merge(Comparable[] a, int l, int m, int h){
for(int i=l;i<=h;i++){
temp[i]=a[i];
}
int i=l;
int j=m+1;
for(int k=l;k<=h;k++){
if(i>m) a[k]=temp[j++];
else if(j>h) a[k]=temp[i++];
else if(less(temp[i],temp[j])) a[k]=temp[i++];
else a[k] = temp[j++];
}
}
private void sort(Comparable[] a,int l,int h) {
if(l<h){
int mid = (l+h)/2;
sort(a,l,mid);
sort(a,mid+1,h);
merge(a,l,mid,h);
}
}
@Override
public void sort(Comparable[] a) {
temp = new Comparable[a.length];
sort(a,0,a.length-1);
}
}

优化

归并排序对小数组排序时,由于会有多重的递归调用,所以速度没有插入排序快。可以在递归调用到小数组时改采用插入排序。小数组的意思是差不多10个数左右。

如果递归时判断已经有序则不用继续递归。也可以增加效率。

1
2
3
4
5
6
7
8
9
private void sort(Comparable[] a,int l,int h) {
if(l<h){
int mid = (l+h)/2;
sort(a,l,mid);
sort(a,mid+1,h);
if (!less(a[mid+1], a[mid])) return;
merge(a,l,mid,h);
}
}

另外在合并时交互两个数组的顺序,能节省复制数组到辅助数组的时间,但节省不了空间。

适用范围

如果你对空间要求不高,且想要一个稳定的算法。那么可以使用归并排序。

快速排序

传说中最快的排序算法,听说能裸写快排,月薪可上10k(ps.不是我说的。)

快排平均情况下时间复杂度O(nlogn),最糟糕情况O(n²)O(n²)主要是因为选定的主元是极端值造成的,比如说最大值,最小值。不过这种情况一般很少出现,所以在进行快排之前我们需要对数组进行乱序,尽量避免这种情况的发生,

原理

第一步打乱数组。

然后也是分治法。归并是先分再合并。快排是先排序再分别排序两边。

排序过程核心思想是为了选出一个数,把数组分成左右两边,左边比主元小,右边比主元大。

选定第一个数作为主元。然后设定两个index指向数组首尾,比如ij。接着从两边向中间扫描,分别用a[i]a[j]和主元比较。若两边位置不对则交换a[i]a[j],比如说a[i]在扫描过程中遇到a[i]&gt;主元,那么则停止扫描,因为我们需要左边的数小于主元,反正右边也一样等到a[j]也停下来,则交换a[i]a[j].

得到中间的位置之后再分别左右递归排序。

优化

第一步的随机打乱数组,虽然会耗费一定时间,但却是必要的。

同样的小数组的排序,快排不如插入排序。所以小数组可以直接采用插入排序。

主元的选择方式可以有多种,比如随机选择主元。或者选取三个数,取中位数为主元,但是会耗费一定时间。

适用范围

虽然快速排序是不稳定的。但快速排序通常明显比其他Ο(nlogn)算法更快,因为它的内部循环很小。

快速排序在对重复数据的排序时,会重复划分数据进行排序。虽然性能也还行,但这里可以进行改进,就是下面介绍的三向切分排序。

三向切分(3-way partitioning)

快速排序的一种改进,使快排在有大量重复元素的数据,同样能保持高效。

原理

基本原理和快排差不多。三向切分的时候在划分数组时不是分为两组,而是分成三组。

  • 小于主元
  • 和主元相等
  • 大于主元

具体排序方式和快排差不多我就不赘述了,我觉得三向切分代码写起来比快排要简单。大家直接看代码吧

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ThreeWaySort extends BaseSort {
@Override
public void sort(Comparable[] a) {
sort(a,0,a.length-1);
}
public void sort(Comparable[] a,int l ,int h) {
if(l>=h) return;
Comparable v = a[l];
int i=l;
int lv=l;
int gh=h;
while(i<=gh){
int cmpIndex = a[i].compareTo(v);
if(cmpIndex<0) exch(a,i++,lv++);
else if(cmpIndex>0) exch(a,i,gh--);
else i++;
}
sort(a,l,lv-1);
sort(a,gh+1,h);
}
}

堆排序

时间复杂度O(nlogn),堆排序主要用二叉堆实现,在讲堆排序之前我们可以要先了解下二叉堆。

二叉堆

所谓的二叉堆用一颗二叉树表示,也就是每一个节点都大于它的左右子节点。也就是说根节点是最大的。

二叉树用数组存储,可以用下标来表示节点。比如i这个节点的父节点为i/2,左儿子为2*i,右儿子为2*i+1.

堆的操作主要有两种上浮和下沉。主要对应两种情况,比如在数组末尾添加节点,此时需要上浮节点,保证二叉堆的特点。反之在替换根节点是则需要下沉操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//上浮
public void swim(int k){
while(k/2>=1 && less(pq[k/2],pq[k])){
exch(pq,k/2,k);
k=k/2;
}
}
//下沉
private void sink() {
int k=1;
while(2*k<N){
int j=2*k;
if(less(pq[j],pq[j+1])) j++;
if(less(pq[k],pq[j])) exch(pq,k,j);
else break;
k = j;
}
}

堆排序实现原理

分为两步。

  • 把数组排成二叉堆的顺序
  • 调换根节点和最后一个节点的位置,然后对根节点进行下沉操作。

实现

可能我的代码和上面的动画略有出入,不过基本原理差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class HeapSort extends BaseSort {
private int N;
@Override
public void sort(Comparable[] a) {
N =a.length-1;
int k = N/2;
while(k>=1){
sink(a,k);
k--;
}
k = 1;
while(k<=N){
exch(a,k,N--);
sink(a,k);
}
}
}

适用范围

堆排序也是不稳定的。
堆排序在空间和时间上都是O(nlogn),且没有最糟情况,但在平均情况下比快排慢。
所以现在大部分应用都是用的快排,因为它的平均效率很高,几乎不会有最糟情况发生。
但如果你的应用非常非常重视性能的保证,比如一些医学上的监控之类的。那么可以使用堆排序。
还有一个堆排序的缺点,是它无法利用缓存,几乎很少和相邻元素的比较。

性能测试

我测试了一下,用10000个数据,排序100次。使用上述四个算法的运行时间如下。

冒泡排序 26.196000000000005
选择排序 9.046000000000006
插入排序 11.630999999999998
希尔排序 0.20900000000000016
归并排序 0.24100000000000016
快速排序 0.16800000000000012
三向快速排序 0.18300000000000013
堆排序 0.18800000000000014

Summary

同时推荐一个很好的网站,对各种算法进行了总结,和动画描述。

sorting-algorithms

Reference

维基百科

算法 4th