图解排序算法

讨论

这些页面在4个不同的初始条件下显示8个不同的排序算法，这些可视化的目的是：

• 显示每个算法是如何运行的。
• 表明没有最好的排序算法。
• 显示每个算法的优点和缺点。
• 表明最坏的情况下的渐近行为并不总是在选择一个算法时的决定因素。
• 表明初始条件（输入顺序和密钥分配）跟算法的选择一样影响性能。

理想的排序算法将具有以下性质：

• 稳定性：相同的键不重新排序。
• 运行的地方，需要O(1)的额外空间。
• 最坏情况下 O(n·lg(n)) 键进行比较。
• 最坏情况下 O(n) 互换。
• 自适应：当数据差不多排好序时或很少有不同键时能加快到 O(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.