两种快速排序算法性能的比较

先来看看第一种快速排序算法（QuickSort1）：

#include <iostream>
#include <fstream>
#include <ctime>

#define MAXNUM 1024

using namespace std;

void QuickSort(int A[], int low, int high)
{
if(low>=high)
return;
int first = low;
int last = high;
int key = A[first];//用第一个元素做主元
while(first<last)
{
while(first<last && A[last]>=key)
--last;
A[first] = A[last];//把比key小的元素换到主元前面
while(first<last && A[first]<=key)
++first;
A[last] = A[first];//把比key大的元素换到主元后面

}
A[first] = key;//确定一个元素(主元)的最终位置
QuickSort(A, low, first-1);//比key小的前半部分元素继续进行快排
QuickSort(A, first+1, high);//比key大的后半部分元素继续进行快排
}

int main()
{
clock_t t1, t2;
t1 = clock();

int A[MAXNUM];
int size=0;
int i=0;
fstream in("data.txt");
if(!in)
cout << "Open error!" << endl;
while(!in.eof())
{
in >> A[i];
++i;
}
size = i-1;
in.close();
QuickSort(A, 0, size-1);

for(i=0; i<size; i++)
cout << A[i] << " ";
cout << endl;

t2 = clock();
cout << "TIME: " << (double)(t2-t1)/CLOCKS_PER_SEC << endl;
return 0;
}

再来看看第二种快速排序算法(QuickSort2)：

#include <iostream>
#include <fstream>
#include <ctime>

#define MAXNUM 8000

using namespace std;

//对数组A[]进行就地重排
int Partition(int A[], int p, int r)
{
int x = A[r];//主元
int i = p-1;//不大于主元x的元素下标都不大于i
for(int j=p; j<=r-1; ++j)
{
if(A[j]<=x)
{
i++;
swap(A[i], A[j]);
}
}
swap(A[i+1], A[r]);
return (i+1);
}

//快速排序算法
void QuickSort(int A[], int p, int r)
{
int q;
if(p < r)
{
q = Partition(A, p, r);
QuickSort(A, p, q-1);
QuickSort(A, q+1, r);
}
}

int main()
{
clock_t t1, t2;
t1 = clock();

int A[MAXNUM];
int i=0;
int size = 0;
fstream in("data.txt");
if(!in)
cout << "Open error!" << endl;
while(!in.eof())
{
in >> A[i];
++i;
}
size = i-1;
in.close();
QuickSort(A, 0, size-1);

for(i=0; i<size; ++i)
cout << A[i] << " ";
cout << endl;

t2 = clock();
cout << "TIME: " << static_cast<double>(t2-t1)/CLOCKS_PER_SEC << endl;
return 0;
}

下面是两个程序执行所需要的时间：