我正在研究我发现的双枢轴快速排序here http://aofa2013.lsi.upc.edu/slides/Nebel.pdf（幻灯片第 20 页）
比较：
雅罗斯拉夫斯基平均需求 = 1.9 n ln n。
经典快速排序需要 = 2 n ln n 比较！
Swaps:
Yaroslavskiy 算法的交换 = 0.6 n ln n
经典快速排序的交换=0.3 n ln n
Results
数据类型-----comp--------swap
整数-------------591ns---------802ns
浮动-----------838ns----------873ns
双倍 ------873ns----------1047ns
字符----------593ns------------837ns
/* 注意：- 以上结果以纳秒为单位，并使用 intel core 2 duo 在 java lang 中执行 */
如果我们结合交换和比较的成本，经典快速排序会击败雅罗斯拉夫斯基快速排序
除非在字符串情况下，我们使用指针数组进行交换，这需要 88 纳秒。这里 Yaroslavskiy 的算法利用 1.9 n ln n 比较，因为与字符串情况下的交换相比，比较成本太高。
我想知道为什么java使用Yaroslavskiy Quicksort？内置库排序的主要焦点是字符串，如果它对其他数据类型不好怎么办？
我不知道你从哪里得到你的号码。根据这一页 http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628:
事实证明，对于双枢轴快速排序，平均数量
比较是2*n*ln(n)，平均交换次数为0.8*n*ln(n),
而经典的快速排序算法有2*n*ln(n) and 1*n*ln(n)分别。
看起来双轴总是更好。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
