第九章 中位数和顺序统计学

9.2 以期望线性时间做选择

上一讲是找出最小值，同时找出最大值最小值，以及找出次小值的问题。随意选择数组中第i小（大）的元素看起来要比找最小值的简单选择问题要复杂一些。但是令人惊奇的是，两种问题的渐近运行时间却是相同的，都是O(n)。算法导论上介绍了一种用来解决选择问题的分治算法，即RANDOMIZED-SELECT算法。本算法以快速排序算法的分割算法为基础，如同在快速排序中一样，此算法的思想也是对输入数组进行递归划分。但与快速排序不同的是，快速排序会递归处理划分的两边，而RANDOMIZED-SELECT只处理划分的某一边。这一差异在算法的分析中就体现出来了：快速排序的期望运行时间是O(nlgn)。而RANDOMIZED-SELECT的期望运行时间为O(n)。下面是RANDOMIZED-SELECT算法：

RANDOMIZED-SELECT(A, p, r, i)  P109

1 if p = r2     then return A[p]3 q ← RANDOMIZED-PARTITION(A, p, r)4 k ← q - p + 15 if i = k6     then return A[q]7 elseif i < k8     then return RANDOMIZED-SELECT(A, p, q - 1, i)9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

RANDOMIZED-SELECT利用了RANDOMIZED-PARTITION程序。所以，本算法也是一个随机算法，因为它的行为部分地由随机数生成器的输出来决定。本算法返回A[p..r]中的第i小的元素。

算法第三行的RANDOMIZED-PARTITION执行之后，数组A[p..r]被划分为两个子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于或等于A[q]，A[q+1..r]中的每个元素都大于A[q]。

第四行计算A[p..r]的元素个数k，即处于低划分区的元素的个数加上一个主元素。然后第五行检查A[q]是不是第i小的元素。如果是，就返回A[q]。否则，算法要确定第i小的元素落在两个子数组A[p..q-1]和A[q+1..r]中的哪一个之中。如果i<k，则在低区，如i>k，则在高区。然后递归选择。

算法的最坏运行时间为O(n2)，即使是要选择最小元素。

《编程之美》中的2.3 寻找发贴“水王”就可以用顺序统计量来解答。

C++代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 void swap(int* x, int* y) 8 { 9     int temp;10     temp = *x;11     *x = *y;12     *y = temp;13 }14 15 inline int random(int x, int y)16 {17     srand((unsigned)time(0));18     int ran_num = rand() % (y - x) + x;19     return ran_num;20 }21 22 int partition(int* arr, int p, int r)23 {24     int x = arr[r];25     int i = p - 1;26     for(int j = p; j < r; j++)27     {28         if (arr[j] <= x)29         {30             i++;31             swap(arr[i], arr[j]);32         }33     }34     swap(arr[i + 1], arr[r]);35     return ++i;36 }37 38 int randomizedpartition(int* arr, int p, int r)39 {40     int i = random(p, r);41     swap(arr[r], arr[i]);42     return partition(arr, p, r);43 }44 45 int randomizedSelect(int* arr, int p, int r, int i)46 {47     if(p == r)48     {49         return arr[p];50     }51     int q = randomizedpartition(arr, p, r);52     int k = q - p + 1;53     if(i == k)54     {55         return arr[q];56     }57     else if(i < k)58     {59         return randomizedSelect(arr, p, q - 1, i);60     }61     else62         return randomizedSelect(arr, q + 1, r, i - k);63 }64 65 int main()66 {67     int arr[] = {
   1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9};68     int i = randomizedSelect(arr, 0, 11, 4);69     cout << i << endl;70     return 0;71 }