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

《(快速、基数)排序算法的设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三：（快速、基数）排序算法的设计一、实验目的和要求(1)深刻理解排序的定义和各种排序方法的特点，并能灵活运用。(2)掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。(3)了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。二、实验内容和原理（1）设计直接插入排序、冒泡排序、快速排序算法。（2）设计基数排序算法。三、实验环境1.硬件：PC机；2.软件：Windows操作系统、VisualC++6.0四、算法描述及实验步骤1、直接插入排序在要排序的一组数中，假设前面(n-1)[n>=2]个数已经是排 好顺序的，现在要把

2、第n个数插到前面的有序数中，使得这n个数 也是排好顺序的。如此反复循环，直到全部排好顺序。 2、冒泡排序在要排序的一组数中，对当前还未排好序的范围内的全部数，自上 而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较 小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要 求相反时，就将它们互换。 3、快速排序算法通过一趟 扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次 扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只 减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧） 的左边各数都比它小，右边各数

3、都比它大。然后又用同样的方法处理 它左右两边的数，直到基准点的左右只有一个元素为止。4、基数排序算法五、调试过程六、实验结果1、2、3、4、七、总结通过这次实验，对于多种排序有了一定地了解，在这次实验过程中，虽然遇到挺多的困难，但是我还是认真的对待。同时意识到我对这些方面的知识还是了解的不够深刻。附录：1、#includeinta[100];voidinsertsort(intn,inta[]){inti,j;for(i=2;i<=n;i++)if(a[i]

4、(j=i-2;a[0]>n;for(i=1;i<=n;i++){cin>>a[i];}insertsort(n,a);for(i=1;i<=n;i++){cout<#defineswap(x,y,t)((t)=(x),(x)=(y),(y)=(t))constintN=5;voidsort(intb[],intcount);intmain(){inta[

5、N];cout<>a[i];cout<b[j+1])swap(b[j],b[j+1],tempt);}

6、}for(i=0;itemplatevoidquick_sort(Ta[],intp,intr){if(pintpartition(Ta[],intp,intr){inti=p,j=r+1;Tx=a[p];while(true){while(a[++i]

7、e(a[--j]>x);if(i>=j)break;swap(a[i],a[j]);}swap(a[j],a[p]);returnj;}templatevoidswap(T&a,T&b){Ttemp;temp=a;a=b;b=temp;}intmain(){int*a=newint[10];cout<<"请输入10个数：";for(inti=0;i<10;i++)cin>>a[i];quick_sort(a,0,9);for(intj=0;j<10;j++)cout<

8、tream.h>voidjishu(int*a){int**b=newint*[10];inti,k;for(i=0;i<