各种排序实验报告

1、【一】需求分析课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。【二】概要设计1 .堆排序算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素AN看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)

2、结点的元素。算法的平均时间复杂度为O(NlogN)。程序实现及核心代码的注释：for(j=2*i+1;j<=m;j=j*2+1)(if(j<m-1&&(suj<suj+1)j+;if(temp>=suj)break;sui=suj;i=j;sui=temp;voiddpx()堆排序(inti,temp;cout<<,中F序之前的数组为："<<endl;output();for(i=N/2-1;i>=0;i-)(head(i,N);for(i=N-1;i>0;i-)(temp=sui;sui=su0;su0=t

3、emp;head(0,i-1);cout<<"排序之后的数组为："<<endl;output();2 .归并排序算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。程序实现及核心代码的注释：intis21000;voidbin(intlow,intmid,inthigh)inti=low,j=mid+1,k=low;while(i<=mid&&j<=high)if(sui<=suj)/此处为排序顺序的关键，用小于表示从小

4、到大排序is2k+=sui+;elseis2k+=suj+;while(i<=mid)is2k+=sui+;while(j<=high)is2k+=suj+;for(i=low;i<=high;i+)/写回原数组sui=is2i;voidg(inta,intb)if(a<b)intmid=(a+b)/2;g(a,mid);g(mid+1,b);bin(a,mid,b);3 .希尔排序算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的逐段分割”，而是将分隔某个

5、蹭量”的记录组成一个子序列。程序实现及核心代码的注释：while(m)m/=2;if(m!=0)(for(i=m;i<N;i+)if(sui<sui-m)(temp=sui;for(j=i-m;j>=0&&(temp<suj);j-=m)suj+m=suj;suj+m=temp;4 .冒泡排序算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小

6、的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。程序实现及核心代码的注释：for(i=0;i<N;i+)flag=true;for(j=0;j<N-1-i;j+)(if(suj>suj+1)(temp=suj;suj=suj+1;suj+1=temp;flag=false;if(flag=true)break;cout<<"排序之后的数组为："<<endl;output();intK;intfind(inti,intj)inttemp;boolflag=true;temp=sui

7、;while(i<j)if(flag)while(temp<=suj)j-;if(i>=j)break;if(i>=j)break;sui=suj;while(temp>=sui)i+;if(i>=j)break;if(i>=j)break;suj=sui;flag=false;else(while(temp>=sui)(i+；if(i>=j)break;suj=sui;if(i>=j)break;while(temp<=suj)(j-;if(i>=j)break;sui=suj;flag=true;for(i=1;i&l

8、t;N;i+)(head=sui;for(j=0;j<i;j+)(if(head<suj)(for(k=i;k>j;k-)(suk=suk-1;suj=head;break;for(i=1;i<N;i+)(head=sui;for(j=0;j<i;j+)(if(head<suj)(for(k=i;k>j;k-)(suk=suk-1;suj=head;break;5.快速排序(1)任取待排序记录序列中的某个记录作为基准，按照该记录的关键字大小，将整个记录序列划分为左右两个子序列。左侧子序列中所有记录的关键字都小于或等于基准记录的关键字。右侧子序列中所有记

9、录的关键字都大于基准记录的关键字。取序列第一个记录为枢轴记录，其关键字为Pivotkey;指针low指向序列第一个记录位置(low=1),指针high指向序列最后一个记录位置(High=SeqList.Len)(2)从high指向的记录开始，向前找到第一个关键字的值小于Pivotkey的记录，将其放到low指向的位置，low+从low指向的记录开始，向后找到第一个关键字的值大于Pivotkey的记录，将其放到high指向的位置，high重复2、3,直到low=high,将枢轴记录放在low(high)指向的位置。(2)程序实现及核心代码的注释：intfind(inti,intj)inttemp

10、;boolflag=true;temp=sui;while(i<j)(if(flag)(while(temp<=suj)(j-;if(i>=j)break;if(i>=j)break;sui=suj;while(temp>=sui)(i+;if(i>=j)break;if(i>=j)break;suj=sui;flag=false;else(while(temp>=sui)(i+;if(i>=j)break;suj=sui;if(i>=j)break;while(temp<=suj)(j-;if(i>=j)break;su

11、i=suj;flag=true;sui=temp;cout<<"排完"<<K+<<"次顺序后的结果"<<endl;output();returni;voidqsort(intlow,inthigh)(if(low<high)(intmid=find(low,high);qsort(low,mid-1);qsort(mid+1,high);6.基数排序（1）算法的基本思想：基数排序是属于“分配式排序”，又称“桶子法”，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。最高位优

12、先法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。(2)程序实现及核心代码的注释：for(i=0;i<N;i+)(if(max<sui)max=sui;aH(sui)bH(sui)+=sui;k=0;for(i=0;i<10;i+)(if(bi!=0)(for(j=0;j<bi;j+)(suk+=aij;cout<<"第一躺排序之后的数组为："<<endl;outpu

13、t();/第二次if(max/10=0)return;for(i=0;i<10;i+)bi=0;for(i=0;i<N;i+)(aHH(sui)bHH(sui)+=sui;k=0;for(i=0;i<10;i+)(if(bi!=0)(for(j=0;j<bi;j+)(suk+=aij;cout<<“第二躺排序之后的数组为："<<endl;output();/第三次if(max/100=0)return;for(i=0;i<10;i+)bi=0;for(i=0;i<N;i+)(aHHH(sui)bHHH(sui)+=sui;k

14、=0;for(i=0;i<10;i+)(if(bi!=0)(for(j=0;j<bi;j+)(suk+=aij;7 .折半排序算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个查找操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，这般插入排序的时间复杂度仍为O(n2)。程序实现及核心代码的注释：for(i=1;i<N;i+)temp=sui;low=0;high=i=1;while(low<=high)(m

15、=(low+high)/2;if(temp<sum)high=m-1;elselow=m+1;for(j=i;j>high+1;j-)suj=suj-1;suhigh+1=temp;8 .直接插入排序算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。程序实现及核心代码的注释：for(i=1;i

16、<N;i+)head=sui;for(j=0;j<i;j+)(if(head<suj)(for(k=i;k>j;k-)(suk=suk-1;suj=head;break;【三】详细设计程序代码：#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cmath>#defineH(X)(X%10)#defineHH(X)(X%100/10)#defineHHH(X)(X/100)usingnamespacestd

17、;/intss10000=32,37,64,87,16,12,24,32;膈要排序的数组intss10000=372,209,53,942,547,234,645,468,7,83;将要排序的数组intsu10000;/路要排序的数组intN=10;/数组的长度voidinput()数组的输入函数cout<<”请输入要排序的数组的长度N:"cin>>N;cout<<”请输入需要排序的数组："<<endl;for(inti=0;i<N;i+)cin>>ssi;voidoutput()数组的输出函数for(int

18、i=0;i<N;i+)cout<<sui<<""cout<<endl;voidhead(inti,intm)堆排序的一个函数intj;inttemp;temp=sui;for(j=2*i+1;j<=m;j=j*2+1)if(j<m-1&&(suj<suj+1)j+；if(temp>=suj)break;sui=suj;i=j;sui=temp;voiddpx()堆排序(inti,temp;cout<<"排序之前的数组为："<<endl;output(

19、);for(i=N/2-1;i>=0;i-)(head(i,N);for(i=N-1;i>0;i-)(temp=sui;sui=su0;su0=temp;head(0,i-1);cout<<"排序之后的数组为："<<endl;output();intis21000;voidbing(intlow,intmid,inthigh)(inti=low,j=mid+1,k=low;while(i<=mid&&j<=high)if(sui<=suj)/此处为排序顺序的关键，用小于表示从小到大排序is2k+=sui+

20、;elseis2k+=suj+;while(i<=mid)is2k+=sui+;while(j<=high)is2k+=suj+;for(i=low;i<=high;i+)/写回原数组sui=is2i;voidg(inta,intb)(if(a<b)(intmid=(a+b)/2;g(a,mid);g(mid+1,b);bing(a,mid,b);voidgbpx()归并排序(cout<<"排序之前的数组为："<<endl;output();g(0,N-1);cout<<"排序之后的数组为："&

21、lt;<endl;output();voidxepx()希尔排序(inti,j,temp;intm=N;cout<<"排序之前的数组为："<<endl;output();while(m)(m/=2;if(m!=0)(for(i=m;i<N;i+)if(sui<sui-m)(temp=sui;for(j=i-m;j>=0&&(temp<suj);j-=m)suj+m=suj;suj+m=temp;cout<<"排序之后的数组为："<<endl;output();v

22、oidmppx()冒泡排序(inti,j,k;inttemp,min;boolflag;cout<<"排序之前的数组为："<<endl;output();for(i=0;i<N;i+)(flag=true;for(j=0;j<N-1-i;j+)(if(suj>suj+1)(temp=suj;suj=suj+1;suj+1=temp;flag=false;if(flag=true)break;cout<<"排序之后的数组为："<<endl;output();intK;intfind(inti

23、,intj)(inttemp;boolflag=true;temp=sui;while(i<j)(if(flag)(while(temp<=suj)(j-;if(i>=j)break;if(i>=j)break;sui=suj;while(temp>=sui)(i+；if(i>=j)break;if(i>=j)break;suj=sui;flag=false;else(while(temp>=sui)(i+;if(i>=j)break;suj=sui;if(i>=j)break;while(temp<=suj)(j-;if(i&

24、gt;=j)break;sui=suj;flag=true;sui=temp;cout<<"排完"<<K+<<"次顺序后的结果"<<endl;output();returni;voidqsort(intlow,inthigh)(if(low<high)(intmid=find(low,high);qsort(low,mid-1);qsort(mid+1,high);voidkspx()快速排序(K=0;cout<<"排序之前的数组为："<<endl;outp

25、ut();qsort(0,N-1);cout<<"排序之后的数组为："<<endl;output();voidjspx()基数排序(inti,j,k;intmax=0;inta10100;intb10=0;cout<<"排序之前的数组为："<<endl;output();for(i=0;i<N;i+)if(max<sui)max=sui;aH(sui)bH(sui)+=sui;k=0;for(i=0;i<10;i+)if(bi!=0)for(j=0;j<bi;j+)suk+=aij;

26、cout<<"第一躺排序之后的数组为："<<endl;output();/第二次if(max/10=0)return;for(i=0;i<10;i+)bi=0;for(i=0;i<N;i+)aHH(sui)bHH(sui)+=sui;k=0;for(i=0;i<10;i+)(if(bi!=O)(for(j=0;j<bi;j+)(suk+=aij;coutw”第二躺排序之后的数组为："«endl;output();/第三次if(max/100=0)return;for(i=0;i<10;i+)bi=0;

27、for(i=0;i<N;i+)(aHHH(sui)bHHH(sui)+=sui;k=0;for(i=0;i<10;i+)(if(bi!=O)(for(j=0;j<bi;j+)(suk+=aij;coutw”第三次排序之后的数组为："«endl;output();voidzbcrpx()/脐半插入排序(inti,j,k,m;intlow,high,temp;cout<<"排序之前的数组为："<<endl;output();for(i=1;i<N;i+)(temp=sui;low=0;high=i=1;whil

28、e(low<=high)(m=(low+high)/2;if(temp<sum)high=m-1;elselow=m+1;for(j=i;j>high+1;j-)suj=suj-1;suhigh+1=temp;cout<<"排序之后的数组为："<<endl;output();voidzjcrpx()/直接插入排序(inti,j,k;inttemp,head;cout<<"排序之前的数组为："<<endl;output();for(i=1;i<N;i+)(head=sui;for(j=0;j<i;j+)(if(head<suj)(for(k=i;k>j;k-)(suk=suk-1;suj=head;break;cout<<"排序之后的数组为："<<endl;output();voidjiemian()(cout<<'*'<<endl;cout<<"*”<<endl;cout<<"*<>*”<<endl;cout<<"*<>*”<<