图解排序算法

算法

for i = 1:n,
    swapped = false
    for j = n:i+1,
        if a[j] < a[j-1],
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

属性

• 稳定
• O(1) 额外空间
• O(n²) 比较和互换
• 适应性：当接近排序完的时候耗费 O(n) 时间

讨论

冒泡排序法跟插入排序有许多相同的属性，但有小幅走高的开销。在数据接近排序完的的情况下，虽然冒泡排序需要O(n)的时间，但至少需要2次通过数据（其中，插入排序需要1次）。

指示

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

关键

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

参考文档

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.