为何我的Quick Sort在随机数组上远慢于Heap Sort与Merge Sort？

以下是几个可能导致你的快速排序远慢于归并、堆排序的核心原因：

• 分区实现的低效
  若你使用的是Lomuto分区方案（单指针遍历），对比Hoare分区（双指针双向遍历）会产生更多的元素交换操作，大数据量下这种交换次数的差异会被显著放大。另外，分区过程中若存在冗余的边界判断、不必要的数组读写，也会额外增加耗时。

• 随机Pivot的额外开销
  如果每次选择Pivot都调用重量级的系统级随机数生成函数，频繁调用会累积大量额外耗时。可以尝试改用轻量级伪随机实现，或者预先生成随机数序列来降低这部分开销。

• 缺乏小分区优化
  当数组分区小到一定规模（比如元素个数小于20），快速排序的递归开销会超过插入排序的优势。若你的实现没有在小分区时切换到插入排序，会在大量小分区上浪费时间。

• 内存访问模式的劣势
  归并排序的内存访问是连续的（合并阶段操作连续子数组），缓存命中率极高；而快速排序的分区操作是跳跃式访问元素，容易触发缓存失效，在10万级别的数组规模下，这种缓存差异会导致性能差距被进一步放大。堆排序的内存访问虽不连续，但交换操作频率低于低效的快速排序实现。

• 时间测量的误差
  确认你的时间测量代码是否只统计排序算法的核心执行时间：有没有误将数组初始化、结果验证等额外操作计入？是否多次运行取平均值以避免系统调度带来的单次测量偏差？

建议的排查步骤 #

• 替换为Hoare分区实现后重新测试性能差异
• 单独统计随机数生成的耗时，确认是否占总运行时间的显著比例
• 添加小分区插入排序优化后对比性能变化
• 检查代码中是否存在重复计算、冗余变量等细节问题

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