2022年c排序算法 .pdf

1.稳定性比较插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的选择排序、希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为O(n2) 其它非线形排序的时间复杂性为O(nlog2n) 线形排序的时间复杂性为O(n); 3.辅助空间的比较线形排序、二路归并排序的辅助空间为O(n), 其它排序的辅助空间为O(1); 4.其它比较插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。宜用归并排序。当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。1,大家都知道的冒泡排序: i nclude i nclude using namespace std; template 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - void swap(type x,int,int); template void BubbleSort(type x,int); int main() srand(time(0); const int n=10; int xn; for(int i=0;i x i=rand()%99; for(int i=0;i cout BubbleSort(x,n); coutnAfter Sort: for(int i=0;i cout =0;i-) int flag=0; for(int j=0;j if(x jx j+1) swap(x,j,j+1); flag=1; if(flag=0) return; template void swap(type x,int n,int m) int temp=xn; xn=xm; xm=temp; 2,简单的选择排序i nclude i nclude using namespace std; template void swap(type x,int,int); template void SlectSort(type x,int); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - int main() srand(time(0); const int n=10; int xn; for(int i=0;i x i=rand()%99; for(int i=0;i cout SlectSort(x,n); coutnAfter Sort: for(int i=0;i cout system(pause); return 0; template void swap(type x,int n,int m) int temp=xn; xn=xm; xm=temp; template void SlectSort(type x,int n) for(int i=0;i for(int j=i+1;j if(x j swap(x,i,j); 3,插入排序i nclude i nclude using namespace std; template void swap(type x,int,int); template void InsertSort(type x,int); int main() srand(time(0); const int n=10; int xn; for(int i=0;in;i+) x i=rand()%99; for(int i=0;in;i+) cout x i; InsertSort(x,n); coutnAfter Sort:endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - for(int i=0;in;i+) cout x i; system(pause); return 0; template void swap(type x,int n,int m) int temp=xn; xn=xm; xm=temp; template void InsertSort(type x,int n) for(int i=1;i0;j-) if(x jx j-1) swap(x,j,j-1); 4:希尔排序i nclude i nclude using namespace std; template void swap(type x,int,int); template void ShellSort(type x,int); template void ShellSorthelper(type x,int,int); int main() srand(time(0); const int n=10; int xn; for(int i=0;in;i+) x i=rand()%99; for(int i=0;in;i+) cout x i; ShellSort(x,n); coutnAfter Sort:endl; for(int i=0;in;i+) cout x i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - system(pause); return 0; template void swap(type x,int n,int m) int temp=xn; xn=xm; xm=temp; template void ShellSort(type x,int n) for(int i=n/2;i=1;i/=2) for(int j=0;ji;j+) ShellSorthelper(&x j,i,n-j); template void ShellSorthelper(type x,int len,int n) for(int i=len;i0;j-=len) if(x jx j-len) swap(x,j,j-len); 5,快速排序i nclude i nclude using namespace std; template void QuicklySort(type x,int n); template void QuicklySorthelper(type x,int,int); template void swap(type x,int,int); int main() srand(time(0); const int n=10; int x n; for(int i=0;in;i+) x i=rand()%99; for(int i=0;in;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - cout x i; QuicklySort(x,n); coutnAfter Sort:endl; for(int j=0;jn;j+) cout x j; system(pause); return 0; template void QuicklySort(type x,int n) QuicklySorthelper(x,0,n-1); template void QuicklySorthelper(type x,int l,int r) if(rl) swap(x,l,(l+r)/2);/ 尽量找出好的轴值 ; int i=l;int j=r+1;type pivot=xl; while(ipivot & ij); if(ij) swap(x,i,j); while(x+ipivot & ij); if(ij) swap(x,i,j); x i=pivot; QuicklySorthelper(x,l,i-1); QuicklySorthelper(x,i+1,r); template void swap(type x,int n,int m) type temp=xn; xn=xm; xm=temp; 6,归并排序 (2 路 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - i nclude i nclude using namespace std; template void swap(type x,int,int); template void MegicSort(type x,int); template void MegicSorthelper(type x,type y,int,int); template void MegicSortPass(type x,type y,int,int,int); int main() srand(time(0); const int n=10; int xn; for(int i=0;in;i+) x i=rand()%99; for(int i=0;in;i+) cout x i; MegicSort(x,n); coutnAfter Sort:endl; for(int i=0;in;i+) cout x i; system(pause); return 0; template void swap(type x,int m,int n) type temp=xm; xm=xn; xn=temp; template void MegicSort(type x,int n) type *y=new typen; int len=1; while(lenn) MegicSorthelper(x,y,len,n);len*=2; MegicSorthelper(y,x,len,n);len*=2; delete y; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - template void MegicSorthelper(type x,type y,int len,int n) int i; for(i=0;i+2*lenn;i+=2*len) MegicSortPass(x,y,i,i+len,i+2*len); if(i+lenn) MegicSortPass(x,y,i,i+len,n); else for(;in;i+) y i=x i; template void MegicSortPass(type x,type y,int l,int m,int n) int i=l,j=m,k=l; for(;im & jx j) y k=x j+; else y k=x i+; for(;im;i+) y k+=x i; for(;jn;j+) y k+=x j; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -