希尔排序的详细过程

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐链塌裤渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。我们来通过演示图，更深入的理解一下这个过程。

希尔排列

希尔排序又叫递减增量排序算法，它是在直接插入排序算法的基础上进行改进而衫老来的，综合来说它的效率肯定是要高于直接插棚简入排序算法的；希尔排序是一种不稳定的排序算法。希尔排序由唐纳德·希尔（Donald Shell）发明并于1959年公布，因此得名希尔排序。

希尔算法

希尔排序（Shellsort），也称递减增量排序算法，是一种典型的插入排序算法，通过对原始序列进行分组进行排序。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

希尔排序的基本思想就是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

矩阵的列数取决于步长序列(step sequence)

比如，如果步长序列为{1,5,19,41,109...}.. 就代表依次分成109列、41列、 19列、 5列、1列进行排序

不同的步长序列，执行效率也不同

1、选择一个增量序列t1，t2，…，tk，其中对于i>j，有ti>tj，tk=1；（增量因子有多种取法，最简单的是t(i+1) = ti/2）

2、按增量序列个数k，对序列进行k 趟排序；

3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

**希尔排序的执行时间依赖于增量序列。 **

希尔排序耗时的 *** 作有：比较 + 后移赋值。

时间复杂度情况如下：（n指待排序序列长度）

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n²)好一些。

希尔算法的性能与所选取的增量（分组长度）序列有很大关系。只对特定的待排序记录序列，可以准确地估算比较次数和移动次数。想要弄清比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。

希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序没歼并有快速排序算法快，因此中等大小规模指举表现良好，对规模非常大的数据排序不是最优选择。

（注：专家们提倡，几乎任何排序工作在开始时都氏逗迹可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。）

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

备注：希尔排序的时间性能优于直接插入排序

参考文章

经典排序算法（5）——希尔排序算法详解

排序：希尔排序（算法）

void ShellSort(int r[],int n)//希尔排序

{

for(int gap=n/2gap>=1gap=gap/2)//以增斗槐大量为d进行直接插入排序

{

CountCompare[1]++

for(int i=d+1i<=ni++)//将r[i]插入到所属的子序列中

{

r[0]=r[i]//暂存被插空竖入记录明颂

CountMove[1]++

for(int j=i-dj>0&&r[0]<r[j]j=j-gap)

{

r[j+d]=r[j]//记录后移gap个位置，保证仍在同一个子序列

CountCompare[1]++

CountMove[1]++

}

r[j+gap]=r[0]

CountMove[1]++

}

for(int k=1k<=nk++)

cout<<r[i]<<" "

}

}

//主程序就麻烦自己写了

---