您的位置: 首页 > IT文章 > 【算法导论】c++兑现的随机化的快速排序 【算法导论】c++兑现的随机化的快速排序 分类: IT文章 • 2023-03-31 11:12:58 【算法导论】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; }