图解排序算法

算法

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end

属性

• 不稳定
• O(1) 额外空间
• 从显示看需要 O(n^3/2) 时间 (看下面)
• 适应性：当接近排序完的时候耗费 O(n·lg(n)) 时间

讨论

希尔排序的最坏情况下的时间复杂度依赖于增量序列。对于增量为 1 4 13 40 121..., 这是用在这里，时间复杂度为 O(n^3/2)。对于其他的增量，时间复杂度是所知的O(n^4/3)，甚至O(n·lg²(n))，已知的既不是紧贴时间复杂度上界，也不是最好的增量序列。

由于希尔排序是基于插入排序，希尔排序继承插入排序的自适应性能。适应性不是剧烈的，因为希尔排序需要一次通过每个增量的数据，但它是显著的。对于递增序列如上图所示，有log₃(n) 增量，所以接近排序完的数据的时间复杂度为O(n·log₃(n))。

由于其低开销，相对简单的实现，自适应的性质，并分二次时间复杂度，希尔排序对于某些要进行排序的数据不是非常大的应用程序可能是一个可行的O(n·lg(n))排序算法的替代方案。

指示

• 点击来重新启动在行、列或整个表格中的动画。
• 可以直接点击动画图像来启动或重新启动它。
• 点击问题的规模来重置所有的动画。

关键

• 黑色的值是已经排好序的。
• 灰色的值是还未完成排序的。
• 一个红色的三角形标记算法的位置。
• 深灰色的值表示当前时间间隔(希尔排序, 归并排序, 快速排序)。
• 一对红色的三角形标记着左、右指针(快速排序)。

参考文档

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.

Dual Pivot Quicksort: Code and Discussion.

Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.