排序小结 c++

2017年02月24日 14点热度 0人点赞 0条评论

/*从平均时间性能而言,快速排序最佳,其所需时间最省,但快速排序在最坏情况下的时间性能不如堆排序和归并排序,而后两者相比较的结果是,在n较大时,归并排序所需时间较堆排序省,但它所需的辅助存储量最多。

基数排序(O(d*n)) 是稳定的内排方法,最试用于n值很大而关键字较小的序列。若关键字也很大,而序列中大多数记录的“最高位关键字”均不同,则亦可先按“最高位关键字”不同将序列分成“小”的子序列,而后进行直接插入排序。

快速排序

#include

#include

#include

#include

using namespace std;

void quicksort(int *a,int low,int high){

       //从小到大排序,从大到小同理

       if(low>=high)return;

       int  t=a[low],i=low,j=high;

       while(i

              while(i

              a[i]=a[j];

              while(i=a[i])i++;

              a[j]=a[i];

              }

              a[i]=t;

              quicksort(a,low,i-1);

              quicksort(a,i+1,high);

}

int main(){

       inta[100];

       srand((unsigned)time(0));

       for(inti=0;i<10;i++)

       a[i]=rand()%1000;

       quicksort(a,0,9);

       for(inti=0;i<10;i++)

       cout<

       return0;

}

堆排序

#include

#include

#include

#include

using namespace std;

void heapadjust(int *a,int s,int m){

       //建大顶堆,小顶堆同理

       intt=a[s],j;

       //下面这个处理非常巧妙

       for(j=2*s;j<=m;j*=2){

              if(j

              if(a[j]<=t)break;

              a[s]=a[j];

              s=j;

              }

              a[s]=t;

}

void heapsort(int *a,int n){

       //从1到n排序

       inti;

       for(i=n/2;i>0;i--)

        heapadjust(a,i,n);

       for(i=n;i>1;i--){

              swap(a[1],a[i]);

              heapadjust(a,1,i-1);

       }

}

int main(){

       inta[100];

       srand((unsigned)time(0));

       for(inti=1;i<11;i++)

       a[i]=rand()%1000;

       heapsort(a,10);

       for(inti=1;i<11;i++)

       cout<

       return0;

}

归并排序

#include

#include

#include

#include

using namespace std;

void Merge(int *a,int* b,int i,int m,intn){

       intk,j;

       memcpy(b+i,a+i,(n-i+1)*sizeof(int));

       for(k=i,j=m+1;i<=m&&j<=n;k++)

              if(b[i]

              elsea[k]=a[j++];

              if(i<=m)memcpy(a+k,b+i,(m-i+1)*sizeof(int));

              elsememcpy(a+k,b+j,(n-j+1)*sizeof(int));

             

}

void Msort(int *a,int* b,int s,int t){

       if(s==t)return;

       intm=(s+t)/2;

       Msort(a,b,s,m);

       Msort(a,b,m+1,t);

       Merge(a,b,s,m,t);

}

Mergesort(int *a,int s,int t){

       int*b=(int*)malloc((t+1)*sizeof(int));

       Msort(a,b,s,t);

       free(b);

}

int main(){

       inta[100];

       srand((unsigned)time(0));

       for(inti=1;i<11;i++)

       a[i]=rand()%1000;

       Mergesort(a,1,10);

       for(inti=1;i<11;i++)

       cout<

       return0;

}

未经允许不得转载!排序小结 c++

update

纸上得来终觉浅, 绝知此事须躬行。