各种排序算法的时间耗费比较

各种排序算法的时间耗费比较

//源代码如下：

#include

#include

#include

#include

#include

#include

#define N 100000 //此处宏定义的范围似乎不能超过100000，甚至连100001也会出错using namespace std;

void Show(int *s,int n)

{

for(int i=0;i

cout<

cout<

}

void RandData(int *s,int n)

{

int i;

srand(time(NULL));

for(i=0;i

s[i]=rand()%n;

//Show(s,n);

}

void Swap(int i,int j,int *s)

{

int t;

t=s[i];

s[i]=s[j];

s[j]=t;

}

///////////////////////////////////////////////////////////////////////

//QuickSort

int Partition(int *s,int l,int r)

{

int left=l;//record the left side

int right=r+1;// record the right side

do //为什么这个地方要用do-while而不能用while

{

do left++;while(s[l]>s[left]) ; //using the l's keyword as the main key

do right--;while(s[l]

if(left

Swap(left,right,s);

}while(left

Swap(l,right,s);

return right;

}

void QuickSort(int *s,int l,int r,int n)

{

if(l

{

int mid=Partition(s,l,r);

QuickSort(s,l,mid-1,n);

QuickSort(s,mid+1,r,n);

}

if(r-l+1==n)

{

cout<<"QuickSort: ";

//Show(s,n);

}

}

///////////////////////////////////////////////////////////////////////

//SelectSort

void SelectSort(int *s,int n)

{

int i,j,k;

for(i=0;i

{

k=i;

for(j=i+1;j

if(s[j]

if(k!=i) Swap(k,i,s);

}

cout<<"SelectSort: ";

//Show(s,n);//this line can not put with the prior line .....Example: cout<<"SelectSort: "<

}

///////////////////////////////////////////////////////////////////////

//BubbleSort

void BubbleSort(int *s,int n)

{

int i,j;

for(i=0;i

for(j=0;j

if(s[j]>s[j+1])

Swap(j,j+1,s);

cout<<"BubbleSort: ";

//Show(s,n);

}

///////////////////////////////////////////////////////////////////////

//InsertSort->插入排序

void InsertSort(int *s,int n)

{

int i,j;

int key;

for(i=1;i

{

key=s[i];

for(j=0;j

if(s[j]>key)break;

for(int k=i;k>j;k--)//keep attention about the moving order

s[k]=s[k-1];

s[j]=key;

//Show(s,n);

}

cout<<"InsertSort: ";

}

///////////////////////////////////////////////////////////////////////

//MergeSort

void Merge(int *s,int left,int right,int mid,int n)

{

int i=left;

int j=mid+1;

int temp[N];

int k=0;

while(i

{

//two ways of transfering keywords to temp

while(s[i]

temp[k++]=s[i++];

if(s[i]>=s[j])//

temp[k++]=s[j++];

}

while(j

temp[k++]=s[j++];

while(i

temp[k++]=s[i++];