为什么快速排序排除了中间元素，但合并排序包含了它？

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，而mergesort包含？

Answer 1

这两种方法都利用了分割策略，但方式不同

Mergesort（最常见的实现）将数组递归地划分为大小相等（如果可能）的部分，中间索引是固定位置（对于给定的数组长度）。Recrive调用完全处理数组的左部分和右部分。

快速排序分区子例程将数据透视元素放置在所需（最终）位置（在大多数情况下，数据透视索引不在中间）。不需要进一步处理这个元素，递归调用处理该元素之前和之后的片段。

Answer 2

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

因此，我们可以排除递归调用中的pivot元素。

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

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