首页 > 代码库 > 随即选取主元的快速排序

随即选取主元的快速排序

 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 }

 

随即选取主元的快速排序