algorithm - 为什么快速排序排除了中间元素而归并排序包含了它？

Question

我正在查看快速排序的实现（来自 CLRS 第 3 版）。我发现数组的递归除法从低索引到中间1，然后再从中间+1到高。

QUICKSORT(A,p,r)
1 if(p < r)
2        q = PARTITION(A,p,r)
3        QUICKSORT(A,p,q-1)
4        QUICKSORT(A,q+1,r)

合并排序的实现如下：

MERGE-SORT(A,p,r)
1 if(p < r)
2       q = (p+r)/2 (floor)
3       MERGE-SORT(A,p,q)
4       MERGE-SORT(A,q+1,r)
5       MERGE(A,p,q,r)

由于它们都使用了相同的划分策略，为什么快速排序忽略中间元素，因为从0到q-1和q+1到r没有q包含在其中，而合并排序有？

标签： algorithmsortingquicksortmergesort

Answer 1

快速排序将所有小于枢轴的元素放在一侧，将所有大于枢轴的元素放在另一侧。在这一步之后，我们知道枢轴的最终位置将在这两者之间，这就是我们放置它的位置，所以我们不需要再次查看它。

因此，我们可以在递归调用中排除枢轴元素。

Mergesort只是选择中间位置，直到稍后才对该元素执行任何操作。无法保证该位置的元素已经在正确的位置，因此我们需要稍后再查看该元素。

因此，我们必须在递归调用中包含中间元素。