#include <iostream>
#include<stdlib.h>
#include<time.h>
#define NUMBER 10
using namespace std;
void exchange(int &a,int &b)//交换两输
{
int temp;
temp=a;
a=b;
b=temp;
}
int random_patition(int *A,int p,int r)//p是起始下标 r是结束下标
{
int temp;//临时变量
int i=p-1;//起始
int k= p + rand()%(r -p +1);//产生随机数组下标
exchange(A[r],A[k]);//仍然将随机的数交换到最后
temp=A[r];
for(int j=p;j<=r-1;j++)
{
if(A[j]<=temp)
{
i=i+1;
exchange(A[i],A[j]);
}
}
exchange(A[i+1],A[r]);//最后主元交换
return i+1;
}
void QuickSort(int *A,int p,int q)//递归
{
if(p<q){
int r = random_patition(A, p, q);
QuickSort(A, p, r-1);
QuickSort(A, r+1, q);
}
}
int main(void)
{
srand((unsigned)time(NULL));
//clock_t begin_time,end_time; //计时开始与结束
int *p;
p=new int[NUMBER];
for(int k=0;k<NUMBER;k++)
{
p[k]=rand()%NUMBER;
cout << p[k]<<" ";
}
cout<<endl<<endl;
//begin_time=clock(); //开始计时
QuickSort(p,0,NUMBER-1);
//end_time=clock(); //结束时计时
for(int i=0;i<NUMBER;i++)
{
cout<<p[i]<<" ";
}
cout<<endl;
//cout<<endl<<endl<<end_time-begin_time<<" ms"<<endl; //打印使用时间
//cout<<end_time<<endl;
return 0;
}
