:-: 14.6 希尔排序 * * * * * **基本概念：** 它也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率； 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位； 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。 它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。 **算法的运作** 1、选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1； 2、按增量序列个数 k，对序列进行 k 趟排序； 3、每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 **图片示例：** :-:  :-:  **代码实现：** ~~~ public static void shellSort(int[] nums) { int gap = 1, i, j, len = nums.length; int temp; while (gap < len / 3) { gap = gap * 3 + 1; } for (; gap > 0; gap /= 3) { for (i = gap; i < len; i++) { temp = nums[i]; for (j = i - gap; j >= 0 && nums[j] > temp; j -= gap) { nums[j + gap] = nums[j]; } nums[j + gap] = temp; } } } ~~~ **与插入排序的不同：** 希尔排序与选择排序最主要的差别在于引入了一个step变量(指步长，一些书上喜欢用gap或h来表示)，这使得每次交换元素位置，都可以使该元素向其最终位置跨一大步，看图： :-:  随着排序的进行，数组越来越接近有序，步长也越来越小，直到step=1，此时希尔排序就变得跟插入排序一模一样了，但此时数组已经几乎完全有序了，还记得前面所说过的吗？对一个几乎有序的数组运行插入排序，其复杂度接近O(N)。整个过程看起来天衣无缝，然而其中隐藏着一个难点，应该使用怎样的步长序列？必须要考虑的因素有两点： 当改变步长的时候，如何保证新的步长不会打乱之前排序的结果？这不会影响最终排序的正确性，因为只要步长在减小，数组永远都只会朝着更加有序的方向迈进，但这却是影响希尔排序效率的关键。因为这涉及到完成排序的过程中，算法做了多少无用功。 如何保证每一个步长都是有意义的？来看一个例子，假设有一个数组[1,5,2,6,3,7,4,8]，使用步长序列[4,2,1]对其进行排序，过程如图： :-:  这就相当于进行了一次低效的插入排序，因为在step=1之前，程序什么也没干，偶数位置永远不会与基数位置进行比较。而下文你会看到，[4,2,1]正是按照Shell本人一开始推荐的增量算法得来的。 **增量的选择：** 1、Shell增量:N/2,N/4,N/8...1 即初始步长选择N/2，后面每次取半直到步长为1，它出自Shell本人且非常容易用代码表达，因此而流行，我看到现在的一些文章都还在使用它。然而前面的例子已经可以看出，在一些特定输入下它非常低效，它在最坏情形的时间复杂度仍是O(N^2)。事实上除了这个序列，后面列出的序列在最坏情形的性能差距都不会很大。 2、Hibbard增量:1,3,7,15...,2^k-1 最坏情形θ(N3/2)),平均复杂度大概是O(N5/4)，它的重要改进是相邻的增量之间没有公因子。而Shell增量之所以不好，因为它的增量之间并非互素，如果这很难理解就回顾一下上面使用[4,2,1]步长排序的例子，再脑补一下用[6,3,1]步长对[1,5,9,2,6,10,3,7,11,4,8,2]排序的情形。 3、Knuth增量:1,4,13,40,...,(3^k - 1)/2 同为θ(N3/2)，但貌似这个序列使用最广泛，即便现在已经证实了有更好的步长序列。 4、Sedgewick增量:1,5,19,41,109... 最坏情形O(N4/3)，这是已知复杂度(还有一些实践起来效果很好的序列至今没有算出复杂度)的最佳序列，通过 1,19,109,505,...,9×4k−9×2k+1 5,41,209,929,...,2k+2×(2k+2−3)+1 两个算式综合而来，依据基偶性交叉选择两个算式的结果即可。 **复杂度分析：** 时间复杂度：平均：根据步长序列的不同而不同、最坏：O(nlog^2n)、最优：O(n)。 空间复杂度：最坏：O(n)、最优：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。** **本文主要参考以下文章：** [维基百科——希尔排序](https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F) [聊聊4种主流排序算法(上)](https://blog.staynoob.cn/post/2016/04/insertion-shell-merge-quick-sort-algorithm-1/) [经典排序算法](https://www.cnblogs.com/onepixel/articles/7674659.html) [排序算法总结](https://itimetraveler.github.io/2017/07/18/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E4%B8%8Ejava%E5%AE%9E%E7%8E%B0/)