janqii

写了一个快排算法

然后进行了一些修改，随机的选择中轴元素，随机化处理了一下。

对两个算法进行比较，随机产生553k的数据进行排序，分别统计花费的时间。

一开始在windows下，直接 cl 进行编译链接，可执行文件112k，输出分别是 31ms和110ms。

后来偶然使用VC6编译，运行，可执行文件544k，大了432k，输出为94ms和171ms，分别慢了3倍和60+ms。

VS到底做了什么使得效率低了下来？？！！

另外还有一个发现，在数据比较多，随机化处理过的快排算法要比没有处理的快排效率要差很大。印象中好像是应该反过来，期望运行时间应该要优于后者，因为快排的最好的情况下才是O(n*lgn)，而随机化处理过之后期望运行时间是O(n*lgn)。

或者是因为多了随机化操作、数据交换操作和过程调用时间消耗而引起的？

---------------------------------------------------------code--------------------------------------------------------------------

#include<iostream>
#include<cassert>
#include<ctime>
#include<cstdlib>
using namespace std;

void quickSort(int arr[],int p,int r);
int Partition(int arr[],int p,int r);

void random_QuickSort(int arr[],int p,int r);
int random_Partition(int arr[],int p,int r);

inline void swap(int &a,int &b);
void writeFile(string file_name);
void readFile(string file_name,int arr[],int size);
void writeToFile(string file_name,int arr[],int size);

int main()
{
/*int i=-1;
int size=-1;
int *arr=NULL;

cin>>size;
arr=new int[size];

for(i=0;i<size;i++)
{
   cin>>arr[i];
}
quickSort(arr,0,size-1);
for(i=0;i<size;i++)
   cout<<arr[i]<<" ";

delete []arr;*/
const int size=100000;
int arr[size];
int arr2[size];

string in_file="dataIn.txt";
string out_file="dataOut.txt";
string out2_file="dataOut2.txt";

writeFile(in_file);
readFile(in_file,arr,size);
readFile(in_file,arr2,size);

clock_t start=clock();
quickSort(arr,0,size-1);
clock_t end=clock();
double diff=(double)(end-start);
cout<<diff<<endl;

clock_t start2=clock();
// insert_sort_rec(arr2,size-1);
random_QuickSort(arr2,0,size-1);
clock_t end2=clock();
double diff2=(double)(end2-start2);
cout<<diff2<<endl;

writeToFile(out_file,arr,size);
writeToFile(out2_file,arr2,size);
return 0;
}

void quickSort(int arr[],int p,int r)
{
if(p<r)
{
   int q=Partition(arr,p,r);

   quickSort(arr,p,q-1);
   quickSort(arr,q+1,r);
}
}

void random_QuickSort(int arr[],int p,int r)
{
if(p<r)
{
   int q=random_Partition(arr,p,r);
   random_QuickSort(arr,p,q-1);
   random_QuickSort(arr,q+1,r);
}
}

int Partition(int arr[],int p,int r)
{
int key=arr[r];
int i=p-1;
int j=p;

for(j=p;j<r;j++)
{
   if(arr[j]<=key)
   {
    i++;
    swap(arr[i],arr[j]);
   }
}

swap(arr[i+1],arr[r]);

return i+1;
}
int random_Partition(int arr[],int p,int r)
{
srand(time(NULL));
int rd=rand()%(r-p+1)+p;

swap(arr[rd],arr[r]);

return Partition(arr,p,r);
}

inline void swap(int &a,int &b)
{
int tmp=a;
a=b;
b=tmp;
}

void writeFile(string file_name)
{
int i=0;
FILE *fp;

fp=fopen(file_name.c_str(),"w");

if(!fp)
{
   cerr<<"failed to open file"<<endl;
   exit(-1);
}

srand(time(0));

while((i++)<100000)
{
   fprintf(fp,"%d ",rand()%100);
}

fclose(fp);
}

void readFile(string file_name,int arr[],int size)
{
FILE *fp=fopen(file_name.c_str(),"r");

assert(fp!=NULL);

for(int i=0;i<size;i++)
   fscanf(fp,"%d",&arr[i]);

fclose(fp);
}

void writeToFile(string file_name,int arr[],int size)
{
FILE *fp=fopen(file_name.c_str(),"w");
assert(fp!=NULL);

for(int i=0;i<size;i++)
   fprintf(fp,"%d ",arr[i]);

fclose(fp);

}

void insert_sort_rec(int array[],int size)
{
if(size>3)
   insert_sort_rec(array,size-1);

int i=size-1;
int key;

key=array[i];
i--;

while(i>=0 && array[i]>key)
{
   array[i+1]=array[i--];
}

array[i+1]=key;
}