360云盘不能分享了:八种排序算法效率比较

      总共建立了三种情况，分别是平均排序、最好情况排序、最坏情况排序。第一种情况就是使用了VC6.0下的随机数生成函数输出100000个随机数进行排序；第二种情况是100000个数本身已经按从小到大的顺序排列了；第三种情况就是100000个数全部是按逆序排列。代码如下：

#include#include#include#include#define MAX 100000 void InsSort(int r[],int length){int i,j;for (i=2;i<=length;i++){r[0]=r[i];j=i-1;while(r[0]a[center])swap(a[left],a[center]);if(a[left]>a[right])swap(a[left],a[right]);if(a[center]>a[right])swap(a[center],a[right]);swap(a[center],a[right-1]);return a[right-1];}void insertionsort(int a[],int n){int j,p;int tmp;for(p=1;p<=n;p++){tmp=a[p];for(j=p;j>0&&a[j-1]>tmp;j--)a[j]=a[j-1];a[j]=tmp;}}void qsort(int a[],int left,int right){int i,j;int pivot;if(left+2<=right){pivot=median3(a,left,right);i=left;j=right-1;for(;;){while(a[++i]pivot){}if(i0;j--)for(i=0;ir[i+1]){temp=r[i];r[i]=r[i+1];r[i+1]=temp;}}      //冒泡排序 void ShellInsert(int r[],int length,int delta){int i,j;for(i=1+delta;i<=length;i++)if(r[i]0&&r[0]=r[j])finished=TRUE;else{r[i]=r[j];i=j;j=2*i;}}r[i] =t;}void crt_heap(int r[], int length){int i,n;n=length;for (i=n/2;i>=1;--i)sift(r,i,n);}void HeapSort(int r[],int length){int i,n;int b;crt_heap(r,length);n= length;for (i=n;i>=2;--i){b=r[1];r[1]=r[i];r[i]=b;sift(r,1,i-1);}}       //堆排序 void merge(int a[],int tmparray[],int lpos,int rpos,int rightend){int i,leftend,numelements,tmppos;leftend=rpos-1;tmppos=lpos;numelements=rightend-lpos+1;while(lpos<=leftend && rpos<=rightend)if(a[lpos]<=a[rpos])tmparray[tmppos++]=a[lpos++];elsetmparray[tmppos++]=a[rpos++];while(lpos<=leftend)tmparray[tmppos++]=a[lpos++];while(rpos<=rightend)tmparray[tmppos++]=a[rpos++];for(i=0;i=high+1;j--)num[j+1]=num[j];num[high+1]=num[0];}}        //折半插入排序 void main(){long dwStart,dwStop,runtime;int num[MAX],a[MAX],i,j;dwStart=GetTickCount();srand((unsigned)time(NULL));for(i=0;i
      执行程序是个很漫长的过程，像对于冒泡排序之类的算法，十万个数的排序再好的机器也得算上半天，不过像快速排序之类的算法如果不给予足够多的数据的话，执行时间永远是0毫秒。所以为了测算精确和公平比较，时间长我就慢慢熬吧。。。以下是我用执行完后的结果做成的统计图表（ps：图表中的数据是我在学院机器上的结果，在自己电脑上时间肯定会少许多，就懒得再算一遍了，反正情况都一样~~）：
      结果很明显，快速排序、堆排序、归并排序这三种执行效率最快，不过话说回来，冒泡排序的代码真的是最好写的！看来算法高效代码复杂与算法低下代码简单是个很辩证的关系啊！