这个是一个叫做randomized-select的算法,这个算法巧妙地运用了快速排序的特性。同时这个算法的期望时间为O(n).
这是算法导论上的一节内容,为了方便理解,所以就写给出算法的伪代码,并加以解释:
RANDOMIZED-SELECT(A, p, r, i)
1 if(p==r)
2 return A[p];
3 q=RANDOMIZED-PARTITION(A,p,r);
4,k=q-p+1
5 if(i==k)
6 return A[k]
7 if(i<k)
8 return RANDOMIZED-SELECT(A,p,q-1,i);
9 else return RANDMOIZED-SELECT(A,q+1,r,i)
在第三行代码执行之后,将数组A分为两个子数组,分为为A[p,q-1]和A[q+1,r].前一个数组的元素值均小于或者等于A[q],后个数组中的值均大于等于A[q]。第四行是计算A[p,q]中数组元素的个数。第5行是判断A[k]是不是第i小元素,如果是,那就返回。如果不是在第7行到第9行就判断,第i小元素落在哪个子数组中。根据第三行的执行结果,如果i<k。说明落在A[p,q-1]中,若i>k,则说明落在A[q+1,r]中,因为已经知道有k个元素即A[p,q],小于A[q+1,r]中的第i小元素,故所求的元素必为A[q+1,r]中第i-k小元素。上述代码中SANDOMIZED-PARTITION和快速排序中的一样,所以就不给出了。
#include <stdio.h> #include<stdlib.h> int randomized_partition(int *a,int low,int high) {//找到分界点 int pivot=a[low]; while(low<high) { while(low<high&&a[high]>=pivot) high--; a[low]=a[high]; while(low<high&&a[low]<=pivot) low++; a[high]=a[low]; } a[low]=pivot; return low; } int randomized_select(int *a,int low,int high,int i) { if(low==high) return a[low]; int pivot=randomized_partition(a,low,high); int k=pivot-low+1; if(k==i) return a[pivot]; else if(i<k ) return randomized_select(a,low,pivot-1,i); else return randomized_select(a,pivot+1,high,i-k); } int main() { int a[]={1,34,5,16,37,28,9,13,26}; int result=randomized_select(a,0,sizeof(a)/sizeof(int)-1,2); printf("%d\n",result); return 0; }