十大排序算法之希尔排序

希尔排序

希尔（音同 Shell）排序，也叫缩小增量排序，它通过将原始列表分解多个子列表来改进插入排序。虽然它叫希尔排序，但和命令解析器 Shell 不是一回事，只是因为该算法是由 D.L.shell 提出的而已。

1. 算法思想

希尔排序法摒弃了直接插入排序逐一比较的方式，而是对指定距离（增量d）的元素进行比较，并不断把增量缩小至1，直到排序完成。

注意：对于增量取值的规律，可以是奇数、偶数或者质数等，并且不断将增量除以 2直至其值为1。

2. 算法步骤

（1）选取增量$d=\frac{n}{2}$。
（2）将待排序数组分为d个子序列，然后分别进行直接插入排序。
（3） 将構康取半，即$d=\frac{d}{2}=\frac{\frac{n}{2}}{2}$。
（4）重复步骤（2）和（3），直到增量d等于1。
（5）对整个待排序数组进行直接插入排序，然后完成排序。

3. 算法分析

同样，还是用例子和图来帮助大家理解这个算法。假设我们要对数组［3，13，1, 8, 2,21，1,5］进行排序，由于有两个1，所以将第二个1标记为“1*”。
首先，待排序数组长度n=8，选取增量d=$\frac{n}{2}$=4，则第1遍排序过程如下图所示。

第2遍排序时增量$d=\frac{d}{2}=2$，排序过程如下图所示。

第3 遍排序时增量$d=\frac{d}{2}=1$，排序过程如下图所示。

这样看起来似乎希尔排序并不比直接插入排序快。其实不是这样的，让我们来分析一下。开始时，希尔排序的增量 d 较大——分组较多，每组记录较少，因此直接插入排序的速度较快，后来增量d缩小——分组减少，每组记录增多，但各组内的记录均已为正序，因此排序速度还是比正常情况下的直接插入要快。看出来了吗？其实希尔排序相较于直接插入排序，就是优化了待排序数组的初始顺序，使其达到或接近于直接插入排序的最好情况。
由于增量的取值不同，增量的个数也不同，所以希尔排序算法的时间复杂度分析十分复杂。如果增量取值合理的话，则时间复杂度约为$O(n^{1.3})$。当然，若运气不好，则最坏情况的时间复杂度依然为 $O(n^2)$，并且希尔排序为不稳定排序。

4. 算法代码

算法代码如下：
Python

# 希尓排序
def shell_sort (array) :
    #设定初始增量d = n/2
    d = len(array)//2 #“//” 表示整数除法
    #当增量大于0时执行，如果小于0，则退出循环
    while d >0:
        #i的取值范围为d到n
        for i in range(d,len(array)):
            # 类似于直接插入排序，比较当前值与之前指定增量的值
            while i >= d and array[i-d]> array[i]:
                # 符合条件，则交换位置
                array[i],array[i-d]=array[i-d],array[i]
                # 取前一个指定增量的值，继续下一个判断
                i-=d
        # 将增量取半，回到 while 外循环
        d=d//2
    return array
# 调用 shell_sort 函数
print(shell_sort([34,21,13,2,5,1,55,3,1,8]))

java

 			int[] array ={
   34,21,13,2,5,1,55,3,1,8};
            int n = array.length/2;
            while (n>0){
   
                for (int i=n;i<array.length;i++){
   
                    while (i>=n && array[i-n]>array[i]){
   
                        int t= array[i];
                        array[i]=array[i-n];
                        array[i-n] = t;
                        i -= n;
                    }
                }
                n=n/2;
            }
            System.out.println(Arrays.toString(array));

5. 输出结果

6. 算法过程分解