排序算法-7---希尔排序
希尔排序（Shellsort），也称递减增量排序算法，是一种典型的插入排序算法，通过对原始序列进行分组进行排序。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
希尔排序的基本思想就是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
矩阵的列数取决于步长序列(step sequence)
比如，如果步长序列为{1,5,19,41,109...}.. 就代表依次分成109列、41列、 19列、 5列、1列进行排序
不同的步长序列，执行效率也不同
1、选择一个增量序列t1，t2，…，tk，其中对于ij，有titj，tk=1；（增量因子有多种取法，最简单的是t(i+1) = ti/2）
2、按增量序列个数k，对序列进行k 趟排序；
3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
**希尔排序的执行时间依赖于增量序列。 **
希尔排序耗时的操作有：比较 + 后移赋值。
时间复杂度情况如下：（n指待排序序列长度）
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长***，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n²)好一些。
希尔算法的性能与所选取的增量（分组长度）序列有很大关系。只对特定的待排序记录序列，可以准确地估算比较次数和移动次数。想要弄清比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。
希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序没有快速排序算法快，因此中等大小规模表现良好，对规模非常大的数据排序不是***选择。
（注：专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。）
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
备注：希尔排序的时间性能优于直接插入排序
参考文章
经典排序算法（5）——希尔排序算法详解
排序：希尔排序（算法）
希尔排序
希尔排序又称 缩小增量排序 ，其也属于插入排序类算法。相教于一般的插入算法、 折半插入 算法、 2-路插入 算法以及 表插入 算法，希尔排序在时间效率上更加优秀。
对于普通的插入算法，其时间复杂度为 ，且在序列有序时，可以达到***的时间复杂度 ；而且当 较小时，由于移动的元素较少，插入排序效率也比较高。
因此，我们可以采用 分治 的思想，先将整个待排序序列分割成为若干个子序列分别进行插入排序，待整个序列「基本有序」时再对全体进行插入排序，即自底向上实现整个序列的排序。
【注】这里的子序列不是简单的逐段分割，而是将相隔某个 增量 的元素组成一个子序列，这样对子序列进行插入排序时，元素就不是一步一步移动，而是跳跃式地往前移。
其中，数组 D 为增量序列。常用的增量序列有：
希尔排序是 不稳定的、原址的 。不稳定原因在于希尔排序中不同段交换元素时会打乱相等元素初始的相对位置。
数据结构：希尔排序
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
说说我的个人理解：
希尔排序其实就是直接插入排序的升级，原理就是先将整个待排序列按照某个增量（也称步长）分割成若干个子序列分别进行直接插入排序，然后合并，之后依次缩小增量大小在进行排序，当增量足够小（通常为1）时，再对全体元素进行直接插入排序，而此时需排序的数据几乎是已排好的了，所以此时插入排序较快。
当然如果你觉得文字比较乏味就看下面的这些例子吧
例如，假设有这样一组数 [9 1 5 8 3 7 4 6 2] ，如果我们先以步长为4进行分割，就是这样：
然后我们对每列进行排序（注意每列哦）：
将上述四行数字，依序合并我们得到： [ 2 1 4 6 3 7 5 8 9 ] 。此时2已经往前移，而8、9已经在后两位，然后再以2为步长进行分割：
继续排序：
合并得到 ［ 2 1 3 6 4 7 5 8 9］ ，此时序列已经基本有序，需交换数据的情况大为减少，这时整列进行直接插入排序效率就非常高。
最终完成排序过程，也就是步长为1时，得到最终序列为： 1 2 3 4 5 6 7 8 9 。
可能有几个步骤略难懂，这里解释下：
当 时，9和3进行了一次交换，变为 （3 9 2） (位置为1 5 9），之后在 时 ，做出的交换如上图所示（图略差...)，分为三个步骤：
步长的选取非常关键，但是步长的选择没有统一规定，也没绝对的规律。只要满足最后一个步长为1即可。Donald Shell最初建议步长选择为 ,虽然这样去可以比 类的算法更好，但仍然有减少平均时间和最差时间的余地。维基百科给出的部分步长与最坏情况下复杂度有：
已知的***步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，该序列的项来自 和 这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序（后续博客整理），但是在涉及大量数据时希尔排序还是比快速排序慢。
希尔排序的详细过程
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。我们来通过演示图，更深入的理解一下这个过程。
希尔排列
希尔排序又叫递减增量排序算法，它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的；希尔排序是一种不稳定的排序算法。希尔排序由唐纳德·希尔（Donald Shell）发明并于1959年公布，因此得名希尔排序。
希尔算法
希尔排序的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于希尔排序属于什么类型排序、希尔排序的信息别忘了在本站进行查找喔。