【算法导论】线性时间选择---从数组中选择第i小的数
问题：从数组中选择第i小的数，并且要求问题的时间复杂度为O(n)。
代码用到了随机化的快速排序中的分组方法。
其基本原理为：用快速排序的分组方法，随机的选择一个数组元素，使其大于左边的元素，小于右边的元素。然后，看这个元素的下表与要求元素中第i小的值是否相等，如果小于i则表示要查找的元素在当前分组元素的右边，如果大于i表示在左边。这样递归进行，可以达到很高的运行效率。
c++实现的代码如下：
#include <iostream> #include <ctime>#include <set> #include <string> void swap(int * a,int * b); int partition(int * array_list,int left,int right); void Print(); int random_partition(int * array_list,int left,int right); const int size = 8; int random_slelect(int * array_list,int left,int right,int index);int * array_list; int main() { array_list = new int [sizeof(int)*size]; srand((unsigned)time(NULL));for(int i=0;i<size;i++) {/*随机的填充数组元素*/ int ran_num=rand()%( size*10); array_list[i] = ran_num; } Print(); std::cout<<random_slelect(array_list,0,size-1,1);getchar();return 0; } /*从数组中，选择第i小的数*/int random_slelect(int * array_list,int left,int right,int index){int val = 0;if(left == right){val = array_list[left];return val;}int q = random_partition(array_list,left,right);int k = q - left + 1;if(index == k){return array_list[q];}else if( index < k){random_slelect(array_list,left,q-1,index);}else{random_slelect(array_list,q+1,right,index - k);}}/*随机化的快速排序分组方法，对于输入的元素加入随机化的成分，使之获得较好的平均性能*/ int random_partition(int * array_list,int left,int right) { srand(left); int ran_num=( rand())% right; if((ran_num < left )) {/*防止出现因为取模后随机数为0的情况*/ ran_num = left; } /*如果，不交换排序区间内的数据，则成为普通的快速排序*/ swap(&array_list[right],&array_list[ran_num]); return partition(array_list,left,right); } int partition(int * array_list,int left,int right) { int index = left; int pivot = array_list[right]; for(int i= left ; i< right; i++) { if(array_list[i] < pivot) { swap(&array_list[index],&array_list[i]); index ++; } } swap(&array_list[right],&array_list[index]); //Print(); return index; } void swap(int * a,int * b) { int tmp = *a; *a = *b; *b = tmp; } void Print() { for(int i=0;i< size;i++) { std::cout<<array_list[i]<<"\t"; } std::cout<<std::endl; }