#include"iostream"
#include"random"
using namespace std; /*
void Swap(int &a,int &b)
{
int tmp;
tmp=a;
a=b;
b=tmp;
}
*/
//官方给的partition函数
int Partition1(int *data,int start,int end)
{
int index=start+(rand()%(end-start+));
swap(data[index],data[end]);
int small=start-;
for(index=start;index<end;index++)
{
if(data[index]<data[end])
{
small++;
if(index!=small)
swap(data[index],data[small]);
}
}
small++;
swap(data[small],data[end]);
return small;
} //自定义Partition函数
int Partition2(int *data,int start,int end)
{
int value=data[start];
while(start<end)
{
while(start<end)
{
if(data[end]>value)
end--;
else
break;
}
if(start<end)
data[start++]=data[end];
while(start<end)
{
if(data[start]<=value)
start++;
else
break;
}
if(start<end)
data[end--]=data[start];
}
data[start]=value;
return start;
} void QuickSort1(int *data,int start,int end)
{
if(start==end) return; int mid=Partition1(data,start,end);
if(mid>start)
QuickSort1(data,start,mid-);
if(mid<end)
QuickSort1(data,mid+,end);
} void QuickSort2(int *data,int start,int end)
{
if(start==end) return; int mid=Partition2(data,start,end);
if(mid>start)
QuickSort2(data,start,mid-);
if(mid<end)
QuickSort2(data,mid+,end);
}
QuickSort.h
#include"QuickSort.h" void Test1()
{
int data[]={,,,,,,,,,};
cout<<"use QuickSort1:";
QuickSort1(data,,);
for(int i=;i<;i++)
cout<<data[i]<<" ";
cout<<endl;
} void Test2()
{
int data[]={,,,,,,,,,};
cout<<"use QuickSort2:";
QuickSort2(data,,);
for(int i=;i<;i++)
cout<<data[i]<<" ";
cout<<endl;
}
int main()
{
Test1();
Test2();
}
TestQuickSort.cpp