//Download by http://www.NewXing.com
#include<iostream>
#include<ctime>
using namespace std;
//数组的第一个元素就不参与到排序中,即测试数据的第一个记录不参与排序
//为数组的第一个元素r[0]留作他用
//快速排序
//快速排序一次划分函数
int compare(0),move(0);
int Partition(int r[],int low,int high)
{
r[0]=r[low];
while(low<high)
{
while(low<high&&r[high]>=r[0])
{
--high;
compare++;
}
r[low]=r[high];
move++;
while(low<high&&r[low]<=r[0])
{
++low;
compare++;
}
r[high]=r[low];
move++;
}
r[low]=r[0];
return low;
}
//快速排序递归函数
void QuickSort(int r[],int first,int end)
{
int pivot;
if(first<end)
{
pivot=Partition(r,first,end);
QuickSort(r,first,pivot-1);
QuickSort(r,pivot+1,end);
}
}
void main()
{
int i;
cout<<"快速排序测试:"<<endl;
cout<<endl;
cout<<"测试数据为正序:"<<endl;
int quick1[10]={10,20,30,40,50,60,70,80,90,100};
cout<<"排序前:"<<endl;
for(i=1;i<10;i++)
cout<<quick1[i]<<' ';
cout<<endl;
QuickSort(quick1,0,9);
cout<<"比较次数:"<<compare<<endl;
cout<<"移动次数:"<<move<<endl;
compare=0;
move=0;
cout<<"排序后:"<<endl;
for(i=1;i<10;i++)
cout<<quick1[i]<<' ';
cout<<endl;
cout<<endl;
cout<<"测试数据为逆序:"<<endl;
int quick2[10]={111,99,88,77,66,55,44,33,22,11};
cout<<"排序前:"<<endl;
for(i=1;i<10;i++)
cout<<quick2[i]<<' ';
cout<<endl;
QuickSort(quick2,0,9);
cout<<"比较次数:"<<compare<<endl;
cout<<"移动次数:"<<move<<endl;
compare=0;
move=0;
cout<<"排序后:"<<endl;
for(i=1;i<10;i++)
cout<<quick2[i]<<' ';
cout<<endl;
cout<<endl;
cout<<"测试数据为随机数据:"<<endl;
srand((unsigned)time(NULL));
int random[10];
for(i=1;i<10;i++)
random[i]=rand()%20;
cout<<"排序前:"<<endl;
for(i=1;i<10;i++)
cout<<random[i]<<' ';
cout<<endl;
QuickSort(random,0,9);
cout<<"比较次数:"<<compare<<endl;
cout<<"移动次数:"<<move<<endl;
compare=0;
move=0;
cout<<"排序后:"<<endl;
for(i=1;i<10;i++)
cout<<random[i]<<' ';
cout<<endl;
cout<<endl;
cout<<"快速排序结束。"<<endl;
cout<<endl;
}
/*#include<iostream>
#include<ctime>
using namespace std;
//(只要有哨兵)数组的第一个元素就不参与到排序中,换言之测试数据的第一个记录不参与排序
//不过插入排序的正序排列因为不移动元素所以无上情况
//有类似情况的:插入排序;希尔排序;冒泡排序;简单选择排序
//快速排序有问题!
//快速排序
//快速排序一次划分函数
int Partition(int r[],int low,int high)
{
r[0]=r[low];
while(low<high)
{
while(low<high&&r[high]>=r[0])
--high;
r[low]=r[high];
while(low<high&&r[low]<=r[0])
++low;
r[high]=r[low];
}
r[low]=r[0];
return low;
}
//快速排序非递归函数
void QuickSort(int r[],int n)
{
int top=-1;//顺序栈并假设无上溢
int low=0,high=n-1;
int i,s[20];
while(low<high||top!=-1)
{
while(low<high)
{
i=Partition(r,low,high);//一次划分
s[++top]=i;//入栈
high=i-1;//high指向左半序列最末记录
}
if(top!=-1)
{
i=s[top--];//出栈
low=i+1;//low指向右半序列起始记录
}
}
}
void main()
{
int i;
cout<<"快速排序测试:"<<endl;
cout<<endl;
cout<<"测试数据为正序:"<<endl;
int quick1[10]={10,20,30,40,50,60,70,80,90,100};
cout<<"排序前:"<<endl;
for(i=1;i<10;i++)
cout<<quick1[i]<<' ';
cout<<endl;
QuickSort(quick1,10);
cout<<"排序后:"<<endl;
for(i=1;i<10;i++)
cout<<quick1[i]<<' ';
cout<<endl;
cout<<endl;
cout<<"测试数据为逆序:"<<endl;
int quick2[10]={111,99,88,77,66,55,44,33,22,11};
cout<<"排序前:"<<endl;
for(i=1;i<10;i++)
cout<<quick2[i]<<' ';
cout<<endl;
QuickSort(quick2,10);
cout<<"排序后:"<<endl;
for(i=1;i<10;i++)
cout<<quick2[i]<<' ';
cout<<endl;
cout<<endl;
cout<<"测试数据为随机数据:"<<endl;
srand((unsigned)time(NULL));
int random[10];
for(i=1;i<10;i++)
random[i]=rand()%20;
cout<<"排序前:"<<endl;
for(i=1;i<10;i++)
cout<<random[i]<<' ';
cout<<endl;
QuickSort(random,10);
cout<<"排序后:"<<endl;
for(i=1;i<10;i++)
cout<<random[i]<<' ';
cout<<endl;
cout<<endl;
cout<<"快速排序结束。"<<endl;
cout<<endl;
}*/