(快速、基数)排序算法的设计.doc

实验三:(快速、基数)排序算法的设计一、实验目的和要求(1)深刻理解排序的定义和各种排序方法的特点,并能灵活运用。(2)掌握常用的排序方法,并掌握用高级语言实现排序算法的方法。(3)了解各种方法的排序过程及其依据的原则,并掌握各种排序方法的性能的分析方法。二、实验内容和原理(1)设计直接插入排序、冒泡排序、快速排序算法。(2)设计基数排序算法。三、:PC机;:Windows操作系统、VisualC++、算法描述及实验步骤直接插入排序在要排序的一组数中,假设前面(n-1)[n>=2]个数已经是排 好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数 也是排好顺序的。如此反复循环,直到全部排好顺序。 冒泡排序在要排序的一组数中,对当前还未排好序的范围内的全部数,自上 而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较 小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要 求相反时,就将它们互换。 快速排序算法通过一趟 扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次 扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只 减少1。快速排序通过一趟扫描,就能确保某个数(以它为基准点吧) 的左边各数都比它小,右边各数都比它大。然后又用同样的方法处理 它左右两边的数,直到基准点的左右只有一个元素为止。基数排序算法五、调试过程六、实验结果1、2、3、4、七、总结通过这次实验,对于多种排序有了一定地了解,在这次实验过程中,虽然遇到挺多的困难,但是我还是认真的对待。同时意识到我对这些方面的知识还是了解的不够深刻。附录:1、#include<>inta[100]; voidinsertsort(intn,inta[]){ inti,j; for(i=2;i<=n;i++) if(a[i]<a[i-1]) { a[0]=a[i]; a[i]=a[i-1]; for(j=i-2;a[0]<a[j];j--) a[j+1]=a[j]; a[j+1]=a[0]; } }intmain(){ intn,i; cin>>n; for(i=1;i<=n;i++){ cin>>a[i]; } insertsort(n,a);for(i=1;i<=n;i++){cout<<a[i]<<"";} return0;}2、#include<>#defineswap(x,y,t)((t)=(x),(x)=(y),(y)=(t))constintN=5;voidsort(intb[],intcount);intmain(){inta[N];cout<<endl;cout<<"请输入:";for(inti=0;i<N;i++)cin>>a[i];cout<<endl;cout<<"输出过程:";for(i=0;i<N;i++)cout<<""<<a[i];cout<<endl;cout<<"输出结果:";sort(a,N);return0;}voidsort(intb[],intn){intt,tempt;for(inti=0;i<n;i++){t=n-i-1;for(intj=0;j<t;j++){if(b[j]>b[j+1])swap(b[j],b[j+1],tempt);}}for