jjn*_*guy 52
画一个数组:
3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0
甲两个分隔快速排序会挑选一个值,即4,并把每一个元素大于4在阵列的一侧,在另一侧上的每一个元素小于4.像这样:
3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5
一个三分区快速排序将选择两个值进行分区并以这种方式拆分数组.让我们选择4和7:
3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9
这只是常规快速排序的一个小变化.
您继续对每个分区进行分区,直到对数组进行排序.运行时在技术上是nlog 3(n),它与常规快速排序的nlog 2(n)略有不同.
cgp*_*cgp 16
http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf
也可以看看:
http://www.sorting-algorithms.com/quick-sort-3-way
我认为面试问题版本也很有趣.它问,有四个分区版本的快速排序 ...
run*_*431 13
我认为3路分区是由Djstrka完成的.
想想带有元素的数组{ 3, 9, 4, 1, 2, 3, 15, 17, 25, 17 }.
基本上你设置了3个分区:小于,等于和大于某个分支.等于分区不需要进一步排序,因为它的所有元素已经相等.
例如,如果我们选择第一个3作为枢轴,那么使用Dijkstra的三向分区将排列原始数组并返回两个索引m1,m2使得索引小于的所有元素m1将低于3索引更大的所有元素等于或m1小于或等于m2等于3,并且索引大于的所有元素m2将大于3.
在这种特殊情况下,结果数组可能是{ 1, 2, 3, 3, 9, 4, 15, 17, 25, 17 },而值m1和m2将是m1 = 2和m2 = 3.
请注意,生成的数组可能会根据用于分区的策略而更改,但数字m1和数字m2会相同.
Aut*_*tic 12
如果你真的使用Akra-Bazzi公式计算数学,将分区数作为参数,然后优化该参数,你会发现e(= 2.718 ...)分区提供了最快的性能.然而,在实践中,我们的语言结构,cpus等都针对二进制操作进行了优化,因此标准分区为两组将是最快的.