排序算法-希尔排序

希尔排序是插入排序的高效版本，算法实现原理是先定义一个间距gap，以二分的方式作为间距进行排序来举例，先把序列分成gap个组，然后对每个gap中的元素进行插入排序。再将gap二分，产生新的gap，继续重复上述操作，直到gap=1，做整个序列的插入排序，这个不断二分插入排序的过程中整体序列是不断向有序变化的。

1.代码实现

以java实现为例：

public class ShellSort {
    public static int[] shellSort(int[] nums) {
        int gap = nums.length / 2;  //间距为序列长度的二分
        while (gap > 0) {  //当gap>0时一直重复操作，直到做完gap=1时的全序列插入排序
            //对gap组数据进行遍历
            for (int i = 0; i < gap; i++) {
                //以下循环本质上是一个插入排序，只不过从基础插入排序的增量1变成了这里的增量gap
                for (int j = i + gap; j < nums.length; j += gap) {
                    int k = j - gap;
                    while (k >= 0 && nums[k] > nums[k+gap]) {
                        int temp = nums[k];
                        nums[k] = nums[k+gap];
                        nums[k + gap] = temp;
                        k -= gap;
                    }
                }
            }
            gap /= 2; //二分gap
        }
        return nums;
    }

    public static int[] shellSort1(int[] nums) {
        int gap = nums.length / 2;  //间距为序列长度的二分
        while (gap > 0) {
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < nums.length; j += gap) {
                    for (int k = j; k - gap >= 0 && nums[k] < nums[k-gap]; k -= gap) {
                        int temp = nums[k];
                        nums[k] = nums[k - gap];
                        nums[k - gap] = temp;
                    }
                }
            }
            gap /= 2;
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
        int[] newNums = shellSort1(nums);
        for (int x : newNums) {
            System.out.print(x+" ");
        }
    }
}

上面的代码用了插入排序的两种写法，方便以后自己温习。了解了算法的思路之后写法都可以自由发挥。

2.数据运行解析

数据的分解示例如下

[9 8 7 6 5 4 3 2 10]      第一次二分时，gap=4，将对下标为以0-gap为基数，gap为增量的多组数据进行排序。例如0 4,1 5,2 6。。。
-> [5 8 7 6 9 4 3 2 10]  
-> [5 4 7 6 9 8 3 2 10]   
-> [5 4 3 6 9 8 7 2 10]   
-> [5 4 3 2 9 8 7 6 10]   
-> [5 4 3 2 9 8 7 6 10]   
---------此时第一次gap=4时的情况结束
[5 4 3 2 9 8 7 6 10]      再次二分，跳入gap=2循环，例如序列为0 2 4 6 8和序列为1 3 5 7
->[3 4 5 2 9 8 7 6 10] 
->[3 4 5 2 7 8 9 6 10]    此时0 2 4 6 8的序列已经排序完成
->[3 2 5 4 7 8 9 6 10]   
......

数据变化样例写的比较简单，感兴趣的话可以debug观察一下程序运行情况即可想明白原理，下方也给出了参考链接。

3.复杂度分析

希尔排序的时间复杂度是比较复杂的分析，跟增量的数学模型相关，最差是O(nlog²n)，平均时间复杂度是O(n√n)，空间复杂度为T(1)。

参考资料：

1）https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin

2）https://blog.csdn.net/weixin_41190227/article/details/86600821