在O(n)时间内找到数组中的第i小的元素

这个是一个叫做randomized-select的算法，这个算法巧妙地运用了快速排序的特性。同时这个算法的期望时间为O(n).

#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);elsereturn 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;}