排序算法对比：快速排序（Quick Sort）是否总比插入排序（Insertion Sort）快

答案是否定的，O(nlog(n))时间复杂度的快速排序，并不代表它的运行速度永远快于O(n²)的插入排序，具体原因如下：

• 大O时间复杂度描述的是数据规模趋近于无穷大时算法耗时的增长趋势，计算时会忽略常数项、低阶项和系数，只能反映大规模数据下的效率走向，不能直接等同于任意数据规模下的实际运行耗时。
• 小数据量场景下插入排序的表现更优：插入排序的单步操作成本极低，仅需相邻元素的比较和移动，没有额外的递归开销，对CPU缓存也非常友好，常数项远低于快速排序。当待排序元素个数小于50~100这个区间时，就算插入排序是O(n²)的复杂度，实际运行速度也会比快速排序更快。现在多数工业级排序实现（比如C++的std::sort）都会在快速排序递归到小区间时，自动切换为插入排序提升整体性能。
• 极端场景下快速排序的性能会劣化：如果没有做基准选择优化（比如每次都取区间首尾元素做基准），遇到完全有序、完全逆序或者大量重复元素的输入时，快速排序的时间复杂度会跌到最坏的O(n²)，此时运行速度会远慢于插入排序。另外对于近乎有序的数据集，插入排序的实际耗时接近O(n)，性能也会明显优于快速排序。

内容的提问来源于stack exchange，提问作者swasthik sbhat