好贷网好贷款

排序算法总结

发布时间:2016-12-4 12:07:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"排序算法总结",主要涉及到排序算法总结方面的内容,对于排序算法总结感兴趣的同学可以参考一下。

先写一个下面长要用到的交换函数和比较交换函数: template <class T> inline void CompareExchange(T &a,T &b) { if(a>b) { T temp; temp = a; a = b; b = temp; } } template <class T> inline void Exchange(T &a,T &b) { T temp; temp = a; a = b; b = temp; } 1、冒泡排序     这是最基本的排序方法,代码:  void sort_bubble(int *a,int left,int right) { int i,j; for(i=left;i<right;i++) for(j=right;j>i;j--) ConpareExchange(a[i],a[j]); } 复杂度:    2、直插排序  void sort_insert(int *a,int left,int right) { int temp; int i,j; for(i=right;i>left;i--) CompareExchange(a[i],a[i-1]); for(i=left+2;i<=right;i++) { j=i; temp = a[i]; while(temp<a[j-1]) { a[j]=a[j-1]; j--; } a[j] = temp; } } 3、希尔排序(其中N取3) void sort_shell(int *a,int left,int right) { int increment=right-left+1; int temp; int i,j; while(increment>1) { increment = increment/3+1; for(i=increment+1;i<right-increment;i++) { temp = a[i]; for(j=i-increment;j>0&&temp<a[j];j=j-increment) a[j+increment] = a[j]; a[j+increment] = temp; } } } 4、选择排序(稳定性无法保证) void sort_select(int *a,int left,int right) { int i,j; int min; for(i = left;i<right;i++) { min = i; for(j=i+1;j<=right;j++) { if(a[j]<a[min]) min = j; Exchange(a[i],a[min]); } } } 5、 快速排序(不稳定,但是复杂度低)  void sort_quick(int *a,int left,int right) { if(right<=left) return; int pos=partition(a,left,right); sort_quick(a,left,pos-1); sort_queck(a,pos+1,right); }   int partition(int *a,int left,int right) { int i=left-1,j=right; int e=a[right]; while(1) { while(a[++i]<=e); while(e<=a[--j]) if(j==left) break; if(i>=j) break; Exchange(a[i],a[j]); } Exchange(a[i],a[right]); return i; } 快排在数组待排序数数量少的时候,比起直插排序反而相对劣势,所以为了避免出现这种劣势,在实际应用中,快排对于小于一个阈值M的数组直接跳过,而对这部分采用直插排序! 6、归并排序 void merge(int *a,int p1,int p2,int p3) { int i,j,k; int *c=new int[p3-p1+1]; for(i=p1,j=p2,k=0;k<p3-p1+1;k++) { if(i==p2){c[k]=a[j];j++;continue;} if(j==p3+1){c[k]=a[i];i++;continue;} c[k]=(a[i]<a[j])?a[i++]:a[j++]; } for(k=0;i<p2-p1+1;k++) { a[p2+k]=c[k]; } }   void sort_merge(int *a;int left,int right) { int i,t; for(t=1;t<right-left;t=t+t) for(i=left;i<right-m;i+=m+m) merge(a,i,i+m,min(i+m+m-1,right)); }  7、堆排序 void HeapAdjust(int *a,int p1,int p2) { int temp,j; temp=a[p1]; for(j=2*p1;j<=p2;j*=2) { if(j<p2 && a[j]<a[j+1]) ++j; if(temp==a[j]) break; a[p1]=a[j]; p1=j; } a[p1]=temp; }   void HeapSort(int *a,int left,int right) { int i,N=right-left; for(i=(N-1)/2;i>0;i--) HeapAdjust(a,i,N); while(N>0) { Exchange(a[0],a[N]); N--; HeapAdjust(a,0,N); } }

上一篇:18 Command Line Tools to Monitor Linux Performance
下一篇:ffmpeg如何转化YUV420p格式为其它视频格式

相关文章

关键词: 排序算法总结

相关评论