常见排序算法

排序在算法中的地位不言而喻,而且也是在面试中经常被问到的点。本文主要分析和比较几种常见的基于比较的排序算法。通常,分析排序算法会从比较次数、交换次数、时间负责度、空间复杂度、最坏情况下的复杂度以及适用场景几个方面去考虑,所以本文也基于这样分析,并用Java进行了简单的实现,且仅考虑了升序的情况,代码只测试了几个简单的用例,如有不对的地方,还请指正。


选择排序

很直观的一种排序,扫描一次数组,确定一个最小值,让它与未排序部分的第一个值交换,然后从刚才交换的值的下一个位置扫描。当扫描了N次以后数组也就有序了。

由于想法和实现都很简单,它的性能也只能是N^2的:

  • 比较次数:N^2/2
  • 交换次数:N
  • 时间复杂度:N*N
  • 空间复杂度:原地的,不需额外空间
  • 最坏情况下时间复杂度:和输入无关
  • 稳定性:不稳定

选择排序每次确定了一个元素的位置,但是每次循环得到的比较结果都没有被下一次利用,所以效率比较低,在实际中应该应用不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void selectionSort(Comparable[] arr) {
for(int i=0;i<arr.length;i++) {
int min=i;
for(int j=i;j<arr.length;j++) {
if(arr[j].compareTo(arr[min])<0) {
min=j;
}
}
Comparable tmp=arr[i];
arr[i]=arr[min];
arr[min]=tmp;
}
return;
}

插入排序

插入排序的想法也很简单,假设当前元素之前的所有元素都已经有序(一个元素的时候就是有序的),那么用当前元素去和之前的元素一一比较,当当前元素比前一个元素小,就交换它们的位置。

插入排序理论上的复杂度和选择排序是一样的,但是它与输入是有关系的,当输入是部分有序的时候,它能达到线性级别的效率。它的性能:

  • 比较次数:平均 N×N/4,最坏 N×N/2,最好 N-1
  • 交换次数:平均 N×N/4,最坏 N×N/2,最好 0
  • 时间复杂度:N*N
  • 空间复杂度:原地的,不需额外空间
  • 最坏情况下时间复杂度:N*N
  • 稳定性:稳定

插入排序在应对小数组和部分有序的数组时,能得到很好的性能,优于其他的算法,所以它适用于非随机的小数组,并且很多高级的排序算法在递归到小数组时通常用它来替换,能有效提高算法性能。

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertionSort(Comparable[] arr) {
for(int i=1;i<arr.length;i++) {
Comparable key=arr[i];
int j=i-1;
while(j>=0 && arr[j].compareTo(key)>0) {
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
return;
}

希尔排序

希尔排序是对插入排序的优化,考虑到插入排序在部分有序和小数组情况下的优秀性能,将数组分成H组,每组的元素都是数组中间隔为H的元素,分别对每组元素进行插入排序,然后再将H减小,再进行插入排序,直到H等于1。

希尔排序的复杂度没有具体的证明,在平方级与线性对数级之间。希尔排序简单高效,一个小小的改动让算法脱离了平方级别,效率远高于插入排序,而且数组越大优势越大。算法的效率与选择的H递增序列有关。性能:

  • 比较次数:
  • 交换次数:
  • 时间复杂度:N e(3/2)
  • 空间复杂度:原地的,不需额外空间
  • 最坏情况下时间复杂度:
  • 稳定性:不稳定

希尔排序在应对中等大小的数值时很有效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void shellSort(Comparable[] arr) {
int len=arr.length;
for(int h=len/2;h>=1;h/=2) {
for(int i=h;i<len;i++) {
Comparable key=arr[i];
int j=i-h;
while(j>=0 && arr[j].compareTo(key)>0) {
arr[j+h]=arr[j];
j-=h;
}
arr[j+h]=key;
}
}
return;
}

归并排序

归并排序是分治思想的体现,将数组划分成两部分,分别排序,然后再合并两个有序数组(当一个元素时,自然是有序的),递归的进行,就能然整个数组有序。归并排序能让算法的复杂度稳定在 NlgN。

归并排序通过二分的方式,能在算法时间复杂度达到 NlgN,而且它与输入没有关系,但是归并需要利用额外的空间,所以空间复杂度是 N。

  • 比较次数:1/2NlgN ~ NlgN
  • 交换次数:
  • 时间复杂度:NlgN
  • 空间复杂度:N
  • 最坏情况下时间复杂度:
  • 稳定性:稳定

在空间不紧张,而且要求稳定的情况下,归并排序是一个好的选择。

归并排序通常的写法是递归的,但是也可以用非递归的方式来写。

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
public static void mergeSort(Comparable[] arr) {
mergeSortHelper(arr, 0, arr.length);
}
private static void merge(Comparable[] arr, int l, int mid, int r) {
Comparable[] tmp = new Comparable[arr.length];
for(int k=l;k=r;k++) {
tmp[k]=arr[k];
}
int i=l,j=mid+1;
for(int k=l;k<=r;k++) {
if(i>mid) arr[k]=tmp[j++];
else if(j>r) arr[k]=tmp[i++];
else if(tmp[i].compareTo(tmp[j])<0) arr[k]=tmp[i++];
else arr[k]=tmp[j++];
}
}
private static void mergeSortHelper(Comparable[] arr, int l, int r) {
if(l==r) return;
int mid=(l+r)/2;
mergeSortHelper(arr, l, mid);
mergeSortHelper(arr, mid+1, r);
merge(arr, l, mid, r);
}
public static void mergeSort2(Comparable[] arr) {
int len=arr.length;
for(int sz=1;sz<len;sz*=2) {
for(int j=0;j<len-sz;j+=sz*2) {
merge(arr, j, j+sz-1,Math.min(j+sz+sz-1, len-1));
}
}
}

快速排序

快速排序每次递归选择一个元素作为key,然后将数组中小于key的元素放左边,大于key的元素放右边。以key为分界点将数组分成两部分,再分别对两个子数组进行同样的操作。

快速排序在大多数应用下是最快的排序算法,它的负责度是NlgN,但是常数因子比别的同级别的算法小,因为他的内循环很简单,只是访问一遍数组,而且是顺序的访问数组,能有效利用缓存。但是在最坏的情况下,也就是每次的Key选择都是最大或最小的元素,快排就会变成冒泡排序,每次只能确定一个值。性能:

  • 比较次数:
  • 交换次数:
  • 时间复杂度:NlgN
  • 空间复杂度:lgN
  • 最坏情况下时间复杂度:N^2
  • 稳定性:不稳定

快排的应用很广泛,由于它在大多数情况下都比别的算法快,内循环简单,比较次数少。快排的性能取决于切分元素的选择,最好的情况是每次都把数组均分成两半,最坏情况是每次都选到了最大或最小的元素,此时退化成冒泡排序,每次只能确定一个值的位置。快拍的时间复杂度是 nlgn 且常数比其他同级别的算法小,空间复杂度 lgn (调用函数栈的开销),最坏情况下也就是冒泡排序的复杂度,分别是 n^2, n。通常会在排序前打乱所有数据,使待排序数据随机分布。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static void quickSort(Comparable[] arr, int start, int end) {
if(start>=end) return;
int i=start,j=end+1;
Comparable key=arr[i];
while(true) {
while(j>i && arr[--j].compareTo(key)>=0);
if(i>=j) break;
arr[i]=arr[j];
while(i<j && arr[++i].compareTo(key)<0);
if(i>=j) break;
arr[j]=arr[i];

}
arr[i]=key;
quickSort(arr, start, i-1);
quickSort(arr, i+1, 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
public static void quickSort_3way(Comparable[] arr, int left, int right) {
if(left>=right) return;
int l=left, r=right, i=left+1;
Comparable key=arr[left];
while(i<r) {
int com=arr[i].compareTo(key);
if(com<0) {
Comparable tmp=arr[l];
arr[l]=arr[i];
arr[i]=tmp;
i++;
l++;
} else if(com>0) {
Comparable tmp=arr[r];
arr[r]=arr[i];
arr[i]=tmp;
r--;
} else {
i++;
}
}
quickSort_3way(arr, left, l-1);
quickSort_3way(arr, r+1, right);
}

堆排序

堆通常指二叉堆,有大堆和小堆。用数组表示,数组元素之间的关系可以按照顺序排成一棵完全二叉树。在大堆中,以任意节点为根节点的子树,它的根节点是最大的节点;小堆相反。若索引从0开始表示,那么 k 的两个子节点分别是 2×k+1 和 2×k+2 ,k 的父节点是 (k-1)/2。
大堆的最大元素在堆顶,用堆顶元素与最末元素交换,前移一位最末元素的指针,同时使堆重新有序,直到末元素指针指到堆顶。注意建堆的时候是从第一个非叶节点开始对节点下沉。

利用了堆的性质,使算法的复杂度达到了 NlgN ,同时空间复杂度是 1。

  • 比较次数:少于(2NlgN+2N)
  • 交换次数:NlgN+N
  • 时间复杂度:NlgN
  • 空间复杂度:1
  • 最坏情况下时间复杂度:2NlgN
  • 稳定性:不稳定

堆排序不能利用缓存,速度也不如快排,所以很少使用。但是在对内存要求很高的环境,如嵌入式系统中,堆排序是一个好的选择。虽然堆排序的应用不多,但是用堆实现的优先队列很重要,它能在对数级别实现插入和删除。

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
public static void heapSort(Comparable[] arr) {
heap_build(arr);
int k=arr.length-1;
while(k>0) {
Comparable tmp=arr[k];
arr[k]=arr[0];
arr[0]=tmp;
k--;
heap_sink(arr, 0, k);
}
}
private static void heap_build(Comparable[] arr) {
int k = arr.length-1;
for(int i=(k-1)/2;i>=0;i--) {
if(arr[i].compareTo(arr[2*i+1]) > 0 || (2*i+1<=k && arr[i].compareTo(arr[2*i+2])>0)) heap_sink(arr, i, arr.length-1);
}
}
private static void heap_sink(Comparable[] arr, int k, int len) {
if(k>len/2-1 || k<0) return ;
while(k<=len/2-1) {
int c=2*k+1;
if(c+1 < len && arr[c].compareTo(arr[c+1])<0) c++;
if(arr[c].compareTo(arr[k])>0) {
Comparable tmp=arr[c];
arr[c]=arr[k];
arr[k]=tmp;
k=c;
} else {
break;
}
}
}

总结

几种常见的排序算法都介绍完了,这里简单的总结一下:

  • 在所有排序算法中,应用最广泛的是快速排序。
  • 快排,归并、堆排都是 NlgN 级别的,但是快排的内循环最简单,只是顺序的访问数组,且比较次数和交换次数都少。在大部分应用场景下,快排都是最快的,但是他的性能和选择的分隔元素有关。归并排序和输入无关,总能保证nlgn的效率,但是它的空间复杂度是 O(N),同时,它是稳定的排序。堆排序应用的不多,除非是在对内存要求很高的环境下,因为它的空间复杂度是1。
  • 在数组比较小的情况下,优先选择插入排序或选择排序。因为算法简单,不需要递归调用,在小数组时比nlng的算法快。插入排序和输入有关,在小数组,部分有序的情况下,能达到线性级别,所以很多大数组排序的优化都是递归到小数组以后用插入排序。
  • 希尔排序是插入排序的改进。通过将数组分成k组,每组的元素间间隔是k,对k组元素分别进行插入排序,然后减小间隔直到1。