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

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

输入:数组A,整数i(i不大于数组的个数).

输出:数组A中第i小的元素.

期望运行时间:Θ(n).最坏运行时间:Θ(n2).

  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};
     /*返回第5小的元素.*/
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 }

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。