希尔排序详解与代码实现

1.简单介绍

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序;它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

看希尔排序前，建议先弄懂插入排序。关于插入排序可以看博主的这篇文章：https://blog.csdn.net/ltf971101/article/details/113767434

2.基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。就是将数据进行分组插入排序，这样防止出现在后面的较小数需要经过多次比较移动来找到正确位置。

3.过程图解

4.代码实现（java实现，和插入排序类似，只是增加了分组的过程。）

private static void shellSort(int[] nums) {
    int n = nums.length;
    // 分组区间 range  需要逐步缩小这个range 分组逐渐变少 整个数组逐渐有序
    for (int range = n / 2; range > 0; range /= 2) {
        for (int i = range; i < n; i++) {
            int j = i;
            int tmp = nums[j];
            if (nums[j] < nums[j - range]) {
                while (j - range >= 0 && tmp < nums[j - range]) {
                    nums[j] = nums[j - range];
                    j -= range;
                }
                nums[j] = tmp;
            }
        }
    }
}

输入:{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}

输出:

第1轮希尔排序中间结果：[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
第2轮希尔排序中间结果：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
第3轮希尔排序中间结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最终排序结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

可以结合这个结果和上面的流程图解来理解代码。

5.总结

建议先看完插入排序在看希尔排序 会帮助理解。