#include <cstdlib>
#include <ctime>
using namespace std;
const int MAX_SIZE=100;
void partition1(int A[],int n,int first,int last,int &mid)//劃分
{
int i=first,j=last,x=A[i];
while(i<j)
{
while(i<j&&A[j]%3!=0)
j--;
if(i<j)
{
A[i]=A[j];i++;
}
while(i<j&&A[i]%3==0)
i++;
if(i<j)
{
A[j]=A[i];
j--;
}
}
A[i]=x;
mid=i;
}
void partition2(int A[],int n,int first,int last,int &mid)//劃分
{
int i=first,j=last,x=A[i];
while(i<j)
{
while(i<j&&A[j]%3!=1)
j--;
if(i<j)
{
A[i]=A[j];i++;
}
while(i<j&&A[i]%3==1)
i++;
if(i<j)
{
A[j]=A[i];
j--;
}
}
A[i]=x;
mid=i;
}
void QuickSort(int A[],int n,int first,int last)//快速排序
{
int middle;
if(first<last)
{
partition1(A,n,first,last,middle);
partition2(A,n,middle+1,last,middle);
}
}
void display(int A[],int n)
{
int i=0;
for(i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
}
int main()
{
int array[MAX_SIZE],i=0,n=1;
srand(time(0));
cout<<"提示:本程序是將壹個整型數組調整為這樣的數組:所有3的倍數在左邊,所有除以 "<<endl;
cout<<"3余1的數放在中間,而所有除以3余2的數放在最右邊.要求算法的時間盡可能少. "<<endl;
cout<<endl<<"數組中元素的值在1~n之間變化,請輸入n的值:";
cin>>n;
for(i=0;i<MAX_SIZE;i++) //插入隨機數
array[i]=rand()%n;
cout<<"排序前："<<endl;
display(array,MAX_SIZE);
QuickSort(array,MAX_SIZE,0,MAX_SIZE-1);
cout<<"排序後："<<endl;
display(array,MAX_SIZE);
system("PAUSE");
return 0;
}
快速排序