Toptal连接了前3%的 自由开发人员 世界各地.
壳类
动画，代码，分析和讨论的shell排序在4个初始条件.
button.
算法
h = 1
while h < n, h = 3*h + 1
while h > 0,
h = h / 3
对于k = 1:h，插入排序a[k:h:n]
→不变式:每个h-子数组排序
结束
讨论
蛋壳排序的最坏情况下的时间复杂度取决于增量序列. 对于增量 1 4 13 40 121…这里用的就是这个，时间复杂度是O(n3/2). 对于其他增量，已知时间复杂度为O(n)4/3)，甚至O(n·lg)2(n)). 时间复杂度的严格上界和最佳增量序列都不知道.
因为shell排序是基于插入排序的, Shell排序继承插入排序的自适应属性. 这种调整并不引人注目，因为shell排序需要对每个增量进行一次数据遍历, 但这很重要. 对于上面显示的增量序列，有log3(n)个增量，所以近排序数据的时间复杂度为O(n·log)3(n)).
因为它的开销很低, 相对简单的实现, 自适应特性, 以及次二次的时间复杂度, 对于某些应用程序，当要排序的数据不是很大时，shell排序可能是O(n·lg(n))排序算法的可行替代方案.
关键
- 黑色值排序.
- 灰度值未排序.
- 深灰色值显示正在使用插入排序排序的当前子数组.
- 红色三角形标记算法位置.
属性
- 不稳定
- O(1)额外空间
- O(n3/2)时间如下所示(见下文)
- 自适应:接近排序时O(n·lg(n))时间