首页 > 代码库 > 随即选取主元的快速排序
随即选取主元的快速排序
1 #include <iostream> 2 using namespace std; 3 #include <stdlib.h> 4 5 #define LEN 12 6 7 int QuickSort(int *arr,int start,int end); 8 int Sort(int *arr,int start,int end); 9 int swap(int &a,int &b);10 11 int main()12 {13 srand(16);14 int A[LEN] = {13,19,9,5,12,8,7,4,21,2,6,11};15 QuickSort(A,0,11);16 for(int i = 0;i < LEN;i++)17 {18 cout<<A[i]<<endl;19 }20 }21 22 int QuickSort(int *arr,int start,int end)23 {24 if(start < end)25 {26 int i = Sort(arr,start,end); //以主元i的位置为界限分割成俩个数组27 QuickSort(arr,start,i -1); 28 QuickSort(arr,i + 1,end);29 }30 return 0;31 }32 33 int Sort(int *arr,int start,int end)34 {35 int piv = rand() % (end + 1 - start) + start; //随机选取主元36 swap(arr[piv],arr[end]);37 //i-j的范围为比主元小的值,j-end的范围为比主元大的值38 int i = start - 1; 39 40 for(int k = start; k < end ; k++) 41 {42 if(arr[k] <= arr[end]) 43 {44 i = i+1;45 swap(arr[i],arr[k]);46 }47 }48 swap(arr[i+1],arr[end]);49 return i+1;50 }51 52 int swap(int &a,int &b)53 {54 int tmp;55 tmp = a;56 a = b;57 b = tmp;58 return 0;59 }
随即选取主元的快速排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。