算法复习 (一) 排序

排序

第一节 前文

1.1 什么是排序?

排序就是将一组对象按照某种逻辑顺序重新排列的过程

排序往往是我们解决现实问题的第一步,接下来我们学习几种经典、优雅和高效的排序算法。

1.2 如何比较两种排序算法?

  1. 实现并调试他们
  2. 分析它们的基本性质
  3. 对它们的相对性能做出猜想
  4. 用实验证明猜想

第二节 排序算法

回顾一下常用的几种排序算法,实现代码可在GitHub中获取:

URL: https://github.com/LAILAIWA/AlgorithmTraining

SSH: git@github.com:LAILAIWA/AlgorithmTraining.git

代码位置:https://github.com/LAILAIWA/AlgorithmTraining/tree/master/src/sort

简单定义一个排序基类,实现几个常用的排序所需方法。

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 class SortExample {

//是否小于
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

//交换
public static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}

//单行打印数组
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}

//测试数组元素是否有序
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1])) return false;
return true;
}
}

每种排序算法都需要分析以下内容:

  1. 验证正确性:通过如 assert isSorted(a); 判断是否每个元素都是有序的,当然这只能判断最终结果数组是否有序,不能检测出如将所有元素替换为相同元素等漏洞。
  2. 评估运行时间:评估算法的性能,首先要计算各种排序算法在随机输入下的基本操作的次数(包括比较交换,或读写数组的次数,前者用来评估排序算法,后者用于评估不交换元素的算法)。
  3. 额外内存开销:排序算法有两种,除了函数调用所需栈和固定数目的实例变量外无需额外内存的原地排序算法,以及需要额外内存空间来存储一份数组副本的其他排序算法
  4. 数据类型:排序算法适用于实现 Comparable 接口的数据类型,实现此接口需要实现一个 compareTo() 方法来定义目标对象的自然次序。该方法要求要实现一个全序关系:
    • 自反性:对于所有的v,v=v;
    • 反对称性:对于所有的v<w都有v>w,且v=w时w=v;
    • 传递性:对于所有的v、w和x,如果v<=w且w<=x,则v<=x。

2.1 选择排序

最简单的排序算法—选择排序,不断地选择当前最小元素。

选择排序:找到数组中最小的元素,将其与数组第一个元素交换,再在剩余的元素中找到最小的元素,并将其与第二个元素交换,继续在余下数组中循环此过程直到所有元素排序。

2.1.1 代码

1
2
3
4
5
6
7
8
9
10
11
public static void sort(Comparable[] a){//将数组a按升序排序
int N = a.length;//记录数组长度
for(int i = 0;i < N;i++){//将a[i]与a[i+1...N]最小元素交换
int min = i;
//循环遍历找到当前最小元素
for(int j = i+1;j < N;j++)
if(less(a[j],a[min])) min = j;
//将第i小元素交换至位置i
exch(a,i,min);
}
}

2.1.2 排序轨迹

2.1.3 运行时间

对于长度为N数组,选择排序需要 N^2^/2 次比较和 N 次交换

交换次数为N很明显,每个元素需要且仅需要一次交换;比较次数则需要根据排序轨迹来总结计算,通过一张 N * N 的表格来表示排序轨迹,对角线表示元素进行一次交换,结合代码可以得知,0到N-1的任意i都会进行一次交换和N-1-i次比较,所以比较总次数等于 (N-1) + (N - 2) + …… + 2 + 1 = N (N - 1) / 2 = N^2 / 2。

2.1.4 额外内存空间

不需要

2.1.5 特点

  1. 运行时间和输入无关,即使是已排序过的数组再排序亦无不同
  2. 数据移动是最少的

2.2 插入排序

插入排序:每次将新来元素插入已经有序的数组中,右侧数据需要右移,当索引到达数组右端排序结束。

2.2.1 代码

1
2
3
4
5
6
7
8
9
public static void sort(Comparable[] a){
int N = a.length;
// 从第二个元素开始遍历数组
for(int i = 1;i < N;i++){
// 第二层游标j从游标i开始,逆向遍历,不断和比其小的元素交换位置,直到移动到0位置
for(int j = i;j > 0 && less(a[j],a[j-1]);j--)
exch(a,j,j-1);
}
}

2.2.2 排序轨迹

2.2.3 运行时间

  • 对于长度为N的数组,插入排序平均需要 N^2^/4 次比较和 N^2^/4 次交换
  • 最坏需要 N^2^/2 次比较以及 N^2^/2 次交换
  • 最好情况下需要 N-1比较0交换

最坏情况即对角线以下所有元素都需要移动位置(逆序数组),最好情况则是都不需要(顺序数组)。随机排列的数组,平均情况下每个元素都可能向后移动半个数组的长度,因此交换总数是对角线以下元素总数的一半。

比较的次数是交换次数加上一个额外的项,N减去被插入的元素正好是已知的最小元素的次数,最坏情况下可忽略(几乎每次比较都要交换位置),最好情况下等于 N-1

2.2.4 额外内存空间

不需要

2.2.5 特点

  • 运行时间取决于数组元素的初始顺序。
  • 类似于选择排序,索引左侧元素都是有序的,选择排序固定次序依次找出插入排序则是固定元素依次排序
  • 适用于对有序数组(部分有序)进行排序。
  • 当数组乱序时就会导致交换次数过多,使性能大幅度下降。

2.3 希尔排序

希尔排序:希尔排序是基于插入排序的改进版本,主要针对乱序的数组。插入排序只交换相邻元素,所以导致交换次数过多从而影响性能(如最小元素在数组尽头,将其挪至正确位置就需要 N-1 次交换),而希尔排序则交换不相邻的元素对局部进行排序,最终用插入排序将局部有序的数组排序加速了元素移动的速度

排序思想:使数组中固定间隔H内的元素是有序的,即H有序数组:一个由H个有序子数组组成的数组。

最简单的实现希尔排序的方式:对于子数组用插入排序进行排序,将子数组中大的元素右移,移动元素的距离由1改为H,希尔排序即增量为H的插入排序。H亦是一组以1为起点的递增序列

希尔排序之所以高效是因为其权衡了子数组的规模和有序性,初始时子数组较短,且都部分有序,这很适合插入排序。

2.3.1 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void sort(Comparable[] a){
int N = a.length;
int H = 1;
// 根据元素数目初始化H
while (H < N/3)
H = 3*H + 1;
//同插入排序,但游标不是相邻移动,而是间隔H,将a[i]插入到a[i-H],a[i-2H]...之中
while (H >= 1) {
// 游标i从H开始遍历数组
for(int i = H;i < N;i++){
// 游标j仍从游标i开始,逆向隔H遍历,
for(int j = i; j >=H && less(a[j],a[j-H]);j-=H)//
exch(a,j,j-H);
}
H = H/3;
}
}

2.3.2 排序轨迹

H=13 P与S交换

H=4 LP,ES,EH,AR,AL,MT,MP,LX,LO,ER,EL

H=1 EL,EL,AL,AE,AE,HM,HL,LM,EM,EL,EL,EH,OS,OP,LS,LP,LO,LM,ST,RX,RT,RS,RS

H=1时希尔排序等价于插入排序,但因为前述步骤此时子数组已都有序,所以插入排序不会有比较长的持续交换情况。

2.3.3 递增序列

递增序列如何选择?有很多论文研究了各种不同的递增序列,但都没法证明哪个序列是“最好的”。优秀的递增序列有待我们去实验和发现。

2.3.4 运行时间

希尔排序的性能论证十分复杂,目前的结论是其运行时间达不到平方级别,最坏情况大概与 N^3/2^ 成正比,相比插入排序一点微小的改变就突破了平方的屏障,这正是算法设计的目标。

2.3.5 额外内存空间

不需要

2.3.6 特点

  • 希尔排序通常会被有经验的程序员使用,一些更高效的算法除非对于N特别大的情景,一般只会比希尔排序快不到两倍,且设计复杂度会更大,希尔排序的代码量很小,也不需要额外的内存空间,所以可以首先考虑希尔排序再根据情况选择更复杂的排序算法。
  • 希尔排序的速度要远远快于选择排序和插入排序,且数组越大时优势越明显。
  • 相比选择排序,希尔排序可以应用于一些大型数组,且对于乱序的数组表现也很好。
  • 时间复杂度和增量序列有关。

2.4 归并排序

归并:即将两个有序数组归并成一个更大的有序数组。

归并排序:根据归并思路设计了简单的递归排序算法—归并排序。即对数组排序时,先将其分为两半分别排序,然后再将结果归并。归并排序可以保证任意长度N数组排序所需时间与NlogN成正比,缺点是所需额外空间与N成正比用空间换时间

2.4.1 原地归并

归并并不高效:每次归并都创建新数组来存储排序结果是非常耗能的设计,所以需要有一种在原数组中归并的方法,我们可以想象一下有哪些办法可以实现这一需求?

没有既简单又高效的归并方案:但实际上所有的原地归并方法都会造成复杂度大幅上升,特别是和使用额外内存空间的实现相比,原地归并一般会采用共用一个公共数组来暂存数组数据。

下文中 merge(Comparable[] a, int lo, int mid, int hi) 方法即原地归并的实现方法,通过一个辅助数组放置复制的元素,再合并回原数组。

2.4.2 自顶向下的归并排序

自顶向下的归并排序:是基于原地归并的抽象,并采用分治思想设计的另外一种递归归并。这段递归代码 sort() 是可以通过归纳证明算法能够正确将数组排序:如果它能将两个子数组排序,它就能通过归并两个子数组将整个数组排序。

2.4.3 自底向上的归并排序

自底向上的归并排序:递归实现的归并排序都是分治思想的经典应用,自底向上的思路是先归并微小数组,再成对的归并得到的子数组,直到将所有数组归并到一起。从最小单元开始两两归并,相比标准递归方法所需的代码量会少一些。

2.4.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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Merge extends SortExample {
public static void main(String[] args){
Integer[] a = RandomUtil.getRandomIndex(10000);
Stopwatch stopwatch = new Stopwatch();
sort(a);
System.out.println(stopwatch.elapseTime());
show(a);
}

/**
* 原地归并的抽象方法
*/
public static void merge(Comparable[] a, int lo, int mid, int hi){
//将a[lo,mid]与a[mid+1,hi]归并,两个数组是有序的
int i = lo,j = mid+1;
//先将所有元素复制到aux[]中,再归并到a[]中
for(int k = lo;k <= hi;k++)
aux[k] = a[k];
//用i,j指针分别游离于两数组
for(int k = lo;k <= hi;k++){
if(i > mid) a[k] = aux[j++]; //左边下标已结束
else if(j > hi) a[k] = aux[i++];//右边下标已结束
else if(less(aux[j],aux[i])) a[k] = aux[j++];//两数组的指针比较当前大小,前者较小
else a[k] = aux[i++];
}
}

/**
* 自顶向下的归并排序
*/
private static Comparable[] aux; //归并所需的辅助数组

public static void sort(Comparable[] a){
aux = new Comparable[a.length];//一次性分配空间
sort(a,0,a.length-1);
}

//将数组a排序,递归排序,sort的作用为以正确的顺序调用merge方法
private static void sort(Comparable[] a,int lo,int hi){
if(hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a,lo,mid); // 将左半边排序
sort(a,mid+1,hi); // 将右半边排序
merge(a,lo,mid,hi); // 归并结果
}

/**
* 自底向上的归并排序
*/
public static void sortBottomUp(Comparable[] a){
// 进行lgN次两两归并
int N = a.length;
aux = new Comparable[N];
for(int sz = 1; sz < N ;sz = sz + sz) //sz-子数组大小
for(int lo = 0; lo < N-sz;lo+=sz+sz) //子数组索引
merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
}
}

2.4.5 运行轨迹

(1)原地归并的抽象方法

原地归并,先将所有元素复制到 aux[] ,然后再归并到 a[] 。方法在归并时进行了4个条件判断:左半边用尽(取右半边的元素)、右半边用尽(取左半边的元素)、右半边的当前元素小于左半边的当前元素(取右半边的元素)以及右半边的当前元素大于等于左半边的当前元素(取左半边的元素)。如下图,将两个有序子数组合并为最终有序数组。

(2)自顶向下的归并排序

自顶向下归并排序,对数组 a[lo...hi] 进行排序,先分为 a[lo...mid]a[mid+1...hi] 两部分,分别通过递归调用将它们分别排序(如图递归到最小数组-两个元素),最后将有序的子数组归并为最终结果。

自顶向下归并排序的递归调用轨迹如下图,要排序 a[0...15] ,递归调用 a[0...7] ,进一步递归调用 a[0...3] 以及到 a[0...1] ,将 a[0]a[1] 排序后归并,再之后是 a[2]a[3] ,之后是 a[0...1]a[2...3]sort() 方法其实就是按顺序调用 merge() 方法。

(3)自底向上的归并排序

自底向上的归并排序会多次遍历整个数组,根据子数组大小进行两两归并。子数组的大小sz的初始值为1,每次加倍。最后一个子数组的大小只有在数组大小是sz的偶数倍的时候才会等于sz(否则会小于sz)。

2.4.6 运行时间

(1)自顶向下的归并排序

对于长度为N的任意数组,自顶向下的归并排序需要 1/2NlgNNlgN 次比较,并且最多需要访问数组 6NlgN

归并排序所需时间与 NlgN 成正比,这相比前几个排序要快很多(指数级),只需要比遍历整个数组多个对数因子的时间就可以将一个庞大的数组排序。

如下列树状图所示,每个节点表示一个 sort() 方法通过 merge() 方法归并而成的子数组。这棵树有n层,对于0到n-1之间的任意k,自顶向下的第k层有 2^K^ 个子数组,每个数组的长度为 2^(n-k)^ ,归并最多需要 2^(n-k)^ 次比较。因此每层的比较次数为 2^K^ x 2^(n-k)^ = 2^n^ ,n层总共为 n2^n^ = NlgN 。

(2)自底向上的归并排序

对于长度为N的任意数组,自底向上的归并排序需要 1/2NlgNNlgN 次比较,最多访问数组 6NlgN

当数组长度为2的幂时,自顶向下和自底向上的归并排序的比较和数组访问次数刚好相等,只是顺序不同。其他时候则不同。

自底向上的归并排序比较适合链表组织的数据,从底层开始重新组织链接即可将链表原地排序(不需要创建新的链表结点)。

2.4.7 额外内存空间

需要额外的内存空间,辅助数组所使用的额外空间和N的大小成正比。

2.4.8 优化

(1)小规模数组采用插入排序

递归会使小规模问题中方法的调用过于频繁,插入或选择排序比较简单,很可能在小数组上比归并排序更快,如长度小于15时采用插入排序,一般可以将运行时间缩短10%~15%。

(2)判断数组是否已有序

可以添加一个判断,如果 a[mid] 小于等于 a[mid+1] ,可以认为数组已经是有序的并跳过 merge() 方法。此改动不影响排序的递归调用,但可以使任意有序的子数组的算法运行时间变为线性的。

(3)不将元素复制到辅助数组

节省将数组元素复制到用于归并的辅助数组所用的时间,为了实现这一目标,需要调用两种排序方法:一种是将数据从输入数组排序到辅助数组,一种将数据从辅助数组排序到输入数组。这一方法需要在递归调用的每个层次交换输入数组和辅助数组的角色。

2.4.9 特点

  • 归并排序所需时间与 NlgN 成正比,远远比前几种排序方法要快。
  • 数组规模较小时使用插入排序可能会比归并排序更快。
  • 自底向上的归并排序比较适合链表组织的数据。
  • 需要额外的内存空间,辅助数组所使用的额外空间和N的大小成正比。
  • 归并排序是一种渐进最优的基于比较排序的算法。
  • 归并排序的空间复杂度不是最优的,实践中不一定会遇到最坏情况,除了比较一些如访问数据的操作可能也会很重要,不进行比较也可以将数据排序。

2.4.10 计算排序算法的复杂度

第一步,建立一个计算模型。排序是基于比较的算法,此类算法在两次比较之间可能会进行任意规模的计算,但只能通过主键之间的比较得到关于某个主键的信息。

设计排序算法时有其复杂度的上限,最优算法的定义也并非只有一种标准。

命题:没有任何基于比较的算法能够保证使用少于 lg(N!) ~ NlgN 次比较将长度为N的数组排序

证明:二叉树来表示比较,叶子结点的数量介于[N!,2^H],H为最坏情况比较次数,根据斯特灵公式对阶乘函数的近似可得lgN!~NlgN,过程暂略。

命题:归并排序是一种渐进最优的基于比较排序的算法

证明:这句话的意思是:归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是 ~ NlgN

准确的上界为软件工程师保证性能提供了空间,平方级别的排序性能低于线性排序;准确的下界帮助我们节省时间,避免因为不可能的性能改进而投入资源。


2.5 快速排序

快速排序,可能是被应用最广泛的排序算法,因为其实现简单、适用各种输入数据且效率比其他排序算法都快的多,甚至还是原地排序。

快速排序是根据切分元素切分为两个子数组,一个子数组内元素都大于切分元素,一个子数组内元素都小于切分元素,递归直到整个数组排序。如下图所示。

2.5.1 优缺点

  • 原地排序,只要一个很小的辅助栈。
  • 快速排序内循环比大部分排序要短小,因此速度较快。
  • 将长度为N的数组排序时间所需和 NlgN 成正比。
  • 需要小心避免性能低劣,比较容易被错误使用。

2.5.2 快速排序和归并排序的区别

  • 快速排序是一种分治的排序算法(归并也是),将数组分为两个子数组,子数组独立的排序。
  • 快排和归并排序是互补的:归并排序是将数组分为两个子数组分别排序将有序的子数组归并从而将整个数组排序;快速排序是将两个子数组顺序有序当子数组内元素有序则数组自然有序
  • 快速排序是将两个子数组顺序有序,当子数组内元素有序则数组自然有序。
  • 归并排序递归调用发生在处理整个数组之前快速排序递归调用发生在处理整个数组之后
  • 归并排序的切分位置为中间,快速排序切分位置取决于数组的内容
  • 快排切分位置取决于输入数据,因为取数组a[lo]作为切分元素,根据归纳法来判断,快速排序递归过程能正确的将整个数组排序,有序的左数组右数组内元素都是有序的则整个数组一定有序。

2.5.3 代码

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
public class Quick {
public static void sort(Comparable[] a){
//消除对输入的依赖,需要在这里把元素随机分布一下
StdRandom.shuffle(a);
sort(a,0,a.length-1);
}

/**
* 递归排序
*/
public static void sort(Comparable[] a,int lo,int hi){
//当左右游标相等,表示已对最小数组排序,结束递归
if(hi <= lo) return;
//切分
int j = partition(a,lo,hi);
//将左半部分排序
sort(a,lo,j-1);
//将右半部分排序
sort(a,j+1,hi);
}

/**
* 切分数组
*/
private static int partition(Comparable[] a,int lo,int hi){
//左右扫描指针
int i = lo,j = hi + 1;
//切分元素
Comparable v = a[lo];
//扫描左右,检查扫描是否结束并交换元素,遍历结束后数组被切分为两部分,一边小于切分元素,一边大于切分元素
while(true){
//循环遍历直到找到大于v元素或游标到底
while(less(a[++i],v))
if(i == hi) break;
//循环遍历直到找到小于v元素或游标到头
while(less(v,a[--j]))
if(j == lo) break;
//若游标交叉则表示以遍历所有元素,结束
if(i >= j) break;
//交换两边元素
exch(a,i,j);
}
//将v=a[j]放入正确位置
exch(a,lo,j);
//a[lo...j-1] <= a[j] <= a[j+1...hi] 达成
return j;
}
}

2.5.4 排序轨迹

递归调用排序子数组 a[lo...hi] ,先用 partition() 方法将 a[j] 放到一个合适位置,然后再用递归调用将其他位置的元素排序。

归纳法证明快排正确性:若左子数组和右子数组都是有序的,那么左子数组、切分元素和右子数组组成的结果数组也一定有序。

快速排序的重点是切分方法,一般策略是先随意的选取 a[lo] 作为切分元素,然后从数组的左端开始向右端扫描知道找到一个大于等于它的元素,再从数组的右端开始向左扫描直到找到一个小于等于它的元素。然后交换两者的位置,如此遍历一轮可以保证左侧元素都小于切分元素、右侧元素都大于切分元素。当两个指针相遇时,只须将切分元素 a[lo] 和左子数组最右侧的元素 a[j] 交换并返回 j 即可,过程如下图所示。

切分方法轨迹如下图所示。

2.5.5 可能导致实现错误和性能下降的细节

  1. 原地切分:我们用数组来辅助切分的话这当然是容易实现的,但这会增加复制过程的开销,有些经验较差的新手甚至可能会把空数组创建在递归过程,这会大大降低排序速度。
  2. 不要越界:如果切分元素可能是最小或最大元素,就要小心不要将扫描指针跑出数组边界,在切分方法中可以检测来避免。
  3. 终止循环:循环结束需要额外小心,常见的错误是没有考虑到数组中可能包含和切分元素值相同的其他元素。
  4. 切分元素有重复如何处理:左侧扫描在遇到大于等于即停下,右侧小于等于时停下,虽然会进行等值交换,但会避免一些情况下运行时间变为平方级别。
  5. 终止递归:快排常见的错误是忘记把切分元素放回正确的位置,导致切分元素一直是子数组的最大或最小元素,导致无限的递归循环。

2.5.6 运行时间

快速排序切分方法的内循环通过一个递增的索引将数组元素和一个固定值来进行比较,这是最短的内循环了,如归并排序和希尔排序它们的内循环会移动数据。

快速排序比较次数很少,其排序效率依赖于切分数组的效果,最好就是每次都对半切分数组,这种情况下比较次数满足分支递归的 CN = 2C(N/2) + N 公式,其中 2C(N/2) 表示将两个子数组排序的成本,N 表示用切分元素和所有数组元素进行比较的成本,这个公式的解为 CN ~ NlgN

命题:将长度为N的无重复元素数组排序,快速排序平均需要 ~ 2NlnN 次比较,以及 1/6 的交换

证明:CN 为将N个不同元素排序平均所需的比较次数。很明显 C0 = C1 = 0,对于 N > 1 ,由递归程序可以得到以下归纳关系:

​ CN = N + 1 + (C0 + C1 + … + C(N-2) + C(N-1)) / N + (C(N-1) + C(N-2) + … + C0) / N

第一项是切分的成本(总是N+1),第二项是将左子数组排序的平均成本,第三项是将右子数组(长度和左子数组相同)排序的平均成本。将等式左右两边乘以N并整理各项得到:

​ NCN = N (N + 1) + 2(C0 + C1 + … + C(N-2) + C(N-1))

将该等式减去 N - 1 时的相同等式可得:

​ NCN - (N - 1)C(N - 1) = 2N + 2C(N - 1)

整理等式并将两边除以 N(N + 1) 可得:

​ CN / (N + 1) = C(N - 1) / N + 2 / (N + 1)

归纳法推导可得:

​ CN ~ 2(N + 1)(1/3 + 1/4 + … + 1 / (N + 1))

括号内的量是曲线 2 / x 下从3到N的离散近似面积加一,积分得到 CN ~ 2NlnN 。注意 2NlnN1.39NlgN ,也就是说平均比较次数只比最好情况多39%。

命题:快速排序最多需要 N^2/2 次比较,但随机打乱数组能够预防这种情况。

证明:在每次切分后两个子数组之一总是空的情况下,比较次数为:

​ N + (N - 1) + … + (N - 2) + 2 + 1 = (N + 1) N / 2

这说明了算法所需时间为平方级别,所需空间是线性的,而这对于大数组来说是不可接受的。比较次数的标准差为0.65N,因此随着N的增大,运行时间会趋于平均数,且不可能与平均数偏差太大。

2.5.7 改进快速排序算法

基于以下两点原因,可以发现快速排序在使用时的一些改进空间:

  1. 小数组,快速排序比插入排序慢。
  2. 因为递归,快速排序的 sort() 方法在小数组中也会调用自己。
(1)根据数组大小切换到插入排序

简单的写法是把 sort() 中的

1
if(hi <= lo) return;

修改为

1
2
3
4
if(hi <= lo + M) {
Insertion.sort(a,lo,hi);
return;
}

非常机智的改法,指定参数M,只要排序数组大小符合就转换为插入排序,一般认为M在 515 很合适。

(2)三取样切分

该方法是使用子数组的一小部分元素的中位数来切分数组,这样得到的切分会更好。虽然多了计算中位数的开销,根据统计取样大小为 3 时并用大小居中的元素切分效果是最好的。我们可以将取样元素放在数组末尾作为哨兵代替切分方法的数组边界测试。

(3)熵最优排序

当数组内有大量的重复元素时,快速排序有很大的改进空间,简单的想法就是将数组切分为三部分,分别对应小于等于大于切分元素的数组元素。但这种切分实现起来会相比二分法更复杂。

E. W. Dijkstra的荷兰国旗问题,就是同样的问题:现有红白蓝三种不同颜色的小球,乱序排列在一起,请重新排列这些小球,使得红白蓝三色的同颜色的球在一起。

2.5.8 三向切分法的快速排序

Dijkstra的解法如三向切分的快速排序算法代码,从左到右遍历数组一次,维护一个指针 lt 使得 a[lo...lt-1] 中的元素都小于v,一个指针 gt 使得 a[gt+1...hi] 中的元素都大于v,一个指针 i 使得 a[lt..i-1] 元素都等于va[i...gt] 中的元素还未确定,如下图所示。

一开始i和lo相等,通过 Comparable 接口(而非 less() )对 a[i] 进行三向比较来直接处理以下情况:

  • a[i] 小于v,将 a[lt]a[i] 交换,将lt和i加一;

  • a[i] 大于v,将 a[gt]a[i] 交换,将gt减一;

  • a[i] 等于v,将i加一。

这些操作都会保证数组元素不变且缩小 gt-i 的值(这样循环才会结束)。另外,除非和切分元素相等,其他元素都会被交换。

20世纪70年代,快排刚发布不久这段代码就出现了,可它并没有流行开,因为在数组重复元素不多的普遍情况下,它比标准的二分法多使用了很多次交换。90年代时,J. Bently和D. Mcilory找到了一个聪明的方法解决了此问题,使得三向切分的快速排序比归并排序和其他排序方法在包括重复元素很多的实际应用中更快。

但我们证明过归并排序是最优的,所以快排是如何突破了归并排序的下界?对于含有以任意概率分布的重复元素的输入,归并排序无法保证最佳性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void sort(Comparable[] a){
sort(a,0,a.length-1);
}

private static void sort(Comparable[] a,int lo,int hi){
if(hi <= lo) return;
int lt = lo,i = lo + 1,gt = hi;
Comparable v = a[lo];
while(i <= gt){
//通过与切分元素比较
int cmp = a[i].compareTo(v);
if(cmp < 0) exch(a,lt++,i++);
else if(cmp > 0) exch(a,i,gt--);
else i++;
}
//a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
sort(a,lo,lt-1);
sort(a,gt+1,hi);
}

这段排序代码的切分能够将和切分元素相等的元素归位,这样它们就不会被包含在递归调用处理的子数组之中了。对于存在大量重复元素的数组,这种方法比标准的快速排序的效率高得多,三向分切的快速排序的可视轨迹如下图所示。

对于随机数组,归并排序的时间复杂度是线性对数的,而三向切分的快速排序则是线性的。如上图,可推测主键值数量的N倍是运行时间的一个保守上界。对于标准的快速排序,随着数组规模的增大,其运行时间会趋于平均运行时间,大幅偏离的情况非常罕见,因此可以肯定三向切分的快速排序的运行时间和输入的信息量的N倍成正比的。对于包含大量重复元素的数组,它将排序时间从线性对数级降低到线性级别

2.5.9 特点

  • 使用广泛,排序性能非常高效。
  • 快速排序比归并排序比较次数会多一些,但移动数据次数要少,最终也会比归并排序快。
  • 容易因一些错误导致性能大幅下降。
  • 潜在缺点是切分不平衡时排序性能可能会极为低效
  • 三向切分的快速排序是包含大量重复元素的数组排序情况的最佳选择。

2.6 优先队列

2.6.1 概述

许多情况下都需要处理有序的元素,但不一定要求所有元素都有序,或是一次就要全部排序。比如一些需求要收集一堆元素后处理当前最大元素,然后再收集一部分元素,再处理此时最大元素(如OS为应用分配优先级)。

在这种情况下,需要一种数据结构能够支持两种操作:删除最大元素插入元素。这样的数据结构叫优先队列,优先队列类似于队列(删除最老的元素)以及栈(删除最新的元素)。二叉堆是一种实现优先队列的经典方法,优先队列可以用来实现排序算法:插入一列元素,一个一个的删掉最小元素。堆排序就是基于堆的优先队列的一种实现,当然优先队列也会用来构造图搜索算法等。

优先队列:支持两种操作(删除最大元素和插入元素)的一种抽象数据类型

2.6.2 API

1
public class MaxPQ<Key extends Comparable<Key>>
方法 描述
MaxPQ() 创建一个优先队列
MaxPQ(int max) 创建一个初始容量为max的优先队列
MaxPQ(Key[] a) 用a[]中的元素创建一个优先队列
void Insert(Key v) 向优先队列中插入一个元素
Key max() 返回最大元素
Key delMax() 删除并返回最大元素
boolean isEmpty() 返回队列是否为空
int size() 返回优先队列中的元素个数

2.6.3 调用示例

考虑一个问题:输入N个字符串,每个字符串都对映着一个整数,从中超出最大(或最小)的M个整数(及其关联的字符串)

解决这一问题,我们首先会想到使用排序算法,但如果加上一个前提:输入很大甚至可能是无限的,那么普通的排序算法就派不上用场了。另外一种方法是将每个新的输入和已知的M个最大元素比较,但除非M值较小,否则这种比较的代价很大。此处我们可以利用优先队列,只有实现了高效的 insert()delMin() 就可以解决这个问题。

从N个输入中找到最大的M个元素所需成本:

算法 时间 空间
排序算法 NlogN N
初级实现的优先队列 NM M
基于堆实现的优先队列 NlogM M

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class TopM {
public static void main(String[] args){
// 打印输入流中最大的M行
int M = Integer.parseInt(args[0]);
MinPQ<Transaction> pq = new MinPQ<Transaction>(M+1);
while(StdIn.hasNextLine()){
// 为下一行输入创建一个元素并放入优先队列中
pq.insert(new Transaction(StdIn.readLine()));
if(pq.size() > M){
pq.delMin(); // 如果优先队列中存在M+1个元素则删除其中最小的元素
}
// 最大的M个元素都在优先队列中
Stack<Transaction> stack = new Stack<Transaction>();
while(!pq.isEmpty()) stack.push(pq.delMin());
for(Transaction t : stack) StdOut.println(t);
}
}
}

2.6.4 初级实现

实现优先队列的几种方式:

  1. 数组实现(无序):利用栈(先进后出)来实现,插入元素就是入栈,内部需要类似选择排序的内循环的代码,将最大元素和边界元素交换并删除它,删除就是出栈,等同于插入排序
  2. 数组实现(有序):在入栈时添加操作,让较大元素向右移动,保证数组总是有序的,最大的元素总是在边界,删除就完全和出栈一样了。
  3. 链表表示法:基于链表的下压栈,使用有序或无序序列就是积极和惰性方法之分,无序即只在必要的时候再选择行动,有序则是尽量未雨绸缪以保证后续操作更加高效。基于栈和队列这些初级实现来说,两个操作总会在最坏情况下需要线性时间来完成,但**基于堆可以把时间从 N 改善到 logN **。
  4. 数组(堆)实现:数组实现的完全二叉树可以高效的实现优先队列,能够实现指数级的插入元素和删除最大元素的操作,基于堆的优先队列即堆排序
数据结构 插入元素 删除最大元素
有序数组 N 1
无序数组 1 N
logN logN
理想情况 1 1

2.6.5 堆的定义

二叉堆能够很好的实现优先队列的基本操作。在二叉堆数组中,每个元素都要保证大于等于另两个特定位置的元素。

当一棵二叉树的每个结点都大于等于它的两个子结点时,它被称为堆有序

根结点是堆有序的二叉树中的最大结点

二叉堆表示法

如果用指针来表示堆有序的二叉树,那么每个元素都需要三个指针来找到其上下结点。但如图所示,使用完全二叉树表达会变得简单,只须定义一个根结点,一层一层由上至下由左至右,从每个结点下方连接两个更小的结点,直至N个结点连接完毕。完全二叉树只须用数组而不用指针就可以表示,方法就是将结点按层级顺序放入数组(不使用数组第一个位置),根结点在1,第二层在2和3,第三层在4、5、6和7,以此类推。

在一个堆中,位置 K 结点的父结点位置为 k/2 ,子结点位置分别为 2k2k+1 ,所以在不使用指针时可以通过计算索引的方法在树上移动。

一棵大小为N的完全二叉树的高度为 lgN

2.6.6 堆的算法

用长度为 N+1 的私有数组 pq[] 来表示一个大小为N的堆,弃用 pq[0] ,堆元素放于1到N中。堆的操作首先需要打破堆的状态,然后再遍历堆按要求将堆的状态恢复,这个过程叫做堆的有序化

有序化过程的问题某个结点优先级上升,需要由下至上的恢复堆的顺序某个结点优先级下降,需要由上至下恢复堆的顺序

上浮和下沉
  • 由下至上的堆有序化(上浮):将比父结点更大的结点和父结点互换,持续这一过程直到遇到比自己大的父结点,只要知道位置 k 的父结点为 k/2 这个过程实现十分容易。
  • 由上至下的堆有序化(下浮):将父结点和子结点中较大者交换位置来恢复堆有序,交换后可能仍需要继续往下交换,直到其子结点都更小或到了底部。

可以将这两种过程看作严密的黑社会组织,每个子结点表示一个下属,swim() 过程即一位强力新人加入组织,逐级提升,直到有一个比他强力的领导,而 sink() 过程为某级领导退休被外来者替代,该外来者需要被强力的下属替换,直到没有能力比其强的下属为止。

上浮和下沉操作过程如下图:

上浮和下沉操作的应用:

  • 插入元素:将新元素加到数组末尾,增加堆的大小,并让新元素上浮到合适位置。
  • 删除最大元素:从数组顶端删去最大的元素并将数组的最后一个元素放到顶端,减小堆的大小,并让此元素下沉到合适位置。

基于堆的优先队列实现代码

基于堆的二叉树实现优先队列的代码如下:

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
public class MaxPQ<T extends Comparable<T>> {
private T[] pq; // 基于堆的完全二叉树
private int N = 0; // 存储于pq[1..N]中,pq[0]没有使用

public MaxPQ(int maxN){
pq = (T[]) new Comparable[maxN+1];
}

public boolean isEmpty(){
return N == 0;
}

public int size(){
return N;
}

public void insert(T t){
pq[++N] = t; // 新增结点
swim(N); // 由下至上恢复堆的有序性
}

public T delMax(){
T max = pq[1]; // 从根节点得到最大元素
exch(1, N--); // 将其和最后一个结点交换
pq[N+1] = null; // 防止对象游离
sink(1); // 由上至下恢复堆的有序性
return max;
}

// 堆的比较方法
private boolean less(int i, int j){
return pq[i].compareTo(pq[j]) < 0;
}

// 堆的交换方法
private void exch(int i, int j){
T t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}

// 上浮
private void swim(int k){
// 循环判断条件,k>1,父结点的值比当前小
while (k > 1 && less(k/2,k)){
// 交换当前结点和父结点的值,以及当前游标所指下标
exch(k/2,k);
k = k/2;
}
}

// 下沉
private void sink(int k){
// 循环判断条件,当前游标所指有子结点存在
while (2*k <= N){
int j = 2*k;
// 当子结点不是最后结点,且子结点小于右子结点,指较大的那个子结点
if(j < N && less(j,j+1))
j++;
// 如果当前结点比子结点大就跳出循环
if(!less(k,j))
break;
// 交换,更新游标
exch(k,j);
k = j;
}
}
}

命题:对于一个含 N 个元素的基于堆的优先队列,插入元素操作只需不超过 lgN+1 次比较,删除最大元素只需不超过 2lgN 次比较

证明:两种操作都需要在根结点和堆底之间移动元素,路径长度不超过 lgN 。对于路径上的每个结点,删除最大元素操作需要两次比较(除了堆底元素),一次用来找出较大的子结点,一次用来确定该子结点是否需要上浮。

此性能突破了使用有序或无序数组实现的优先队列总需线性时间来完成其中一种操作,基于堆的实现保证了对数时间内完成。

多叉堆

基于用数组表示的完全三叉树构造堆并修改相应代码并不困难,对于数组1至N个元素,位置 k 的结点大于等于位于 3K-13k3k+1 的结点,小于等于位于 (k+1)/3 的结点。甚至对于任意D叉树改动都不困难。

2.6.7 基于堆的索引优先队列

很多应用中,已进入优先队列的元素也需要被外部引用,一个简单的实现方法是为元素增加索引

基于堆的索引优先队列(IndexMinPQ)

1
public class IndexMinPQ<Item extends Comparable<Item>>
方法 描述
IndexMinPQ(int maxN) 创建一个最大容量为maxN的优先队列,索引的取值范围为0至maxN-1
void insert(int k, Item item) 插入一个元素,将它和索引k相关联
void change(int k, Item item) 将索引为k的元素设为item
boolean contains(int k) 是否存在索引为k的元素
void delete(int k) 删去索引k及其相关联的元素
Item min() 返回最小元素
int minIndex() 返回最小元素的索引
int delMin() 删除最小元素并返回它的索引
boolean isEmpty() 优先队列是否为空
int size() 优先队列中的元素数量

IndexMinPQ可以快速访问数组的一个特定子集中的最小元素(指所有被插入的元素),在一个大小为N的索引优先队列中,插入元素,改变优先级,删除,删除最小元素操作所需的比较次数和logN成正比

1

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public class IndexMinPQ<T extends Comparable<T>> {
private int N; //PQ中的元素数量
private int[] pq; //索引二叉堆,由1开始
private int[] qp; //逆序,qp[pq[i]] = pq[qp[i]] = i
private T[] keys; //有优先级之分的元素
public IndexMinPQ(int maxN){
keys = (T[]) new Comparable[maxN + 1];
pq = new int[maxN + 1];
qp = new int[maxN + 1];
for (int i = 0;i <= maxN; i++)
qp[i] = -1;
}

public boolean isEmpty(){
return N == 0;
}

public boolean comtains(int k){
return qp[k] != -1;
}

public int size(){
return N;
}

public void insert(int k,T t){
N++;
qp[k] = N;
pq[N] = k;
keys[k] = t;
swim(N);
}

public T min(){
return keys[pq[1]];
}

public int delMin(){
int indexOfMin = pq[1];
exch(1,N--);
sink(1);
keys[pq[N+1]] = null;
qp[pq[N+1]] = -1;
return indexOfMin;
}

public int minIndex(){
return pq[1];
}

public void change(int k,T t){
keys[k] = t;
swim(qp[k]);
sink(qp[k]);
}

public void delete(int k){
int index = qp[k];
exch(index,N--);
swim(index);
sink(index);
keys[k] = null;
qp[k] = -1;
}


private boolean less(int i, int j){
return keys[i].compareTo(keys[j]) < 0;
}

private void exch(int i, int j){
T t = keys[i];
keys[i] = keys[j];
keys[j] = t;
}

private void swim(int k){
while (k > 1 && less(k/2,k)){//循环判断条件,k>1,父结点的值比当前小
//交换当前结点和父结点的值,以及当前游标所指下标
exch(k/2,k);
k = k/2;
}
}

private void sink(int k){
while (2*k <= N){//循环判断条件,当前游标所指有子结点存在
int j = 2*k;
//当子结点不是最后结点,且子结点小于右子结点,指较大的那个子结点
if(j < N && less(j,j+1))
j++;
//如果当前结点比子结点大就跳出循环
if(!less(k,j))
break;
//交换,更新游标
exch(k,j);
k = j;
}
}
}

在一个大小为N的索引优先队列中,插入元素、改变优先级、删除和删除最小元素操作所需的比较次数和 logN 成正比

含有N个元素的基于堆的索引优先队列所有操作在最坏情况下的成本:

操作 比较次数的增长数量级
insert() logN
change() logN
contains() 1
delete() logN
min() 1
minIndex() 1
delMin() logN
使用案例

多向归并问题:将多个有序的输入流归并成一个有序的输出流,输入可能是各种科学仪器的输出值(按时间排序)、可能是来自音乐或电影网站的信息列表(按艺术家名字排序)、可能是商业交易(按账号或时间排序)等。

使用优先队列排序,无论输入有多长都可以全部读入并排序:

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 class Multiway {
public static void merge(In[] streams){
// 输入流数目
int N = streams.length;
// pq为优先队列
IndexMinPQ<String> pq = new IndexMinPQ<String>(N);

// 遍历所有输入流
for(int i = 0; i < N; i++){
// 当此输入流不为空,将输入流插入优先队列
if(!streams[i].isEmpty())
pq.insert(i, streams[i].readString());
}
while(!pq..isEmpty()){
// 输出最小值
StdOut.println(pq.min());
// 删除并返回最小值的索引
int i = pq.delMin();

// 循环内确保所有输入流都已处理
if(!streams[i].isEmpty())
pq.insert(i, streams[i].readString());
}
}

public static void main(String[] args){
int N = args.length;
In[] streams = new In[N];
for(int i = 0; i < N; i++){
streams[i] = new In[args[i]];
}
merge(streams);
}
}

2.7 堆排序

可通过 IndexMinPQ 将多行输入的字符串归并为一行有序的输出,所以优先队列可以变为一种排序方法,其中基于堆的优先队列等同于:堆排序

堆排序:将所有元素插入一个查找最小元素的优先队列,然后重复调用删除最小元素的操作将元素按顺序删除

对于无序数组实现的优先队列就等同于插入排序,而堆排序则是一种全新的排序方法

堆排序分为两个阶段:

  • 堆的构造阶段,将原始数组重新安排进一个堆中。
  • 下沉排序阶段,从堆中按递减顺序取出所有元素并得到排序结果。

2.7.1 堆的构造

如何使给定的N个元素构成一个堆?

一个简单的方法:从左至右遍历数组,用 上浮 swim() 保证指针左侧的所有元素已经是一棵堆有序的完全树即可,可以在与 NlogN 成正比的时间内完成。

一个高效的方法:从右至左通过下沉 sink() 函数构造子堆。数组的每个位置都已经是一个子堆的根结点,若一个结点的两个子结点都已经成堆,那么在此结点上调用sink() 函数可以将它们成堆,递归此过程直到最后在位置1调用sink。这一过程可以跳过大小为1的子堆。在堆的构造阶段,最大元素是位于数组的开头,而不是结尾。

命题:用下沉操作由N个元素构造堆只须少于2N次比较以及少于N次交换

2.7.2 实现代码

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
/**
* 堆排序
*/
public class Set extends SortExample {

public static Comparable[] sort(Comparable[] c){
Comparable[] a = new Comparable[c.length+1];
int N = c.length;
for (int i = 0;i < N;i++)
a[i+1] = c[i];
// for循环构造堆,sink方法将a从1到N排序
for(int k = N/2; k >= 1; k--)
sink(a,k,N);
show(a);
// while循环将最大元素a[1]和a[N]交换,并修复堆
while (N > 1){
exch(a,1,N--);
sink(a,1,N);
show(a);
}
return a;
}

private static void swim(Comparable[] a,int k){
while (k > 1 && less(k/2,k)){//循环判断条件,k>1,父结点的值比当前小
//交换当前结点和父结点的值,以及当前游标所指下标
exch(a,k/2,k);
k = k/2;
}
}

private static void sink(Comparable[] a,int k,int N){
while (2*k <= N){//循环判断条件,当前游标所指有子结点存在
int j = 2*k;
//当子结点不是最后结点,且子结点小于右子结点,指较大的那个子结点
if(j < N && less(a[j],a[j+1]))
j++;
//如果当前结点比子结点大就跳出循环
if(!less(a[k],a[j]))
break;
//交换,更新游标
exch(a,k,j);
k = j;
}
}

public static void exch(Comparable[] a,int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}

public static void main(String[] args){
// Integer[] a = RandomUtil.getRandomIndex(10000);
Comparable[] a = {'S','O','R','T','E','X','A','M','P','L','E'};
Stopwatch stopwatch = new Stopwatch();
a = sort(a);
System.out.println(stopwatch.elapseTime());
show(a);
}
}

2.7.3 排序轨迹

堆排序的轨迹如下图所示,分为两个阶段。

堆排序的主要工作都在第二阶段完成,构造阶段通过下沉操作完成堆有序,下沉排序阶段再依次将根结点与当前数组末尾元素交换,并忽略末尾元素即堆缩小(已经处于最终位置),这很像选择排序但比较次数会少的多,将此时根结点(较小元素)下沉恢复堆有序,持续此过程直到得到最终排序数组。

大多数在下沉排序期间重新插入堆的元素会被直接加入堆底,因为下沉总是会直接提升较大的子结点直至到达堆底,然后再使元素上浮到正确位置,这种改法可以使比较次数减少一半(接近于归并排序的比较次数)。但这种做法需要额外内存空间,所以只会在比较操作比较费时时采用。

2.7.4 运行时间

将N个元素排序,堆排序只需要少于 2NlgN + 2N 次比较,以及一半次数的交换

2.7.5 额外内存空间

堆排序使用空间是恒定的,所以在一些嵌入式系统中很流行,但其无法利用缓存导致很多应用很少使用它。数组元素很少和相邻元素比较,因此缓存未命中的次数要远远高于其他算法。但另一方面,用堆实现的优先队列在如今越来越重要,因为其能在插入元素删除最大元素这两个基本操作混合的动态场景中保证对数级别的运行时间。

2.7.6 特点

  • 唯一能够同时最优地利用空间和时间的方法,最坏情况下也能保证 ~ 2NlgN 次比较和恒定的额外空间。
  • 排序过程分两个阶段。
  • 无法有效利用缓存。
  • 能在插入元素删除最大元素这两个基本操作混合的动态场景中保证对数级别的运行时间。

2.8 补充:冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法,算法思路:遍历无序数组,进行两两比较,根据大小交换位置,直到把当前最大(小)元素交换到队尾,持续这一过程,直到所有元素都已排序。

算法流程如下图所示:

代码实现如下:

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
public class BubbleSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

for (int i = 1; i < arr.length; i++) {
// 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
boolean flag = true;

for (int j = 0; j < arr.length - i; j++) {
// 比较两个元素大小,若前大于后则交换
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;

flag = false;
}
}

if (flag) {
break;
}
}
return arr;
}
}

时间复杂度:基本语句即比较操作 arr[j] > arr[j + 1] ,其运行次数为 (n - 1) + (n - 2) + … + 2 + 1 = n (n - 1) / 2 = n^2^ / 2 。所以时间复杂度为 O(n^2^) 。


第三节 归纳总结

3.1 注意事项

  1. 不可变的键:尽量使用不可变数据类型来作键,如String、Integer、Double、File。
  2. 廉价交换:若元素大而键小,可以使用引用排序,避免元素的交换操作。
  3. 多键数组:应用场景中,可能元素多种属性都可以当作排序的键,Comparator 接口可以定义多种比较器,甚至定义多种排序方法。

3.2 排序算法的比较

测试用例:1万个随机整数[0,9999]。

算法 100次运行平均所用时间
选择排序 0.0718
插入排序 0.1156
希尔排序 0.0025
快速排序 0.0014
三向切分的快速排序 0.0021
归并排序 0.0031
堆排序 0.0020

取随机数耗时比较大,测试的时候注意把取随机数的时间过滤。

稳定性指排序算法能够保留数组中重复元素的相对位置,这种性质对于按不同维度依次排序的需求很重要(如先按时间排序,再按某一属性排序,相同属性的元素仍能按时间排序),当然也有办法使所有算法都强制稳定,取决于是否有必要花费这样的开销。

算法 是否稳定 原地排序 时间复杂度 空间复杂度 备注
冒泡排序 O(n^2^) 1
选择排序 O(n^2^) 1
插入排序 O(n) ~ O(n^2^) 1 取决于输入元素的排列情况
希尔排序 O(nlogn) ~ O(n^6/5^) 1
快速排序 O(nlogn) ~ O(n^2^) lgn 运行效率由概率提供保证
三向快速排序 O(n) ~ O(nlogn) lgn 运行效率由概率保证,同时也取决于输入元素的分布情况
归并排序 O(nlogn) n
堆排序 O(nlogn) 1

快速排序是最快的通用排序算法,大多数实际情况快排是最佳选择,但如看重稳定性又不在意空间的场景,归并排序是更好的选择

Java 的 Arrays.sort()对原始数据类型进行三向快速排序对引用类型使用归并排序,也暗示了用空间来换取稳定性


参考博客和文章书籍等:

《算法 第4版》

冒泡排序-菜鸟教程

因博客主等未标明不可引用,若部分内容涉及侵权请及时告知,我会尽快修改和删除相关内容