“快速排序“ 的一个疑问，请教下各位朋友：）
quicksort在序列的各个元素不相同时效率比较高, nlgn。
但是，如果序列的各个元素几乎都相同时，效率就低了，n^2。
以下是我对randomized quicksort的一个测试
./quicksort [size] [range] 表示 sort [size] elements of range [0 - range]
~/MyPro/Algorithms/sort $ ./quicksort 1024 10000000
start sorting ...
sorting finished!
====================================
Randomized Quicksort
Sorting 1024 elements
Time: 0s 468us
The result is right !
====================================
~/MyPro/Algorithms/sort $ ./quicksort 1024 1
start sorting ...
sorting finished!
====================================
Randomized Quicksort
Sorting 1024 elements
Time: 0s 15426us
The result is right !
====================================
可以看到，当元素几乎相同时（如第二个输入，元素只有0和1），排序效率明显很低。
有么有什么办法对quicksort进行改进使它可以处理这种情况呢？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（19）
code google
没找到Tim peter排序算法资料.
先判数据的场景啊，如果是大量重复最好就不要用快速排序了
快速排序不是稳定的，对于大量重复的数据还是用稳定的排序算法好，比如说堆排序，归并排序，shell排序，虽然比快速排序慢一点，但至少是稳定的
回复
有个问题哦。如何通过一次扫描解决，如下问题。假设N个数大于100个，其中相同的只有1和2，但存在两种可能，存在5个1和5个2，与存在 7个与 3个2的差异？一次扫描只能对第一层递归有效。对子递归，是无法利用该信息的。不知道你是否考虑过。
回复
http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
辛苦了。3q
if(数据大,且重复率高) //这处判断的耗时 可能就让你的优化白费.
use_heap_sort();
else
use_quick_sort();
回复
都是应该小朋友做的题目。我是闲得蛋疼，顺顺手而已。
数量级O(nlogn)的排序算法有现成的啊，insert-sort-with-binary-search，inplace-merge-sort，heap-sort都是雷打不动的O(nlogn)，不论输入的是什么样的数据。
综合的看,快速排序只是在普通时候最快而已.你的情况已经不是普通时候了,那么还想最快的话,就不应该使用这种方法.
数量级O(nlogn)的排序算法有现成的啊，insert-sort-with-binary-search，inplace-merge-sort，heap-sort都是雷打不动的O(nlogn)，不论输入的是什么样的数据。
楼主，这有答案了。。。哈。
数量级O(nlogn)的排序算法有现成的啊，insert-sort-with-binary-search，inplace-merge-sort，heap-sort都是雷打不动的O(nlogn)，不论输入的是什么样的数据。
什么叫做非比较模型？排序算法固定下，唯一不定是对比较的方式的差异性。你改成浮点比较，还有什么问题？
回复
非比较模型就是不是直接比较按键值大小来决定位置的, 我记得是这样. 比较模型总要if(a>b)之类的东西. 我还记得,比较模型排序撑死了最好的复杂度是O(nlog), 这是在数学上证明了的, 你不是搞数学嘛, 来来来, 求证.
这个事情不能强求的。抽象点将，你使用一个中优化方式，是有边界条件的。当在边界条件的另一端的实例，就会导致你做的更差。
关键看你是想用非等概率的优化策略，还是等概率的优化策略。后者也有。只不过任意数据进来，时间都差不多。而不会这个样本快，那个样本慢这种情况出现。
看你对输入数据的先验的假设情况了。
额。。。。我对优化没什么了解。我这种计时方法不太对么？我在两次取时间之间，只调用了quicksort这个排序。
time1= now
xxx
...
xxx
time2=now
time= time2-time1
然后说怎么优化呢?
这都跟谁学的啊？！！！！！！！！！！！误人子弟啊！
这个事情不能强求的。抽象点将，你使用一个中优化方式，是有边界条件的。当在边界条件的另一端的实例，就会导致你做的更差。
关键看你是想用非等概率的优化策略，还是等概率的优化策略。后者也有。只不过任意数据进来，时间都差不多。而不会这个样本快，那个样本慢这种情况出现。
看你对输入数据的先验的假设情况了。