快速排序的随机化版本

//交换两个元素值，咱们换一种方式，采取引用“&” void swap(int& a , int& b){ int temp = a; a = b; b = temp;}

//返回属于[lo,hi)的随机整数 int rand(int lo,int hi){ int size = hi-lo+1; return  lo+ rand()%size; }

//分割，换一种方式，采取指针a指向数组中第一个元素 int RandPartition(int* data, int lo , int hi){     //普通的分割方法和随机化分割方法的区别就在于下面三行  swap(data[rand(lo,hi)], data[lo]);    int key = data[lo]; int i = lo;     for(int j=lo+1; j<=hi; j++) {  if(data[j]<=key)  {   i = i+1;   swap(data[i], data[j]);  }             }  swap(data[i],data[lo]); return i;}

//逐步分割排序 void RandQuickSortMid(int* data, int lo, int hi){ if(lo<hi) {  int k = RandPartition(data,lo,hi);  RandQuickSortMid(data,lo,k-1);  RandQuickSortMid(data,k+1,hi); }}int main(){ const int N = 100; //此就是上文说所的“极限”测试。为了保证程序的准确无误，你也可以让N=10000。 int *data = new int[N];          for(int i =0; i<N; i++)  data[i] = rand();   //同样，随机化的版本，采取随机输入。     for(i=0; i<N; i++)  cout<<data[i]<<" ";    RandQuickSortMid(data,0,N-1); cout<<endl; for(i=0; i<N; i++)  cout<<data[i]<<" "; cout<<endl;    return 0;}