排序算法-希尔排序(Shell Sort)_如何根据关键字序列进行shell排序

希尔排序法介绍

希尔排序法(Shell Sort)是D.L.Shell于1959年提出的一种排序算法，是直接插入排序法的更高效的改进版。在这之前的排序算法如冒泡排序、简单选择排序、直接插入排序等算法的的时间复杂度都为$O(n^2)$，而希尔排序突破了这一时间复杂度。
【原理】
直接插入排序算法比冒泡排序和简单选择排序性能都要高，尤其在序列基本有序并且记录数相对较少的情况，只需要简单的几个插入动作就能完成排序。

希尔排序的思路就是在插入排序算法的基础上，创造插入排序算法的有利条件，将序列按照某个增量分成多个子序列进行插入排序，使整个序列变为基本有序，并且由于按照增量分了子序列，所以每个子序列的记录数变少了，增量和子序列长度成反比，增量从小于n的某个值每次递减，子序列随增量变小而变长。直到增量变为1，使其所有记录为一个整体序列然后进行一次插入排序为止。

什么才叫基本有序呢？比如{2,1,4,3,5,6,8,7,9}可以说是基本有序，小的数字基本在序列的前部，不大不小的在中部，大的数字在后部。 {8,7,6,3,9,2,4,5,1}这样的序列就不是基本有序，因为1在序列的最后，9在中间，8在第一位，所以谈不上是基本有序的。

【例子】
下面看个对关键字序列{8,7,1,9,3,6,4,5,2}进行希尔排序的步骤。

希尔排序法算法

public static void shellSort(Integer[] arr) {
    int increment = arr.length;
    do {
        increment = increment / 3 + 1;
        for (int i = increment; i < arr.length; i++) {
            if (arr[i-increment] > arr[i]){
                int minIdx = i;
                int compIdx = minIdx-increment; //需往右边移动的关键字下标
                int minValue = arr[minIdx];
                while (compIdx >= 0 && arr[compIdx] > minValue) { //比较大小
                    arr[minIdx] = arr[compIdx]; //关键字右移
                    minIdx = compIdx;
                    compIdx = compIdx - increment;
                }
                arr[minIdx] = minValue; //插入关键字
            }
        }
    } while (increment > 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度

希尔排序的时间复杂度依赖增量序列，增量的取值至今还是个难题，大量研究表明，当增量序列为delta[k]=$2^{t-k+1}$-1(0$⩽$k$⩽$t$⩽\lfloor log2(n+1)\rfloor$) 时，可以获得不错的效率，其时间复杂度为$O(n^{3/2})$，要好于直接插入排序的$O(n^2)$。

稳定性

由于按照增量跳跃式分成了子序列插入排序，所以相同值位置可能会被替换，所以希尔排序是不稳定的。

其他排序法的比较

以下分别使用简单选择排序法、直接插入排序法和希尔排序法对10万随机关键字的排序耗时，从结果可以看出直接插入排序的执行时间比简单选择排序法快，而希尔排序法比直接插入排序法快了非常多只用了38ms。

简单选择排序执行时间:8077ms
直接插入排序执行时间:4408ms
希尔排序执行时间:38ms
1
2
3