Quicksort 和 Median 使用相同的方法(分而治之)，为什么它们具有不同的渐近行为？
快速排序可能没有使用正确的主元吗？
最佳答案
当您在 Quicksort 中使用方法 partition 时(见链接中的方法)找到中位数，该方法返回位置正确的元素的索引，根据这个位置，你只需要检查包含中位数的选定部分。
例如数组长度为5，则中位数为3。分区方法返回2，因此您只需要检查数组从2到5的上部，而不是像Quicksort那样检查整个数组。
关于algorithm - 快速排序与中值渐近行为，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21718157/