算法原理

希尔排序是把记录按表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法思路

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  2. 按增量序列个数k，对序列进行k 趟排序；
  3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度 shell-sort.jpg

代码实现

 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

class ShellSort{
    /**
     * 希尔排序
     *
     * @param array
     * @return
     */
    public static int[] shellSort(int[] array) {
            if(array.length==0){
                return array;
            }
            int len=array.length;
            int cur,gap=len/2;//计算步长
            while(gap>0){
                for (int i = gap; i < array.length; i++) {
                    cur=array[i];//当前步长元素
                    int preindex=i-gap;//相同步长对应的元素
                    while(preindex>=0 && array[preindex]>cur){//前一个元素比当前元素大时
                        array[preindex+gap]=array[preindex]; //前一个元素放到当前步长位置
                        preindex -=gap;//同步长向前遍历
                    }
                    array[preindex+gap]=cur;//插入元素
                }
                gap /=2;//计算步长
            }
        return array;
    }
    public static void main(String[] args) {
        int [] arr={8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

算法分析

最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)

参考文章：https://www.cnblogs.com/guoyaohua/p/8600214.html