算法4 初级排序算法

排序的算法的应用实在是太广泛了,作为算法的基础部分,本文将讲述几种最简单的排序算法,分别是选择排序、插入排序和希尔排序。而冒泡排序因为其实现和插入排序实在是太相似了,并不做过多的叙述。另外这里非常推荐一个网站,包含常用排序算法的动画演示:sorting-algorithms。并且我会录制该网站的gif,从左到右的4格排序动画分别表示序列的不同初始状态:随机的、基本有序的、逆序的、重复元素的。

在开始之前,我们还需要约定一些规则,因为排序算法基本都基于“比较元素大小”和“交换元素位置”这两个基本操作实现的,并且这部分代码是可以通用的。所以在后面的所有算法中我都将使用下面这一套规则并且不再重复贴出代码,它们分别是lessexch

1
2
3
4
5
6
7
8
9
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}

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

需要注意的是:less(a,b) 相当于 a < b || b > a; !less(a,b) 相当于 a >= b || b <= a

选择排序

选择排序是一种很容易理解的并且实现同样非常简单的排序算法,它循环的遍历数组并每次选出最小的元素将它放到首位。指针i面的元素都是已经排序好的,指针i右边的元素都是待排序的,直到指针移动到元素末尾表示排序结束。

1
2
3
4
5
public static void selectionSort(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length && less(a[j], a[i]); j++)
exch(a, j, i);
}

性能分析

比较次数 交换次数
N

插入排序

选择排序效率低的最主要原因是因为它每次都需遍历数组尚未排序的部分。

所以插入排序的想法是,每次只取右边尚未排序部分的第一个元素,然后插入到左边已经有序的部分中,这样能大大减少元素的比较次数。

1
2
3
4
5
public static void insertion(Comparable[] a) {
for (int i = 0; i < a.length; i++)
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}

性能分析

插入排序的性能受数组的初始状态影响非常大,最好的情况是数组有序,只需要N次比较和0次交换;最差的情况是数组逆序,需要 次比较和 次交换。而对于部分有序的数组插入排序的效率也是非常高的,它的这个特性非常有意思,希尔排序正是基于这个特性的算法。

比较次数 交换次数
平均 平均

希尔排序

对于逆序的数组,插入排序的效率是非常低的,主要是因为它只会交换相邻的元素。

希尔排序核心思想是交换不相邻的元素以对数组进行局部排序,使得数组中任意间隔为h的元素都是有序的,这样的数组称为 h有序数组 ,即一个由h个有序子数组组成的数组,当h=1时数组是全序的。

下面表格中,我们使用13、4、1这三个h对SHEELORTEXAMPLE这个字符串进行排序,而这三个数字我们成为递增序列

输入 S H E L L S O R T E X A M P L E
13-sort P H E L L S O R T E X A M S L E
4-sort L E E A M H L E P S O L T S X R
1-sort A E E E H L L L M O P R S S T X

最终使用1-sort进行排序时,相当于对一个基本有序的数组进行插入排序,速度是非常快的。

在上面例子中我们使用的递增序列是3x+1,它是比较常用的递增序列。加1是为了使得h最后可以递减到1,而不是其它数值。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void shell(Comparable[] a) {
int h = 1;
while (h < a.length / 3)
h = 3 * h + 1;

while (h >= 1) {
// 这部分其实就是插入排序,只不过指针跨度为h;
for (int i = h; i < a.length; i++)
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
exch(a, j, j - h);
h = h / 3;
}
}

性能分析

希尔排序可以说是算法4课程中唯一一个无法分析其准确性能的算法了。但是对于递增序列3x+1而言,最坏的情况下的比较次数最多为 次平方级

是否存在更好的递增序列?很多论文研究了各种不同的递增序列,但都无法证明某个序列是"最好的"。

排序算法的稳定性

排序算法的稳定性是指不打乱原本已经有序的部分。如下图所示,一个按已经时间排序的城市列表,分别使用稳定排序算法和不稳定排序算法排序后的结果:

各类排序算法的稳定性:

排序算法 是否稳定
选择排序
冒泡排序
插入排序
希尔排序
归并排序
快速排序
堆排序