摘要 排序是数据结构中非常重要的内容,也是公司笔试面试经常会考的内容。掌握所有的排序并不是必须的,关键是知道在什么情况下,使用什么排序算法,效率更高,知道哪种排序算法是稳定的,以及该排序算法的时间复杂度。排序要求的数据结构一般都是静态数组的形式,如果单单去背诵某一排序算法的实现,你可能这段时间能够记住,但不能保证过段时间你还能记住,因此,要想彻底记住这些排序算法,必须从它的实现法则上去记忆。

排序算法简介

本文主要讲述的是内排序算法,关乎外排序需要与外存交互,因此这里不做考虑。

所有的内排序算法可以分为五类:选择排序,插入排序,交换排序,归并排序,基数排序。

其中选择排序又可以分为简单选择排序,树形选择排序(锦标赛排序),堆排序(树形选择排序的一种).

插入排序分为直接插入排序和希尔排序(缩小增量排序).

交换排序分为冒泡排序,快速排序。

下面是对所有内排序算法的时间复杂度,空间复杂度和稳定性的统计表格。

  • 时间复杂度:执行该算法的基本语句的执行频度,通常指最坏情况下的时间复杂度。
  • 空间复杂度:执行该算法所需要的额外辅助存储空间的大小。
  • 稳定性:如果待排序列中有若干个相等的元素,排序结束之后,这些相等元素的先后顺序并没有随排序的执行而发生改变,就称该排序算法是稳定的。
排序算法 时间复杂度 空间复杂度 稳定性
简单选择排序 $$$O(n^2)$$$ $$$O(1)$$$ 不稳定
堆排序 $$$O(nlgn)$$$ $$$O(1)$$$ 不稳定
直接插入排序 $$$O(n^2)$$$ $O(1)$$$ 稳定
希尔排序 $$$O(n^{1.4})$$$ $$$O(1)$$$ 不稳定
冒泡排序 $$$O(n^2)$$$ $$$O(1)$$$ 稳定
快速排序 $$$O(nlgn)$$$ $$$O(n)$$$ 不稳定
归并排序 $$$O(nlgn)$$$ $$$O(n)$$$ 稳定
基数排序 $$$O(n)$$$ $$$O(n)$$$ 稳定

对以上统计信息的总结:

  • 时间复杂度
    • $$$O(n^2)$$$:简单选择排序、直接插入排序、冒泡排序
    • $$$O(nlgn)$$$:堆排序、快速排序、归并排序
    • $$$O(n^{1.4})$$$:希尔排序
    • $$$O(n)$$$:基数排序
  • 空间复杂度
    • 快速排序和归并排序都需要额外的$$$O(n)$$$的辅助栈空间用于递归。
    • 基数排序用空间换时间。空间复杂度也为$$$O(n)$$$
    • 其余排序算法都是就地排序,空间复杂度为$$$O(1)$$$
  • 稳定性
    • 直接插入排序、冒泡排序、归并排序、基数排序是稳定的。
    • 其余排序算法不稳定。

排序算法实现

简单选择排序

思想:每次从剩下的无序区中选取最小的加入的有序区中,最后无序区只剩一个元素,直接加入即可,简单选择排序的实现关键在于无序区元素的比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void selectSort(int[] data){
for(int i=0; i<data.length-1; i++){
int minIndex = i;
for(int j=i+1; j<data.length; j++){
if(data[j] < data[minIndex]){
minIndex = j;
}
}
if(minIndex != i){
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}

堆排序

思想:堆排序是树形选择排序的一种,相对于简单选择排序,它可以充分利用上一次比较的结果,因而较快地完成排序。堆排序是利用完全二叉树顺序存储的特性完成。堆中,任何双亲结点的关键字均不大于或不小于其孩子节点的关键字。堆中任何一棵子树也是堆。

以大根堆(堆中任何双亲结点的关键字都大于其孩子结点关键字)为例,介绍堆排序主要的两个步骤如下:

  • 初始化堆
  • 将当前无序区中的第一个元素与最后一个元素交换,使最后一个元素进入有序区。重新调整无序区,并再次将无序区中第一个元素加入有序区,直到无序区只包含一个元素。

堆排序的关键问题在于:如何初始化堆,如何调整堆。这两个问题都要从堆的性质出发去解决,假设,现在的堆满足堆性质,我们可以将第一个元素加入有序区,这样一来,无序区的最后一个元素被交换到了第一个位置,那么该元素极有可能破坏堆性质。我们从该元素出发,讨论如果该元素小于其孩子中的一个,那就证明它破坏了堆性质,需要将其与其拥有较大关键字的孩子进行交换。交换之后它的孩子也有可能破坏堆性质,因此如此递推下去,调整区间为整个无序区,直至该堆重新满足堆性质。每次需要调整的都只是按树的层级往下递推,而不需要像简单选择排序一样每次都从无序区所有元素选择最小的,比较的次数显然减少了。这种调整堆的方法称之为筛选法

初始化堆的过程也可以理解为调整堆,按照完全二叉树的顺序存储,只有根节点才有可能不满足堆性质,需要进行调整,而完全二叉树中,结点编号在[0,n/2]的为根节点,因此只需要调整[0,n/2]的所有根节点即可,由于初始化堆,所有元素均为无序区,因此调整区间为整个数据序列。既然堆排序的两个关键步骤都依赖调整堆,那接下来先介绍调整堆的算法实现。

1
2
3
4
5
6
7
8
9
10
11
12
public void heapAdjust(int[] data, int low, int high){
for(int j=2*low; j<=high; j*=2){
int temp = data[low];
if(j < high && data[j] < data[j+1])
j++;
if(temp > a[j])
break;
data[low] = data[j];
data[j] = temp;
low = j;
}
}

下面给出初始化堆的算法实现:

1
2
3
4
5
public void initHeap(int[] data){
for(int i=data.length/2; i>=0; i--){
heapAdjust(data, i, data.length-1);
}
}

有了初始化堆和调整堆的算法实现,堆排序的算法实现如下:

1
2
3
4
5
6
7
8
9
10
11
public void heapSort(int[] data){
initHeap(data);

for(int i=data.length-1; i>0; i--){
int temp = data[0];
data[0] = data[i];
data[i] = temp;

heapAdjust(data, 0, i-1);
}
}

直接插入排序

思想:直接插入排序非常类似于我们生活中的打扑克,在拿到下一张扑克牌的时候,我们需要将其插入到手中已排好序的所有扑克牌中的合适位置。开始时,有序区为第一个元素,无序区为待插入的其余元素。从第二个元素起开始插入,如果插入元素大于前一个元素(前一个元素为当前有序区最后一个元素),则无需调整,如果插入元素小于前一个元素,则顺序往前,并将比插入元素大的元素往后移动直到找到比插入元素小的元素位置,此即为插入位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void insertSort(int[] data){
for(int i=1; i<data.length; i++){
if(data[i] < data[i-1]){
int temp = data[i];
int j = i-1;
for(; j>=0; j--){
if(temp < data[j]){
data[j+1] = data[j];
}else{
break;
}
}
data[j+1] = temp;
}
}
}

希尔排序

思想:希尔排序是一种缩小增量插入排序,每次不是比较一位,而是跨越一个增量进行插入,先将待排数据区以增量d划分为d个小组,距离为d的倍数的记录在一个组,如1,2,3,4,5,6,7,8,9,10,这10个元素,选择增量d=5进行划分,则可以分为(1,6),(2,7),(3,8),(4,9),(5,10)这5个组,对每一个增量进行组内排序,然后依次选定较小的增量,划分为较小的组,借助上一次的排序结果,已经近似有序了,所以这次排序相对较快,最后的增量一定是1,而且这个时候,记录序列已基本有序。

希尔排序为什么比直接插入排序快,其原因在于:

  • 单文件近似有序时,直接插入排序移动和比较的次数都较少。
  • 希尔排序开始增量较大,分组较多,每组的记录数目少,所以各个小组内完成直接插入较快,后来随着增量逐渐减少,组内元素变多,但是借助上一次增量的排序结果,此时组内元素已基本有序,因此新的增量排序也较快。

下面先介绍给定一个增量的一趟排序算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public shellInsert(int[] data, int d){
for(int i=d+1; i<data.length; i++){
if(data[i] < data[i-d]){
int temp = data[i];
int j= i-d;
for(; j>=0; j-=d){
if(temp < data[j]){
data[j+d] = data[j];
}else{
break;
}
}
data[j+d] = temp;
}
}
}

从以上代码也可以发现,每一个组内都是直接插入排序,但是由于组内元素距离是d的倍数,因此,每次直接插入的步长不再是1,而是d.

希尔排序性能的好坏关键在于增量序列的选取:

  • 最后一个增量必须为1
  • 应该尽量避免增量序列中的值(尤其是相邻的值)互为倍数的情况。

对于增量序列increment,希尔排序实现如下:

1
2
3
4
5
public void shellSort(int[] data, int[] increment){
for(int i=0; i<increment.length; i++){
shellInsert(data, increment[i]);
}
}

冒泡排序

思想:冒泡排序是最简单也是最直接的排序算法,冒泡排序属于交换类排序,排序过程中需要频繁交换关键字。一趟冒泡排序之后,会选出最大关键字到最后位置,类似冒出最大气泡,每趟排序过程中,都需要进行关键字的两两比对,并可能交换,直至交换出最大关键字。外循环为排序趟数,至多为n-1次。每趟排序过程即内循环,需要从剩下的无序气泡中不断交换出最大者。冒泡排序实现如下.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void bubbleSort(int[] data){
boolean flag = false;
for(int i=0; i<data.length-1; i++){
flag = false;
for(int j=0; j<data.length-i-1; j++){
if(data[j+1] < data[j]){
data[j+1] ^= data[j];
data[j] ^= data[j+1];
data[j+1] ^= data[j];
flag = true;
}
}
if(flag == false)
break;
}

}

以上代码是属于优化的冒泡排序算法,设置一个标志变量,如果前一趟排序过程中,没有元素发生位置交换,说明所有未知区的元素已有序,因此退出冒泡排序过程。

快速排序

思想:快速排序平均性能与最坏性能相同,因此比较常用。快速排序算法的关键在于每一次排序过程的划分,找到基准位置,并通过基准位置一分为二,递归实现快排,实际上是一种分治策略。基准元素的选取也会影响快排效率,不失一般性,我们通常选取第一个位置元素作为基准元素,参与快排。每次划分过程中,先从后往前遍历,直到找到比基准元素小的元素,将其放置到基准元素位置,然后再从前往后直到找到比基准元素大的元素,将其放到上一次放置的基准元素位置。直到前后指针碰到,该指针位置就是基准位置,将基准元素放置到该位置并返回该基准位置。下面是划分实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int partition(int[] data, int low, int high){
int i=low,j=high;
int pivot = data[low];
while(i < j){
while(i<j && data[j] > temp)
j--;
data[i] = data[j];
while(i<j && data[i] < pivot)
i++;
data[j] = data[i];
}
data[i] = pivot;
return i;
}

快排的递归实现:

1
2
3
4
5
6
7
public void quickSort(int[] data, int low, int high){
if(low < high){
int pivotPos = partition(data, low, high);
quickSort(data, low, pivotPos-1);
quickSort(data, pivotPos+1, high);
}
}

归并排序

思想:和快排类似,归并排序也是一种递归分治策略,区分于快排,归并排序关键在于两个以中间位置划分的有序序列的合并。二路归并排序,最终子序列中只有一个元素一定是有序的,将其合并,然后一层层地递归进行。合并算法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void merge(int[] data, int low, int mid, int high){
int i = low;
int j = mid+1;
int k= 0;
int result[] = new int[high-low+1];
while(i <= mid && j <= high)
result[k++] = data[i] < data[j] ? data[i++] : data[j++];
while(i <= mid)
result[k++] = data[i++];
while(j <= high)
result[k++] = data[j++];
for(k=0; k<result.length; k++){
data[low++] = result[k];
}
}

二路归并策略,以中间位置,将待排序列一分为二,进行递归计算

1
2
3
4
5
6
7
8
public void mergeSort(int[] data, int low, int high){
if(low < high){
int mid = (low+high) / 2;
mergeSort(data, low, mid);
mergeSort(data, mid+1, high);
merge(data, low, mid, high);
}
}

基数排序

思想:基数排序属于一种空间换时间的策略,要了解基数排序,最好先了解桶排序思想。

桶排序:将数据序列分到有限数量的桶子里。每个桶子再分别排序,桶子内部的排序算法可采用上述基本排序算法中的任意一种,排序完成之后,依次输出每个桶子里的数字,且每个桶子的数字从小到大输出,这样就得到数字排好序的序列了。

假设有n个关键字,有m个桶,如果数字是平均分布的,则每个桶子平均有n/m个数字,如果对每个桶采用快速排序,那么整个算法的时间复杂度是:

$$
O(n+m*n/m*lg(n/m)) = O(n+nlgn-nlgm)
$$

从上式可以看出,当m接近n时,,桶排序复杂度接近$$$O(n)$$$。

基数排序:按照低位先排序,然后搜集;再按照高位排序,然后搜集;依次类推,直到最高位。基数排序是分别排序,分别搜集,所以是稳定的。具体实现,请读者自行查阅。