timsort和快速排序的比较 [英] Comparison between timsort and quicksort
问题描述
为什么说我大多听到的快速排序是最快的整体排序算法的时候timsort（根据维基百科），似乎性能要好得多？谷歌似乎没有露面任何形式的比较。
Why is it that I mostly hear about quicksort being the fastest overall sorting algorithm when timsort (according to wikipedia) seem to perform much better? Google didn't seem to turn up any kind of comparison.
推荐答案
TimSort高度优化归并，它是稳定的，比老归并排序快。
TimSort is highly optimization mergesort, it is stable and faster than old mergesort.
在与快速排序相比，它有两个好处：
when comparing with quicksort, it has two advantages:
- 这是令人难以置信的速度快了近排序的数据序列（包括反向排序的数据）;
- 在最坏的情况仍然是O（N *的log（n））。
说实话，我不觉得＃1是一个优势，但它确实IM preSS我。
To be honest, I don't think #1 is a advantage, but it did impress me.
下面是快速排序的优势
- 在快速排序是非常非常简单，即使是高度优化的实现，我们可以记下其pseduo codeS中的20行;
- 在快速排序是速度最快的，在大多数情况下;
- 的内存消耗的log（n）。
目前，Java 7的SDK实现timsort和一个新的快速排序的变体：即双枢轴快速排序
Currently, Java 7 SDK implements timsort and a new quicksort variant: i.e. Dual Pivot QuickSort.
如果你需要稳定的排序，尽量timsort，否则开始快速排序。
If you need stable sort, try timsort, otherwise start with quicksort.
这篇关于timsort和快速排序的比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
