当前位置:文档之家› 各种排序算法的时间耗费比较

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

各种排序算法的时间耗费比较//源代码如下:#include<iostream>#include<time.h>#include<stdlib.h>#include<windows.h>#include<stdio.h>#include<algorithm>#define N 100000 //此处宏定义的范围似乎不能超过100000,甚至连100001也会出错using namespace std;void Show(int *s,int n){for(int i=0;i<n;i++)cout<<s[i]<<" ";cout<<endl;}void RandData(int *s,int n){int i;srand(time(NULL));for(i=0;i<n;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;}/////////////////////////////////////////////////////////////////////////QuickSortint Partition(int *s,int l,int r){int left=l;//record the left sideint right=r+1;// record the right sidedo //为什么这个地方要用do-while而不能用while{do left++;while(s[l]>s[left]) ; //using the l's keyword as the main keydo right--;while(s[l]<s[right]) ;if(left<right)Swap(left,right,s);}while(left<right);Swap(l,right,s);return right;}void QuickSort(int *s,int l,int r,int n){if(l<r){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);}}/////////////////////////////////////////////////////////////////////////SelectSortvoid SelectSort(int *s,int n){int i,j,k;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(s[j]<s[k]) k=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: "<<Show(s,n);}/////////////////////////////////////////////////////////////////////////BubbleSortvoid BubbleSort(int *s,int n){int i,j;for(i=0;i<n-1;i++)//just n-1 rounds of comparisionfor(j=0;j<n-i-1;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<n;i++)//start with the second keyword{key=s[i];for(j=0;j<i;j++)if(s[j]>key)break;for(int k=i;k>j;k--)//keep attention about the moving orders[k]=s[k-1];s[j]=key;//Show(s,n);}cout<<"InsertSort: ";}/////////////////////////////////////////////////////////////////////////MergeSortvoid 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<mid+1&&j<right+1){//two ways of transfering keywords to tempwhile(s[i]<s[j]&&i<j&&i<mid+1)//here (i<j) is a must, or it should change to ( if(s[i]<s[j])...)temp[k++]=s[i++];if(s[i]>=s[j])//temp[k++]=s[j++];}while(j<right+1)temp[k++]=s[j++];while(i<mid+1)temp[k++]=s[i++];for(i=left,j=0;i<right+1;i++,j++)s[i]=temp[j];}void MergeSort(int *s,int left,int right,int n){if(left<right){int mid=(left+right)/2;MergeSort(s,left,mid,n);MergeSort(s,mid+1,right,n);Merge(s,left,right,mid,n);}if(right-left+1==n){cout<<"MergeSort: ";//Show(s,n);}}/////////////////////////////////////////////////////////////////////// void Test(int *s){double start,end;int number=10000;while(number<100001){cout<<number<<"个数据:"<<endl;RandData(s,number);start=clock();//记录系统现在的时间,需要的头文件是<time.h> QuickSort(s,0,number-1,number);end=clock();cout<<(end-start)/1000<<endl;//将两个时间做差后即可得到排序所用的时间RandData(s,number);start=clock();sort(&s[0],&s[number]);end=clock();cout<<"sort:"<<(end-start)/1000<<endl;RandData(s,number);start=clock();MergeSort(s,0,number-1,number);end=clock();cout<<(end-start)/1000<<endl;RandData(s,number);start=clock();InsertSort(s,number);end=clock();cout<<(end-start)/1000<<endl;RandData(s,number);start=clock();SelectSort(s,number);end=clock();cout<<(end-start)/1000<<endl;RandData(s,number);start=clock();BubbleSort(s,number);end=clock();cout<<(end-start)/1000<<endl;number+=10000;}}int main(){int s[N];Test(s);return 0;//system("pause");//why the final said that "pause" not found }。

相关主题