algorithm - 混合快速/合并排序在随机数据上的性能

Question

一个测试要求我实现一个排序算法，该算法对一个数组进行排序，当大小为 N > 1000 时，通过合并排序，否则通过带有枢轴的快速排序随机选择。然后假设要比较的键由 [1, M] 上的随机分布的整数组成。M 应该如何才能使上述算法运行得最好？

如果大小<=1000，我让快速排序处理合并排序的递归调用。在我看来，由于随机键、随机枢轴和 Hoare 的分区方案不会因重复元素而减慢，如果 M 远小于 N，快速排序将运行在最佳状态，合并排序对于特定数组大小运行相同不管密钥分配如何，这里的 M 是做什么用的？

标签： algorithmsortingquicksortmergesort

Answer 1

必须小心实施快速排序以避免病态情况。随机选择枢轴是避免排序数组的二次时间复杂度的好方法，但对于具有许多重复元素的数组来说，这还不够。

如果M远小于N，您将有很多重复项。原始算法不能有效地处理重复，这将导致快速排序性能显着下降，因为 Hoare 的原始算法仅在具有所有相同元素的数组上的每个递归级别删除一个元素。

有关实际实现的研究，请参阅此问题，它在具有小范围内随机分布数据的数组上的行为以及如何修复快速排序实现以避免性能下降：基准测试快速排序和合并排序产生合并排序更快