期望为线性时间的选择算法

浏览数：28 / 时间：2015年06月08日

randomized_select函数的期望运行时间是Θ(n)，这里假设输入数据都是互异的．它返回数组A[p, r]中第ｉ小的元素．该函数最坏情况运行时间为Θ(n²)，即使是找最小元素也是如此，以为在每次划分时可能极不走运地总是按余下的元素中最大的来进行划分，而划分操作需要Θ(n)时间．我们也将看到该算法有线性的期望运行时间，又因为它是随机化的，所以不存在一个特定的会导致其最坏情况发生的输入数据．

输入：数组A，整数ｉ(ｉ不大于数组的个数).

输出：数组A中第ｉ小的元素．

期望运行时间：Θ(n)．最坏运行时间：Θ(n²)．

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 
  5 static int randomized_select(int *, int, int, int);
  6 static int randomized_partition(int *, int, int);
  7 static int partition(int *, int, int);
  8 static int randomd(int, int);
  9 static void swap(int *, int *);
 10 
 11 
 12 int main(int argc, char *argv[])
 13 {
 14 
 15     int mid;
 16     int array[9] = {1,2,4,7,3,5,6,8,12};
　　　　　/*返回第５小的元素．*/
 17     mid = randomized_select(array, 0, 8, 5);
 18     printf("%d\n", mid);
 19     return 0;    
 20 }
 21 
 22 
 23 static int randomized_select(int *A, int p, int r, int i)
 24 {
 25     int q, k;
 26 
 27     if (p == r)
 28         return A[p];
 29 
 30     q = randomized_partition(A, p, r);
 31     k = q - p + 1;
 32 
 33     if (i == k)
 34         return A[q];
 35     else if (i < k)
 36         return randomized_select(A, p, q - 1, i);
 37     else
 38         return randomized_select(A, q + 1, r, i - k);
 39 }
 40 
 41 static int randomized_partition(int *A, int p, int r)
 42 {
 43     int i, temp;
 44     i = randomd(p, r);
 45     swap(A + r, A + i);
 46 /*
 47     temp = A[r];
 48     A[r] = A[i];
 49     A[i] = temp;
 50 */    
 51     return partition(A, p, r);
 52 }
 53 /*划分，跟快速排序一样．*/
 54 static int partition(int *A, int p, int r)
 55 {
 56     int a, i, j, temp;
 57     a = A[r];
 58     i = p - 1;
 59 
 60     for (j = p; j < r; ++j)
 61     {
 62         if (A[j] <= a)
 63         {
 64             ++i;
 65             swap(A + j, A + i);
 66         /*    
 67             temp = A[j];
 68             A[j] = A[i];
 69             A[i] = temp;
 70         */
 71         }
 72 
 73     }
 74 
 75     swap(A + r, A + i + 1);
 76 /*
 77     temp = A[r];
 78     A[r] = A[i + 1];
 79     A[i + 1] = temp;
 80 */
 81     return i + 1;
 82 }
 83 
 84 /*返回特定范围［a, b］内的一个随机数．*/
 85 static int randomd(int a, int b)
 86 {
 87     int q;
 88 
 89     srand((unsigned int)time(NULL));
 90     q = rand()%(b - a + 1) + a;
 91     
 92     return q;
 93 }
 94 
 95 /*交换值．*/
 96 static void swap(int *num1, int *num2)
 97 {
 98     int temp;
 99     temp = *num1;
100     *num1 = *num2;
101     *num2 = temp;
102 }