1回答

liuyubobobo

2018-08-19

因为Quick Sort的复杂度的那个常数小。在我们学习算法复杂度分析的时候，复杂度符号大O，是忽略掉常数的。10000n，100n，2n都是O(n)，他们的复杂度是在一个级别的，但是实际性能却不同。同理，归并排序和快速排序都是O(nlogn)级别的，但是快速排序的那个常数更小。具体表现在，快速排序在每一层比较次数比归并排序少。（更不用提归并排序的merge过程，还需要一个辅助空间，将所有的元素都挪一边，而快速排序则完全是原地的。）

这也是快速排序叫“快速”排序的原因：）

2

0