《算法技术手册》中值排序

在计算机科学中，分治是一种非常常见的方法，它将一个问题分成两个独立的子问题，每个子问题的规模是原始问题规模的一半。下面让我们来看看中值排序（图4-8），在对一个包含有n≥1个元素的数组A排序时，它交换中值元素A[me]和A的中位元素（第2～4行），将数组分成左右各一半。中值排序然后将左边大于A[mid]的元素和右边小于等于A[mid]的元素互换（第5～8行）。这样将原始数组细分成两个不同的子数组，每一个子数组的大小是原始大小的一半，这两个子数组也同样需要排序。中值排序就这样递归地应用在每一个子数组上（第9～10行）。

在图4-9中，我们一步一步地解释了中值排序的行为，图中的每一行都表示对此算法的一个递归调用。每一步问题的数量都会加倍，但是每一个问题的规模都会减少一半。因为子问题之间都是相互独立的，一旦递归结束，我们也就得到了最终排序的结果。

行1a表示最初的无序数组，中值元素A[me]被用灰色方块标示出来。在行1b中，A[me]和中位元素（黑色方块表示）进行交换，然后大于中值元素的元素（行1b中点左边的灰色方格）和小于等于中值元素的元素（行1b中点右边的灰色方格）互换，得到行1c中的分割后的数组。在递归的每一步，每一个子数组都会被排序，行2a～2c，3a～3c和4a～4c表示了这个过程。

使用环境

使用中值排序的关键在于高效地从无序数组中选择出中值元素。我们先不回答这个问题，我们来看看另一个在计算机科学中非常典型的问题，这个问题最终能够给我们的初始问题一个很好的解决方案。想象一下一个人给了你一个函数p=partition(left,right,pivotIndex)，这个函数将元素A[pivotIndex]作为一个特殊的中枢值，其将数组A[left,right]分成两半，其中一半中所有元素都小于等于中值元素，另一半的所有元素都大于等于中值元素。注意left≤pivotIndex≤right，返回值p是p在子序列A[left,right]的最终位置。例4-3是这个partition函数的C实现。

例4-3：根据给定的中枢值切分数组ar[left，right]的C语言实现

我们是如何通过使用partition更加高效地选择中值呢？首先，让我们看看这个方法的结果，以一个16个元素的无序数组为例。首先第一步是将中枢值和最右边的元素交换。在partition每一次执行循环的时候，关键的变量如图4-10所示。store这个值用来区分执行的是哪一次循环。图4-10中的后继行表示了每一次执行partition的循环都挑选出来了一个A[idx]，这个元素小于或者等于中枢值（在这里是元素“06”）。一旦不再有元素小于或者等于中枢值，store这个位置的元素将会和最右边的元素进行交换，这样安全地将中枢值放到了适当的位置。

partition(0,15,9)执行并且返回p=5，你能看到A[left,p）中的所有元素都小于等于中枢值，反之，A[p+1,right]中的元素都大于等于中枢值。选择出中值元素的过程是怎样的呢？注意到p是在中值在有序数组的最终位置的左侧（标记为“中值位置”的黑色元素）。因此，p的左边没有元素会是中值！我们只需要反复调用partition（这次是一个不同的在A[p+1,right]中的A[pivotIndex]）知道其返回p等于中值位置。

注意到partition高效地将数组组织成两个不同的子数组，但是并没有排序每一个元素。partition返回中枢值的位置p，p能够用来递归地在A[left,right]中检查第k个元素，对于任何1≤k≤right-left+1，如下所示：

如果k=p+1

选择的中值元素是第k个值（回忆一下数组索引是从0开始的，但是这里的k却是从1开始）。

如果k＜p+1

A的第k个元素是A[left,p]的第k个元素。

如果k＞p+1

A的第k个元素是A[p+1,right]的第k-p个元素。

图4-10的目标是确定A的中值位置，或者换句话说，第八大（k=8）的元素。得到了调用partition的返回值p=5，我们下一步递归地在A[p+1,right]中寻找第二大的元素。

这个定义反复地在递归中使用，不过它也能够迭代地在一个循环而不是在一个尾递归函数中定义（可以参考代码库中的这个例子）。selectKth是一个平均时间为线性的函数，给定一个适当的pivotIndex，其返回了数组ar中的第k个元素，例4-4是它的一个实现。

例4-4：selectKth的C语言递归实现

selectKth函数必须为数组A[left,right]选出pivotIndex来在递归中使用。如何选择这里存在多种策略，包括：

·选择第一个位置（左边）或者最后一个位置（右边）。

·选择一个随机位置（left≤random≤right）。

如果多次出现选择了不好的pivotIndex，那么这个函数的性能将会退化成为O(n2)；但是，其最好和平均性能都是线性的，即O(n)。