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)

既然都使用了相同的划分策略，为什么quicksort会忽略从0到q-1和q的中间元素+1 到 r 没有包含 q 而合并排序有？

Answer 1

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

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

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

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