Algs4笔记(三) --- 选择排序、插入排序与希尔排序

排序算法如同计算机科学中的基础设施,没有高效的排序算法,计算机将无法完成计算任务,进而完成一些有趣的事情。

辅助函数

为了更好描述排序算法,我们封装了一些辅助函数,less()方法对元素进行比较,exch()方法将元素交换位置,多数情况下,我们只会通过这两个方法操作数据。exch()方法和less()方法是排序算法都会用到的共同操作,我们如此抽象,使得代码易于理解,也增强了代码的可移植性。

1
2
3
4
5
6
7
8
9
10
11
12
public class Example {
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}

private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// ... ...
}

选择排序

选择排序(Selection sort)是一种简单直观的排序算法,首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。如此往复,直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Selection {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i+1; j < N; j++)
if (less(a[j], a[min]))
min = j;
exch(a, i, min);
}
}
// ... ...
}

选择排序简单明了,有两个鲜明特点:运行时间和输入无关;数据移动是最少的,和数组大小成线性关系。对于长度为\(N\)的数组,选择排序需要\(~N^2/2\)次比较和\(N\)次交换。

插入排序

插入排序(Insertion sort)的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

1
2
3
4
5
6
7
8
9
10
public class Insertion {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}
}
// ... ...
}

和选择排序不同的是,插入排序所需的时间取决于输入中元素的初始顺序。如果数组是接近有序的话,插入排序将可能比所介绍的这几种算法都快。对于随机排列长度为\(N\)且主键不重复的数组,平均情况下插入排序需要\(~N^2/4\)次比较以及\(~N^2/4\)次交换;最坏情况下需要\(~N^2/2\)次比较以及\(~N^2/2\)次交换;最好情况下需要\(N-1\)次比较以及\(0\)次交换。插入排序适合小规模数组,对于部分有序的数组十分高效。
我们可以通过简单的优化,大幅提高插入排序的速度,在内循环中将较大的元素都向右移动而不是总是交换,如此可使访问数组的次数减半。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Insertion {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 1; i < N; i++) {
int j = i;
Comparable temp = a[j];
for (; j > 0 && less(temp, a[j-1]); j--)
a[j] = a[j-1];
a[j] = temp;
}
}
// ... ...
}

希尔排序

希尔排序(Shell sort)是插入排序的一种更高效的改进版本,交换不相邻的元素以对数组的局部进行排序,并最终归约成插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Shell {
public static void sort(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N/3)
h = 3 * h + 1;

while ( h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
exch(a, j, j-h);
}
h = h / 3;
}
}
// ... ...
}

希尔排序比插入排序更加高效的原因在于它权衡了子数组的规模和有序性,排序开始前各子数组短,排序后各子数组部分有序,插入排序都很适合这些情况。递增序列的选择将会影响希尔排序的性能,上示的递增序列在实际应用中就非常不错。惊讶的是,即便是如今,我们对希尔排序的性能仍无法准确描述,目前最重要的结论是,它的运行时间达不到平方级别。希尔排序代码短小,解决中等规模问题的时间是可以接受的,并且是原地排序算法,因为这些特点,希尔排序很适合嵌入式开发。


参考资料