为什么？它更快还是更有效？
对于具有一个核心的系统,我们可以使用quicksort.我们应该在具有两个内核,四个内核或八个内核的系统上使用什么？
Mic*_*rdt 34
快速排序具有在适当位置被完全的优点,所以它不需要任何额外的存储,而归并(其是实际使用Arrays.sort()为对象阵列)和其他(所有？)保证为O(n*log n)的算法需要至少一个数组的完整副本.对于对非常大的原始数组进行排序的程序,这意味着可能会使整体内存使用量翻倍.
Jos*_*Lee 18
答案在Jon L. Bentley和M. Douglas McIlroy的"工程排序函数"中,排序函数引用.
为了获得更好的qsort,我们发现1983年在Berkeley编写的qsort会在包含少量元素重复多次的数组上消耗二次时间 - 特别是随机零和1的数组.事实上,在十几个不同的Unix库中,我们发现没有qsort不能轻易被驱动到二次行为 ; 所有这些都来自第七版或1983年的伯克利函数....
无法找到足够好的qsort,我们打算建立一个更好的.该算法应该避免合理输入的极端减速,并且应该在"随机"输入上快速.它在数据空间和代码空间中也应该是高效的.排序不一定稳定; 它的规范不保证保持相等元素的顺序.
由于Java是在20世纪90年代初创建的,所以替代品是heapsort和mergesort.Mergesort不太理想,因为它需要额外的存储空间.Heapsort具有更好的最坏情况性能(与之O(n log n)相比O(n^2)),但在实践中表现更慢.因此,如果您可以通过良好的启发式方法控制最坏情况的性能,那么可以采用经过调整的快速排序方式.
Java 7正在转向Timsort,它是在1993年发明的(2002年在Python中实现),具有最差的性能,O(n log n)并且是一种稳定的类型.
Orb*_*ing 14
Quicksort具有O(n log n)平均值和O(n ^ 2)最差情况性能,这是排序算法可能的最佳"平均情况",还有其他排序算法具有此性能,但快速排序往往表现更好比大多数人.
请参阅:http://en.wikipedia.org/wiki/Quicksort
Boz*_*zho 10
这是一个经过调整的快速排序.如果您真的感兴趣,可以阅读文档中提到的材料.
排序算法是一个经过调整的快速排序,改编自Jon L. Bentley和M. Douglas McIlroy的"工程排序功能",软件实践和经验,卷.23(11)P.1249-1265(1993年11月).
这里有一点解释 - 调优版本在许多数据集上给出了n*log(n):
该算法在许多数据集上提供n*log(n)性能,导致其他快速降序降级为二次性能