希尔排序算法实例讲解（希尔排序）

本文目录

• 希尔排序
• 希尔排序的排序过程
• 数据结构：希尔排序
• 排序算法-7---希尔排序
• shell排序法是怎么实现
• 希尔排序的详解
• 希尔排序的详细过程
• 希尔排序法特点
• 希尔排序时间复杂度O(n¹.³)中的1.3是怎么来的

希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

第一轮排序：设置step步长为4，根据步长将数组分为四组，{1,3}， {4,2}，{6,5}，{0,9} 进行两两比较。
将i=step，开始往后遍历。如果a交换数据。得到第一轮排序结果：1 2 5 0 3 4 6 9
第二轮排序：设置step步长为2，根据步长继续两两分组，比较数据大小。得到第二轮排序结果：1 0 3 2 5 4 6 9
第三轮排序：设置step步长为1，根据步长继续两两分组，比较数据大小。得到第三轮排序结果：0 1 2 3 4 5 6 9

输出结果：
Shell sort:
0, 1, 2, 3, 4, 5, 6, 9,

希尔排序的关键并不是随便分组后各自排序，而是将相隔某个step 的记录组成一个子序列， 实现跳跃式的移动，使得排序的效率提高。
希尔排序的时间复杂度是O（nlogn），效率上比冒泡排序，直接插入排序，简单选择排序的O（n^2）要高。

希尔排序的排序过程

希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。
排序过程：先取一个正整数d1《n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2《d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。
　三趟结果
04 13 27 38 49 49 55 65 76 97 Shell排序的算法实现:
1． 不设监视哨的算法描述
void ShellPass(SeqList R，int d)
{//希尔排序中的一趟排序，d为当前增量
for(i=d+1;i《=n；i++) //将R分别插入各组当前的有序区
if(R.key){
R只是暂存单元，不是哨兵
do {//查找R的插入位置
R； //后移记录
j=j-d； //查找前一记录
}while(j》0&&R.key)；
R； //插入R到正确的位置上
} //endif

数据结构：希尔排序

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

说说我的个人理解：

希尔排序其实就是直接插入排序的升级，原理就是先将整个待排序列按照某个增量（也称步长）分割成若干个子序列分别进行直接插入排序，然后合并，之后依次缩小增量大小在进行排序，当增量足够小（通常为1）时，再对全体元素进行直接插入排序，而此时需排序的数据几乎是已排好的了，所以此时插入排序较快。

当然如果你觉得文字比较乏味就看下面的这些例子吧

例如，假设有这样一组数 ，如果我们先以步长为4进行分割，就是这样：

然后我们对每列进行排序（注意每列哦）：

将上述四行数字，依序合并我们得到： 。此时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,...)，该序列的项来自 和 这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序（后续博客整理），但是在涉及大量数据时希尔排序还是比快速排序慢。

排序算法-7---希尔排序

希尔排序（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）——希尔排序算法详解

排序：希尔排序（算法）

shell排序法是怎么实现

希尔Shell排序是一种插入排序算法，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-l《；…《d2《d1），即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法。

算法分析

增量序列的选择

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征：

① 最后一个增量必须为1；

② 应该尽量避免序列中的值(尤其是相邻的值）互为倍数的情况。

有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在n到1.6n之间。

Shell排序的时间性能优于直接插入排序

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

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度O(n）和最坏时间复杂度0(n^2）差别不大。

③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

因此，希尔排序在效率上较直接插人排序有较大的改进。

稳定性

希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。

算法讨论

Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。研究证明，若增量的取值比较合理，Shell排序算法的时间复杂度约为O（n（ldn）2）。由于Shell排序算法是按增量分组进行的排序，所以Shell排序算法是一种不稳定的排序算法。

算法步骤

Step1 将n个元素个数列分为5个小组，在每个小组内按直接插入法排序；

step2 在第i步，分组个数取 di+1 =（di +1）/2 {9，5，3，2，1}；相临两组之间的对应元素进行比较，如果ai》aj，则交换它们的位置；

Step3 当dK = 1的循环过程完成后，排序过程结束。

（详细请查看百度百科相关条目。）

希尔排序的详解

希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-l《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。

举例说明：

对于这样一个无序的数组5 9 3 2 6 11 8 1 7 4 10 ，想把它变成顺序递增的数组1 2 3 4 5 6 7 8 9 10 11。先隔3个元素取一次：把5 2 8 4取了出来，往后搓一位，把9 6 1 10取出来，再往后搓一位，又把3 11 7取出来。分别对这三个小组排序成为递增的序列，再插回去，如图：

于是得到了第一趟排序的结果：2 1 3 4 6 7 5 9 11 8 10.现在再以2为间隔重复以上步骤（这次得到的是两个小组）得到了2 1 3 4 5 7 6 8 11 9 10。最后再以1为间隔再搞一次（实际上这一步就是从左到右两两比较，调整位置），就得到了想要的结果。

这就是希尔排序，其要义就是先进行宏观调整，再进行微观调整。

希尔排序的详细过程

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

希尔排列

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

希尔算法

希尔排序法特点

1.3希尔排序特点
·一次移动，移动位置较大，跳跃式地接近排序后的最终位置
·最后一次只需要少量移动
·增量序列必须递减的，最后一个必须是1
·增量序列应该是互质的
1.4希尔排序算法
主程序：

子函数：

上面代码中i=0处存储了哨兵，所以真正的序列是从1开始的，因此i是从增量+1开始的。
在希尔排序的理解时，我们倾向于对于每一个分组，逐组进行处理，但在代码实现中，我们可以不用这么按部就班地处理完一组再调转回来处理下一组（这样还得加个for循环去处理分组）。比如，实现时不用循环按组处理，我们可以从第gap个元素开始，逐个跨组处理。同时，在插入数据时，可以采用元素交换法寻找最终位置，也可以采用数组元素移动法寻觅。
在写代码时，我们从下标为第一个增量值处开始，进行跨组处理，而不是一组一组处理，如果要一组一组处理，则需要额外增加一个for循环，这样增加了算法的复杂度。例如，初始序列如下（无哨兵，故初始序列的下标从0开始，则i=增量）：

若取增量为4，则分组结果为：{5，1，2}、{3，6}、{7，4}，{9，8}按照理解希尔排序的思路，我们应该先将{5，1，2}排好序后，再排{3，6}……但是这样做我们需要给整个程序加一个用于分组处理的for循环，增加了算法复杂度。因此我们这样考虑：从下标4处开始，减一个增量，先将这2个数排好序，然后继续往后跨组移动排序，接下来下标为5，那么我们减一个增量，继续排序……这样我们一直进行到整个序列的最后一个元素，此时我们就已经将所有的数排好序了。那么此时或许有一个疑问，这样做每次只交换了2个数，可是对于分组中有大于3个数的组，程序是怎么解决的呢？
比如说{5，1，2}，第一次时我们对5和1进行了排序，接下来我们跨组依次往后排序，此时到了2这个元素，那么我们用2减去增量，又到了5那个位置，将这2个数排好序，然后我们利用for循环再继续减增量，对这2个数再继续排序，，一直到减增量后的值小于0为终止条件，说明此时2以及2之前的5和1，这3个数已经彻底排好了序，如果说序列再足够长，等到有一个数减去增量后又等于2，那么再利用for循环对这4个数再依次进行排序。
程序如下：

1.5希尔排序算法分析
希尔排序算法效率增量序列的取值有关：
·Hibbard增量序列
·𝐷k=2k−1—相邻元素互质。 比如k从4开始，依次取15，7，3，1
·最坏情况：Tworst=O（n3/2）
·猜想：Tavg=O（n5/4）
上述算法的平均程度只是一个估计或者猜想，因为根据增量序列来估算希尔排序的算法效率还属于数学上没有解决的一个难题。

1.6希尔排序算法的稳定性
希尔排序法是一种不稳定的排序算法。举例：

1.7希尔排序算法分析总结
·时间复杂度是n和d的函数：
O（n1.25）~ O（1.6n1.25）——经验公式
·空间复杂度为 O（1）
·是一种不稳定的排序方法
√如何选择最佳d序列，目前尚未解决
√最后一个增量值必须为1，其它增量值无除了1之外的公因子
√不宜在链式存储结勾上实现（因为链式存储结构找同一个增量的分组序列很麻烦

希尔排序时间复杂度O(n¹.³)中的1.3是怎么来的

1、首先希尔排序是一种递减增量的排序算法，下面使用大小为9的数组：54、26、93、17、31、44、55、20。

2、令数据间隔为3，将该数组分成三个子数组，如下图所示，为下图中灰色的部分。

3、对每一个子数组都进行插入排序操作，将排序好的子数组合并到一个数组当中。这个时候，会发现，每个数字都会务必接近他应该存在的位置。

4、这是间隔为3的子数组排序后的结果，发现该排序后的数列非常接近我们需要的递减或者递增序列。下一步只需要，缩小间隔进行重复性操作即可

5、最后改变间隔，使间隔变成4，这个时候子数组反而有4组。这个说明希尔排序（shell sort）是一个不稳定的排序。