#include <iostream>
#include <time.h>
using namespace std;
int PARTITION(int A[],int p,int r)
{
int x=A[r];
int i=p;
int j=r;
while (i<j) //当还没相等需要进行的步骤
{
//i前进将不符合的数与主元调换，进而放到合适的位置
while (i<j&&A[i]<=x) //不能加上=因为两端都有=号就可能将相等的数分到两个不懂的集合中
{
i++;
}
if (i<j) //此时A[i]>x
{
int t;
t=A[i];A[i]=A[j];A[j]=t; //实质就是将主元与不符合左边集合的那个数互相交换，这时主元被放在j位置了
j--;
}
//j后退将不符合的数与主元调换，进而放到合适的位置
while (A[j]>=x&&i<j)
{
j--;
}
if (i<j)
{
int t;
t=A[j];A[j]=A[i];A[i]=t; //实质就是将主元与不符合左边集合的那个数互相交换，这时主元被放在i位置了
i++;
}
}
//相等时返回分割线的位置
return i;
}
void QuickSort(int A[],int p,int r) //快速排序
{
if (p<r) //只要有数就能进行快速排序
{
int q;
q=PARTITION(A,p,r);
QuickSort(A,p,q-1); //前半部分进行快速排序
QuickSort(A,q+1,r); //后半部分进行快速排序
}
}
int main()
{
int number[20]={0};
int i;
srand((unsigned)time(NULL));
for(i=0;i<20;i++)
{
number[i]=rand()%100;
cout << number[i] << " ";
}
cout<< endl;
QuickSort(number,0,19);
for(i=0;i<20;i++)
{
cout << number[i] << " ";
}
cout<< endl;
return 0;
}
/*
1.从一端选定主元
2.再从另一端开始前进，当遇到不满足的数，就将其与主元交换
3.此时主元已经到了另一边，再从另外一边开始出发，当遇到不满足的数是，在将其与主元交换
4.重复的交替前进与交换，将不满足的数交换到满足条件的集合中并且主元也在越来越趋于分割线
5.重复2，3，直到前进到一样的位置是停止，停止的那个位置就是分割线
*/