关于快速排序的问题
大家帮忙看一下这两个快速排序，为什么对100000或1000000个数排序时，测试时间会相差这么多，不知道哪里导致这种结果!
首先是比较快的一个程序
#include <iostream>
#include <fstream>
#include "stdlib.h "
#include <ctime>
#include <vector>
using namespace std;
template <class T>
long Partition(T *data, long* link, long low, long high, bool
ascend)
{
long i,j,k;
long thresindex;
bool tmpbool;
thresindex=link[low];
i=low;
j=high;
while(i <j)
{
do {
i++;
if(i> high-1) break;
if(ascend)
tmpbool=data[link[i]] <data[thresindex];
else tmpbool=data[link[i]]> data[thresindex];
} while(tmpbool);
if(i> high-1) { j=high-1; break; }
do {
j--;
if(j <low+1) break;
if(ascend)
tmpbool=data[link[j]]> data[thresindex];
else tmpbool=data[link[j]] <data[thresindex];
} while(tmpbool);
if(j <low+1) { j=low; break; }
if(i <j) {
k=link[i];
link[i]=link[j];
link[j]=k;
}
}
link[low]=link[j];
link[j]=thresindex;
return j;
}
template <class T>
void QuickSort(T* data, long* link, long low, long high, bool
ascend)
{
long mid=0;
if(low <high)
{
mid=high+1;
mid=Partition(data,link,low,mid,ascend);
QuickSort(data,link,low,mid-1,ascend);
QuickSort(data,link,mid+1,high,ascend);
}
}
/***************测试************************************/
void main()
{
long DATANUM=100000;
long *data;
long *link;
long i;
cout < < "Please input the total number of random-generated
digits(default 100000): ";
cin> > DATANUM;
if(DATANUM <1) DATANUM=100000;
data=(long *)malloc(DATANUM*sizeof(long));
link=(long *)malloc(DATANUM*sizeof(long));
/* Create random numbers & initial the index in array "link " */
srand((unsigned)(time(NULL)));
for(i=0;i <DATANUM;i++)
{
data[i]=(rand()*10000+rand())%(DATANUM*2);
link[i]=i;
}
cout < <endl;
/* Sort! Then show how long of the sorting procedure! */
double start,end;
double duration;
start=clock();
QuickSort(&data[0],&link[0],0,DATANUM-1,1);
end=clock();
duration = (double)(end-start);
cout < < "Time elapsed = " < <duration < < " ms!\n ";
}
下面这个就比较慢了：
/************** "qsort.h "****************************/
#include <iostream>
#include <vector>
using namespace std;
template <class T>
void QuickSort(vector <T> &Array,int low,int high)
{
int Part;
if(high> low)
{
Part = Partition(Array,low,high);
QuickSort(Array,low,Part-1);
QuickSort(Array,Part+1,high);
}
}
template <class T>
int Partition(vector <T> &Array,int low,int high)
{
T temp = Array[low];
while(low < high)
{
while((low <high)&&(Array[high] > = temp))
high--;
Array[low] = Array[high];
while((low <high)&&(Array[low] <= temp))
low++;
Array[high] = Array[low];
}
Array[low] = temp;
return low;
}
#include "qsort.h "
#include <time.h>
void main()
{
vector <int> Heap;
vector <int> Quick;
vector <int> Merge;
double Tstart;
double Tend;
double duration;
srand((unsigned)(time(NULL)));
int DATANUM = 100000;//排序个数
for(int i=0;i <DATANUM;i++)
{
Quick.push_back((rand()*10000+rand())%(DATANUM*2));
}
Tstart = clock();
QuickSort(Quick,1,Quick.size()-1);
Tend = clock();
duration = double(Tend-Tstart);
for(i = 1;i <Quick.size();i++)
{
cout < <Quick[i] < < " ";
}
cout < <endl;
cout < < "Quick Time: " < <duration < < "ms " < <endl;
cout < < "END " < <endl < <endl < <endl < <endl;
}
[解决办法]
我做测试了, 但将后一个算法 的 vector 改成了 long[], 然后时间从 1500ms 级别变成了100 ms
