【算法导论】c++兑现的随机化的快速排序

2012-08-08

【算法导论】c++实现的随机化的快速排序随机化的快速排序：#include iostream#include set#include stri

【算法导论】c++实现的随机化的快速排序

随机化的快速排序：

#include <iostream>#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);void random_quick_sort(int * array_list,int left,int right);const int size = 100;//int array_list [] ={2,8,7,1,3,5,6,4};int * array_list;int main(){//const int size = 10;array_list = new int [sizeof(int)*size];srand(0);for(int i=0;i<size;i++){/*随即的填充数组元素*/int ran_num=rand()% size;array_list[i] = ran_num;}random_quick_sort(array_list,0,size - 1);Print();return 0;}void random_quick_sort(int * array_list,int left,int right){if(left >= right){return ;}int index = random_partition(array_list,left,right);random_quick_sort(array_list,left,index - 1);random_quick_sort(array_list,index + 1,right);}/*随机化的快速排序对于输入的元素加入随机化的成分，使之获得较好的平均性能*/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;}

热点排行

C++

【算法导论】c++兑现的随机化的快速排序