十大排序算法之希尔排序

发表于 | 分类于
字数统计: 2.6k 字 | 阅读时长 ≈ 11 分钟

本文首发于个人博客

前言

本系列排序包括十大经典排序算法。

  • 使用的语言为：Java
  • 结构为：
    定义抽象类Sort里面实现了，交换，大小比较等方法。例如交换两个值，直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort。这样我们就能专注于算法本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
	 * 返回值等于0，代表 array[i1] == array[i2]
	 * 返回值小于0，代表 array[i1] < array[i2]
	 * 返回值大于0，代表 array[i1] > array[i2]
	 */
	protected int cmp(int i1, int i2) {
		return array[i1].compareTo(array[i2]);
	}
	
	protected int cmp(T v1, T v2) {
		return v1.compareTo(v2);
	}
	
	protected void swap(int i1, int i2) {
		T tmp = array[i1];
		array[i1] = array[i2];
		array[i2] = tmp;
	}

什么是希尔排序

  • 希尔排序（Shellsort）也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

改进

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序的历史

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”

算法实现

  • 原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。 V. Pratt的书对算法进行了少量修改，可以使得性能提升至O(n log2 n)。这比最好的比较算法的O(n log n)要差一些。

  • 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

  • 假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

  • 一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。

  • 例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

1
2
3
4
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

1
2
3
4
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

1
2
3
4
5
6
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

1
2
3
4
5
6
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序（此时就是简单的插入排序了）。

算法稳定性

  • 希尔排序不是一种稳定排序算法。

是否是原地算法

  • 何为原地算法？
    • 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
    • 空间复杂度为 𝑂(1) 的都可以认为是原地算法
  • 非原地算法，称为 Not-in-place 或者 Out-of-place
  • 希尔排序属于 In-place

时空复杂度

  • 最好时间复杂度：O(n)
  • 最坏时间复杂度：O(n4/3)~O(n2)
  • 平均时间复杂度：取决于步长
  • 空间复杂度：O(1)

步长序列

  • 希尔本人给出的步长序列，最坏情况时间复杂度是O(n2)

    • 希尔给出的步长序列为1,2,4,8,16,32,64…

  • 目前已知的最好步长序列，最快情况时间复杂度为O(n4/3)，是在1986年由Robert Sedgewick提出的。

    • 1，5，19，41，109…

  • Robert Sedgewick给出的步长序列实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
	获取最优步长
	*/
	private List<Integer> sedgewickStepSequence() {
		List<Integer> stepSequence = new LinkedList<>();
		int k = 0, step = 0;
		while (true) {
			if (k % 2 == 0) {
				int pow = (int) Math.pow(2, k >> 1);
				step = 1 + 9 * (pow * pow - pow);
			} else {
				int pow1 = (int) Math.pow(2, (k - 1) >> 1);
				int pow2 = (int) Math.pow(2, (k + 1) >> 1);
				step = 1 + 8 * pow1 * pow2 - 6 * pow2;
			}
			if (step >= array.length) break;
			stepSequence.add(0, step);
			k++;
		}
		return stepSequence;
	}

代码

最简单的插入排序为基础，步长为1，2，4，8，16，32…

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
public class ShellSort <T extends Comparable<T>> extends Sort<T> {

	@Override
	protected void sort() {
		// TODO Auto-generated method stub
		List<Integer> stepSequence = sedgewickStepSequence();
		for (Integer step : stepSequence) {
			sort(step);
		}
	}
	/**
	 * 分成step列进行排序
	 */
	private void sort(int step) {
		// col : 第几列，column的简称
		for (int col = 0; col < step; col++) { // 对第col列进行排序
			// col、col+step、col+2*step、col+3*step
			for (int begin = col + step; begin < array.length; begin += step) {
				int cur = begin;
				while (cur > col && cmp(cur, cur - step) < 0) {
					swap(cur, cur - step);
					cur -= step;
				}
			}
		}
	}


	/*
	获取步长序列
	*/
	private List<Integer> shellStepSequence() {
		List<Integer> stepSequence = new ArrayList<>();
		int step = array.length;
		while ((step >>= 1) > 0) {
			stepSequence.add(step);
		}
		return stepSequence;
	}

}

优化

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void sort2(int step) {
	// col : 第几列，column的简称
	 for (int col = 0; col < step; col++) { // 对第col列进行排序
		for (int begin = step+col; begin < array.length; begin+=step) {
			int cur = begin;
			T res =array[cur];
			while (cur>col && cmp(res,array[cur-step])<0) {
				array[cur] = array[cur-step];
				cur-=step;
			}
			array[cur] = res;
		 }
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
	获取最优步长
	*/
	private List<Integer> sedgewickStepSequence() {
		List<Integer> stepSequence = new LinkedList<>();
		int k = 0, step = 0;
		while (true) {
			if (k % 2 == 0) {
				int pow = (int) Math.pow(2, k >> 1);
				step = 1 + 9 * (pow * pow - pow);
			} else {
				int pow1 = (int) Math.pow(2, (k - 1) >> 1);
				int pow2 = (int) Math.pow(2, (k + 1) >> 1);
				step = 1 + 8 * pow1 * pow2 - 6 * pow2;
			}
			if (step >= array.length) break;
			stepSequence.add(0, step);
			k++;
		}
		return stepSequence;
	}

优化过的代码为

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
package YZ.Sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ShellSort <T extends Comparable<T>> extends Sort<T> {

	@Override
	protected void sort() {
		// TODO Auto-generated method stub
		List<Integer> stepSequence = sedgewickStepSequence();
		for (Integer step : stepSequence) {
			sort2(step);
		}
	}
	/**
	 * 分成step列进行排序
	 */
	private void sort(int step) {
		// col : 第几列，column的简称
		for (int col = 0; col < step; col++) { // 对第col列进行排序
			// col、col+step、col+2*step、col+3*step
			for (int begin = col + step; begin < array.length; begin += step) {
				int cur = begin;
				while (cur > col && cmp(cur, cur - step) < 0) {
					swap(cur, cur - step);
					cur -= step;
				}
			}
		}
	}

	private void sort2(int step) {
		// col : 第几列，column的简称
	 for (int col = 0; col < step; col++) { // 对第col列进行排序
		for (int begin = step+col; begin < array.length; begin+=step) {
			int cur = begin;
			T res =array[cur];
			while (cur>col && cmp(res,array[cur-step])<0) {
				array[cur] = array[cur-step];
				cur-=step;
			}
			array[cur] = res;
		 }
		}
	}

	/*
	获取步长序列
	*/
	private List<Integer> shellStepSequence() {
		List<Integer> stepSequence = new ArrayList<>();
		int step = array.length;
		while ((step >>= 1) > 0) {
			stepSequence.add(step);
		}
		return stepSequence;
	}

	/*
	获取最优步长
	*/
	private List<Integer> sedgewickStepSequence() {
		List<Integer> stepSequence = new LinkedList<>();
		int k = 0, step = 0;
		while (true) {
			if (k % 2 == 0) {
				int pow = (int) Math.pow(2, k >> 1);
				step = 1 + 9 * (pow * pow - pow);
			} else {
				int pow1 = (int) Math.pow(2, (k - 1) >> 1);
				int pow2 = (int) Math.pow(2, (k + 1) >> 1);
				step = 1 + 8 * pow1 * pow2 - 6 * pow2;
			}
			if (step >= array.length) break;
			stepSequence.add(0, step);
			k++;
		}
		return stepSequence;
	}
}

结果

数据源：

从1到20000之间随机生成10000个数据来测试

Integer[] array = Integers.random(20000, 1, 80000);

结果如下

【MergeSort】
稳定性：true 耗时：0.011s(11ms) 比较次数：26.10万 交换次数：0

【QuickSort】
稳定性：false 耗时：0.012s(12ms) 比较次数：34.55万 交换次数：1.32万

【HeapSort】
稳定性：false 耗时：0.018s(18ms) 比较次数：51.10万 交换次数：2.00万

【ShellSort】
稳定性：false 耗时：0.02s(20ms) 比较次数：43.04万 交换次数：0

【SelectionSort】
稳定性：true 耗时：0.485s(485ms) 比较次数：2.00亿 交换次数：2.00万

【InsertionSort3】
稳定性：true 耗时：0.526s(526ms) 比较次数：25.80万 交换次数：0

【InsertionSort2】
稳定性：true 耗时：0.801s(801ms) 比较次数：9963.29万 交换次数：0

【InsertionSort1】
稳定性：true 耗时：1.281s(1281ms) 比较次数：9963.29万 交换次数：9961.29万

【BubbleSort2】
稳定性：true 耗时：2.271s(2271ms) 比较次数：2.00亿 交换次数：9961.29万

【BubbleSort】
稳定性：true 耗时：2.339s(2339ms) 比较次数：2.00亿 交换次数：9961.29万

【BubbleSort1】
稳定性：true 耗时：2.403s(2403ms) 比较次数：2.00亿 交换次数：9961.29万

可以看到希尔排序的性能还是很不错的，对比插入排序，优化的还是挺多的。

逆序对

什么是逆序对？

数组[2,4,1]中的逆序对为<2,1> 和 <4,1>

插入排序的时间复杂度和逆序对的数量成正比关系

逆序对越多，插入排序的时间复杂度越高

当逆序对的数量极少时候，插入排序的效率特别高

甚至有时候可以比O(nlogn)级别的快速排序还要快

代码地址：