图解排序算法

算法

# choose pivot
swap a[1,rand(1,n)]

# 2-way partition
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# recursive sorts
sort a[1..k-1]
sort a[k+1,n]

属性

• 不稳定
• O(lg(n)) 额外空间 (see discussion)
• O(n²) 时间，但通常 O(n·lg(n)) 的时间
• 没有真正适应

讨论

当认真贯彻实施时，快速排序是强大的并具有低开销。当并不需要一个稳定的排序是，快速排序是一个很好的通用排序 - 虽然三平均分区的版本应该总是被用来代替。

2路分区上面显示的是代码写的清晰度，而不是最佳性能较差的地方，而且，关键的是，当很少有不同键的时候，展示出O(n²)时间。一个在快速排序中更有效和强大的2路分割方法是由Robert Sedgewick和乔恩·本特利优化的。当有许多值等于支点，产生的概率保证O(n·lg(n))时间和O(lg(n))空间的所有输入时，可靠的分区产生均衡的递归。

两个子排序递归执行，当递归是不均衡时，快速排序在最坏的情况下需要O(n)的额外空间的递归栈。这是极其不可能发生的，但首先，在进行排序小的子阵列递归时它可以被避免；第二，可能被用而不是迭代完成的子数组排序是一个尾部递归调用。随着这种优化，在最坏的情况下该算法用掉 O(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.