复杂排序之归并、快速、三向切分、堆 详细总结
归并排序(MergeSort)
复杂度 O(nlogn) .
核心思想就是采用分而治之的方法，递归的合并两个有序的数组。效率比较高，缺点是空间复杂度高，会用到额外的数组。
原理
核心代码是合并的函数。合并的前提是保证左右两边的数组分别有序，在合并之前和之后在 Java 中我们可以用断言来保证数组有序。
合并的原理其实也很简单，先把 a 数组中的内容复制到额外储存的 temp 数组中去。分别用两个 index 指向 a 数组的起始位置和中间位置，保证 a 数组左右两边有序，比如 i ， j 。现在开始从头扫描比较左右两个数组,若 a[i]<=a[j] ，则把 a[i] 放到 temp 数组中去，且 i 向前走一步。反正则放 a[j] ，且 j 走一步。若其中一个数组走完了，则把另一个数组剩余的数直接放到temp数组中。
我们用递归的方式来实现左右两边有序。递归到数组只有1个数时肯定是有序的，再合并2个数，再退出来合并4个数，以此类推。
实现
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个数左右。
如果递归时判断已经有序则不用继续递归。也可以增加效率。
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指向数组首尾，比如 i ， j 。接着从两边向中间扫描，分别用 a[i] 和 a[j] 和主元比较。若两边位置不对则交换 a[i] 和 a[j] ，比如说 a[i] 在扫描过程中遇到 a[i]>主元 ，那么则停止扫描,因为我们需要左边的数小于主元,反正右边也一样等到 a[j] 也停下来,则交换 a[i] 和 a[j] .
得到中间的位置之后再分别左右递归排序。
优化
第一步的随机打乱数组，虽然会耗费一定时间，但却是必要的。
同样的小数组的排序，快排不如插入排序。所以小数组可以直接采用插入排序。
主元的选择方式可以有多种，比如随机选择主元。或者选取三个数，取中位数为主元，但是会耗费一定时间。
适用范围
虽然快速排序是不稳定的。但快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环很小。
快速排序在对重复数据的排序时，会重复划分数据进行排序。虽然性能也还行，但这里可以进行改进，就是下面介绍的三向切分排序。
三向切分(3-way partitioning)
快速排序的一种改进，使快排在有大量重复元素的数据，同样能保持高效。
原理
基本原理和快排差不多。三向切分的时候在划分数组时不是分为两组，而是分成三组。
- 小于主元
- 和主元相等
- 大于主元
具体排序方式和快排差不多我就不赘述了，我觉得三向切分代码写起来比快排要简单。大家直接看代码吧
实现
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 .
堆的操作主要有两种上浮和下沉。主要对应两种情况，比如在数组末尾添加节点，此时需要上浮节点，保证二叉堆的特点。反之在替换根节点是则需要下沉操作。
//上浮
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;
}
}
堆排序实现原理
分为两步。
- 把数组排成二叉堆的顺序
- 调换根节点和最后一个节点的位置，然后对根节点进行下沉操作。
实现
可能我的代码和上面的动画略有出入，不过基本原理差不多。
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) ,且没有最糟情况。
在平均情况下比快排稍慢一点。
之所以堆排序应用没有快排广的原因，是因为它无法利用缓存，几乎很少和相邻元素的比较。
性能测试
冒泡排序 26.196000000000005
选择排序 9.046000000000006
插入排序 11.630999999999998
希尔排序 0.20900000000000016
归并排序 0.24100000000000016
快速排序 0.16800000000000012
三向快速排序 0.18300000000000013
堆排序 0.18800000000000014
Summary
同时推荐一个很好的网站，对各种算法进行了总结，和动画描述。
sorting-algorithms
Reference
维基百科
算法 4th
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
