希尔排序

概念介绍

　　有同学想了解希尔排序，今天它来了！在了解希尔排序之前，必须得有插入排序的基础，如果对插入排序不了解的朋友，可以看下https://www.cnblogs.com/maguanyue/p/11593059.html。

　　我们先来看下插入排序可能存在的问题。在上述插入排序中，我们使用[2，7，-5，30，9]作为例子进行排序。现在我们在这个序列最后一行加入一个数字-1，那么准备排序的序列变为[2，7，-5，30，9，-1]。在四轮插入排序后，序列会变为[5-，2，7，9，30，-1]，最后一轮待插入的数字为-1，在这种情况下，-1与排在它前面的数字分别进行对比后，会将对比的数字往后移，这就造成了很大的开销。

　　为了解决插入排序低效的问题，希尔排序出现了。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。大家先得了解增量的概念，我们定义初始值为0，增量为2，那么0的下一个数是什么？那就是2，依次类推，我们可以得到，[0，2，4，6...]，增量为2就是这个意思。希尔排序的核心思想是：把待排序元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个序列恰被分成一组，此时排序完成。

　　举个简单的例子，对[2，7，-5，30，9，-1，3，8]这个序列进行排序，大家要记住，每轮排序前，我们需要找到该轮排序的增量并进行分组。

　　为第一轮排序找增量：初始增量， increment= 8（元素个数）/2 = 4（本轮增量），整个数组分成了4 组，分组的规则是，2与9一组，7与-1一组，-5与3一组，30与8一组，为什么这么分呢？从数组的第一个下标[0]开始，[0]=2，0+increment=4，[4]=9，第一组2与9分组完毕，同理，[1]=7，1+increment=5，[5]=-1，第二组7与-1分组完毕。剩下分组情况类似。[2，9]，[7，-1]，[-5，3]，[30，8]。

　　第一轮排序开始：每轮排序前，我们需要做的就是找增量然后进行分组。分组完毕后，我们需要对组内的元素使用插入排序进行排序。分组：[2，9]，[7，-1]，[-5，3]，[30，8]，组内排序：[2，9]，[-1，7]，[-5，3]，[8，30]。第一轮分组排序后的序列为：[2，-1，-5，8，9，7，3，30]。

　　为第二轮排序找增量：缩小增量，4（第一轮排序增量）/2=2（本轮增量），整个数组分成了2 组。

　　第二轮排序开始：分组：[2，-5，9，3]，[-1，8，7，30]，对分成的两组进行组内培训[-5，2，3，9]，[-1，7，8，30]。第二轮分组排序后的序列为：[-5，-1，2，7，3，8，9，30]。

　　为第三轮排序找增量：缩小增量，2（第二轮排序增量）/2=1（本轮增量），整个数组分成了1 组。

　　第三轮排序开始：分组：[-5，-1，2，7，3，8，9，30]，对组内元素使用插入排序。排序后的序列为：[-5，-1，2，3，7，8，9，30]。

　　第三轮排序完毕时，增量已经减至1，排序结束。看完例子大家对希尔排序的思想是不是理解更深刻了？

代码实现

　　其核心思想其实就是递归缩小增量量直至1以及根据增量分组后使用插入排序。

public static void shellSort(int[] arr) {
        // 取序列的一半为增量，以后每次减半，直到增量为1
        for (int increment = arr.length / 2; increment > 0; increment /= 2) {
            // 从第increment个元素开始，逐个对其所在的组进行直接插入排序
            for (int i = increment; i < arr.length; i++) {
                int insertIndex = i;
                int insertValue = arr[insertIndex];
                // 插入排序实现
                if (arr[insertIndex] < arr[insertIndex - increment]) {
                    while (insertIndex - increment >= 0 && insertValue < arr[insertIndex - increment]) {
                        // 通过对比后，将较大的数后移
                        arr[insertIndex] = arr[insertIndex - increment];
                        insertIndex -= increment;
                    }
                    // 将插入的值放到合适的位置中
                    arr[insertIndex] = insertValue;
                }
            }
        }
    }

　　至此，代码编写完成，Git地址：https://github.com/HollowCup/algorithms-and-data-structure，具体实现位于algorithm工程下的sort目录ShellSort，如果发现不足之处，请联系我进行更改，十分感谢！关注我，为你揭秘更多排序算法！