type
status
category
date
slug
summary
tags
icon
Last edited time
May 21, 2023 07:57 AM
一、什么是希尔排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
二、动图演示
- 动图来自菜鸟教程
举个例子,
对于
{1,2,3,4,5,6,7,8,9,10}
选取d
为3,那么我们就对{1,4,7,10}{2,5,8}{3,6,9}
这三个逻辑上的组
进行一次直接插入排序
然后下一次d
取为2.....
d
取为1.....整个文件恰被分成一组,算法便终止
这也就是希尔排序又称为"缩小增量排序"的原因三、实现方式
先将排序表分割成
d
个形如 $L[i,i+d,i+2d,...,i+kd]$的“特殊”子表,分别进行直接插入排序,当整个表中的元素已呈“基本有序时”,再对全体记录进行一次直接插入排序。四、关于希尔排序的性能参数
1、时间复杂度
最坏:
某些情况下:
2、空间复杂度
$O(1)$
3、是否稳定
不稳定
4、适用于何类型存储
顺序存储
五、代码实现
对于
d
这个增量的取值,我采用的是Shell
的方法:希尔排序第1趟的增量: 希尔排序第$i$躺的增量: 直到最后一个$d_k=1$
1、算法
2、实例实现
- 作者:Jimmy Huang
- 链接:https://huangjihao.com/9032bb28-ec70-4e07-aa44-a98342336db6
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。