为什么快速排序在数组小时慢呢？

Question

    我在学习数据结构内排序。书上有句话是这样说的：“事实上，快速排序在n（指的待排序数组的长度）很小时是很慢的！”，“一个简单的改进是用能较快处理较小数组的方法来代替快速排序，如插入排序和选择排序”。我现在想要问的是：
（1）为什么快速排序在n很小时会很慢？
（2）插入排序和选择排序就很快吗？快速排序平均时间复杂度是nlogn,而插入排序和选择排序是n^2.那怎么会更快呢？
希望大侠们解我迷团！我用的教材是电子工业出版社的《数据结构与算法分析（C++版）》，Clifford A.Shaffer著！

Answer 1

快速排序使用了分治的思想.所以在n很大时,分治处理的效率很高.但是n很小时,分治的优势就体现不出来了.相反其他插入货或是选择排序会更快.因为cpu在内存中执行之时.不需要频繁的隔着很远的内存单元读取数据放置入寄存器.只需要顺序读取.所以其他算法在n很小时比快速排序快.这一点类似硬盘的读写.

Answer 2

不单是快速排序，归并排序，堆排序等，在小的数量小情况都比不上插入
可以理解为插入排序
 T1 = c1 * n * n
归并排序，堆排序等亚2次排序（快排的平均时间也是这个界）
 T2 = c2 * n * log(n)其中c1和c2是与n无关的常数，他们其实代表排序的每个迭代步骤中需要执行的操作数量
显然，c1 < c2
所以，存在一个n使T1 = T2即
c1 * n * n = c2 * n * log(n)
得到：
log(n) / n = (c1 / c2)