算法

排序算法04：希尔排序

算法介绍

  从上一篇《插入排序》可以知道，当最小元素恰好在最后一个时，需要移动的次数为N-1。当一个从大到小排列的数组使用插入排序变成从小到大排列时，需要比乱序状态下耗费更多的时间。原因为插入排序是从后往前一位一位的往前交换，如果能把靠后的较小元素只交换（移动）一次就插入到靠前位置，则能有效的缩短排序时间。希尔排序就是这样一种算法。

  希尔排序通过一个序列让靠后的元素一次性移动到前面，最后使用插入排序让数组变成有序状态。

  举个例子。长度为100的数组，挑选出[1,10,20,50]这么一个序列，这个数列的含义就是每次元素移动的间隔。

  1. 让间隔50的数据相对有序（arr[0]<arr[49]<arr[99]）
  2. 让间隔20的数据相对有序（arr[0]<arr[19]<arr[39]<arr[59]<arr[79]<arr[99]）
  3. 让间隔10的数据相对有序（arr[0]<arr[9]<arr[19]<arr[29]<arr[39]……）
  4. 让间隔1的数据现对有序(步长为1实际上就是插入排序)

下图为《算法》第四版上希尔排序排序轨迹样例：

这张图是对SHELLSORTEXAMPLE字符序列排序，序列为13、4、1。

可视化效果：这里

Javascript实现

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

/**
 * Created by YiYing on 2017/4/22.
 */
(function (W) {

    function Shell(arr) {
        this.arr = arr;
    }

    /**
     * 冒泡排序算法实现
     */
    Shell.prototype.sort = function () {
        var len = this.arr.length;
        var h   = 1;
        //自动生成序列。步长序列为1、4、13、40、121、364、1093......
        while(h<parseInt(len/3)){
            h = h*3+1;
        }
        while(h>=1){
            for(var i=h;i<len;i++){
                //当h>1时，实际上是把后面的一次性移动到前面。最后h为1时实际上就是对arr进行插入排序
                for(var j=i;j>=h && this.less(j,j-h);j=j-h){
                    this.exchange(j,j-h);
                }
            }
            //每执行一次，步长依次递减，最终步长递减为1。
            h = parseInt(h/3);
        }
    };

    /**
     * 判断m是否小于n
     * @param m
     * @param n
     */
    Shell.prototype.less = function (m,n) {
        //可根据不同的数据类型设置比对规则，比如json。这里适用于数字与字符串。
        return this.arr[m]<this.arr[n];
    };

    /**
     * 交换数组中m与n的位置
     * @param m
     * @param n
     */
    Shell.prototype.exchange = function (m,n) {
        var swap    = this.arr[m];
        this.arr[m] = this.arr[n];
        this.arr[n] = swap;
    };

    /**
     * 打印排序后的数组
     */
    Shell.prototype.show = function () {
        console.log(this.arr);
    };

    /**
     * 判断是否已排序
     * @returns {boolean}
     */
    Shell.prototype.isSorted = function () {
        var len = this.arr.length;
        for(var i=1;i<len;i++){
            if(this.less(i,i-1)){
                return false;
            }
        }
        return true;
    };

    W.Shell = Shell;
})(window);

//测试代码
(function () {
    var arr = [4,5,6,0,3,5,21,7,9,0,1];
    var shell = new Shell(arr);
    console.log("排序前："+shell.isSorted());
    shell.sort();
    console.log("排序后："+shell.isSorted());
    shell.show();
})();

Java实现

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

package com.algs;

public class Shell {

	/**
	 * 希尔排序实现逻辑
	 * @param arr
	 */
	public static void sort(int[] arr){
		int len = arr.length;
		int h	= 1;
		//自动生成序列。步长序列为1、4、13、40、121、364、1093......
		while(h<len/3){
			h = 3*h+1;
		}
        while(h>=1){
        	for(int i=h;i<len;i++){
        		//当h>1时，实际上是把后面的一次性移动到前面。最后h为1时实际上就是对arr进行插入排序
        		for(int j=i;j>=h && less(arr[j],arr[j-h]);j -= h){
        			exchange(arr,j,j-h);
        		}
        	}
        	//每执行一次，步长依次递减，最终步长递减为1。
        	h = h/3;
        }
	}

	/**
	 * 比较m是否小于n
	 * @param m
	 * @param n
	 * @return
	 */
	private static boolean less(int m,int n) {
        return m < n;
    }

	/**
	 * 交换m与n的位置
	 * @param a
	 * @param m
	 * @param n
	 */
	private static void exchange(int[] a, int m, int n) {
        int swap = a[m];
        a[m] = a[n];
        a[n] = swap;
    }

	public static void show(int[] a){
		for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
	}

	public static void main(String[] args) {
		int[] arr = {4,5,6,0,3,5,21,7,9,0,1};
		Shell.sort(arr);
		Shell.show(arr);
	}
}


总结

  1. 不稳定。
  2. 原地排序。
  3. 时间复杂度为：目前无法准确评估时间复杂度。但是肯定小于平方级别，大于线性对数级别。详细可见《算法》第四版P162
  4. 空间复杂度为：常数级别。
  5. 希尔排序比插入排序、选择排序更快。且数组越大，优势越大。
  6. 对于递增序列可以随意选择，目前无法证明某个序列是最优的。

GitHub：https://github.com/AlbertKnag/algs-practice

上一篇：排序算法03：插入排序
下一篇：排序算法05：归并排序

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。