# choose pivot swap a[n,rand(1,n)] # 3-way partition i = 1, k = 1, p = n while i < p, if a[i] < a[n], swap a[i++,k++] else if a[i] == a[n], swap a[i,--p] else i++ end → invariant: a[p..n] all equal → invariant: a[1..k-1] < a[p..n] < a[k..p-1] # move pivots to center m = min(p-k,n-p+1) swap a[k..k+m-1,n-m+1..n] # recursive sorts sort a[1..k-1] sort a[n-p+k+1,n]
3路分区的快速排序相比标准的2路分区版本具有略高的开销。两者都具有相同的最好的,典型的,和最坏情况下的时间界限的性质,但在非常普遍的情况下这个版本对很少有不同键的排序具有很强的适应性。
如上所示的3路分割代码被清楚地写入而不是优良的性能,它具有较差的局部性,并且执行超出必要更多的互换。一个给出的更有效的但更复杂的三路划分方法是由Robert Sedgewick和乔恩·本特利优化的。
当不需要保证稳定性时,快速排序是通用的排序算法的选择。最近,一种新型的3路分割双枢转变体已被发现在理论和实践上击败了单枢轴3路分区方法。
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.