老师你好，请问为什么看到有人说大量数据适合用快速排序，而小量数据适合插入排序呢？快速排序和归并排序时间复杂度是一样的，那么在大量数据时推荐使用哪个呢

Answer 1

liuyubobobo 2018-08-27 05:39:02

一看就是没有学习过我的《算法与数据结构》：）

大量的数据排序，如果数据本身没有特殊的性质（比如近乎有序），应该用快速排序。因为快速排序快。这也是快速排序名称的由来：）

首先，必须明确的是，时间复杂度只衡量趋势，看n无限大时的情况。所以他也有另一个称呼，叫“渐进时间复杂度”，这个“渐进”的由来就在这里。n要渐进无穷。但是对于具体的测试用例，时间复杂度无法描述具体性能，因为时间复杂度忽略了常数项和低阶项。一个算法，时间需要10000n，100n，2n，其时间复杂度都是O(n)级别的算法。

快排和归并同理。他们都属于O(nlogn)的算法，但是归并排序的比较次数是高于快排的（仔细分析一下merge的过程？），更不用提归并过程由于需要辅助空间，所有的元素都需要在merge汇总进行移动的过程：）

至于插入排序，是的，在小数据量的情况下，插入比快排归并都要快。多小算小，不同的计算机不一样不同的计算体系，结果不同。在我的课程中，选用16。这是我的《算法与数据结构》中专门讲的一个排序优化——在归并排序或者快排的过程中，当数据量小到一定程度时，转用插入排序。

为什么小数据量插入排序快，还是和系数有关。比如一个排序算法，虽然是O(n^2)的，但是实际T (n)= 2n^2，另一个算法，虽然是O(nlogn)的，但实际T(n)=16nlogn。算算看，当n=16时，O(n^2)复杂度的算法更快：）更不用提当数据近乎有序的时候，插入排序会“进化”成为O(n)级别的算法，而数据量越小，数据有序的概率越大。

最后打一个广告：推荐学习一下我的《算法与数据结构》。传送门：https://coding.imooc.com/class/71.html 

加油！

• 提问者 qq_湿腻焦糊_0 #1

  非常感谢！