各种排序实验报告

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

2、结点的元素。算法的平均时间复杂度为0(N log N)。程序实现及核心代码的注释：for(j=2*i+1; j=m; j=j*2+1)if(j=suj)break;sui=suj;i=j;sui=temp;void dpx()/ 堆排序int i,temp;cout=0; i-)head(i,N);for(i=N-1; i0; i-)temp=sui;sui=su0;su0=temp;head(0,i-1);coutvv排序之后的数组为：vvendl;output();归并排序算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最

3、后并成一组，即排好序的一组数据。程序实现及核心代码的注释：int is21000;void bin(int low,int mid,int high)int i=low,j=mid+1,k=low;while(i=mid&jv=hig h)if(suiv=suj)/此处为排序顺序的关键，用小于表示从小到大排序is2k+=sui+;elseis2k+=suj+;while(iv=mid) is2k+=sui+;while(jv=high)is2k+=suj+;for(i=low; iv=high; i+) / 写回原数组sui=is2i;void g(int a,int b)if(avb)int

4、 mid=(a+b)/2;g(a,mid);g(mid+1,b); bin(a,mid,b);希尔排序算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成 不是简单的 逐段分割”而是将分隔某个 增量”的记录组成一个子序列。程序实现及核心代码的注释:while(m) m/=2;if(m!=0)for(i=m; i=0&( tempsuj); j-=m) suj+m=suj;suj+m=temp;冒泡排序算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小 的数放于两个

5、数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比 较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数3、倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数,如此循环到只剩最后两个比较，即得到排好序的一组数。程序实现及核心代码的注释：for(i=0; isuj+1) temp=suj; suj=suj+1; suj+1=temp; flag=false;if(flag=true) break;vvendl;coutvv排序之后的数组为：output();int K;int find(int i,int j)int temp;

6、bool flag=true; temp=sui;while(ivj)if(flag)while(tempv=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;elsewhile(temp=sui)i+； if(i=j) break;suj=sui;if(i=j)break;while(tempv=suj) j-;if(i=j) break;sui=suj; flag=true;for(i=1; iN; i+)head=sui;

7、 for(j=0; ji; j+)if(headj; k-) suk=suk-1;suj=head;break;for(i=1; ivN; i+)head=sui;for(j=0; jvi; j+)if(headj; k-)suk=suk-1;suj=head;break;快速排序任取待排序记录序列中的某个记录作为基准，按照该记录的关键字大小，将整个记录 序列划分为左右两个子序列。左侧子序列中所有记录的关键字都小于或等于基准记录的关键字。右侧子序列中所有记录的关键字都大于基准记录的关键字。取序列第一个记录为枢轴记录，其关键字为Pivotkey;指针low指向序列第一个记录位置(low=1)，指

8、针high指向序列最后一个记录位置( High=SeqList.Len)(2)从high指向的记录开始，向前找到第一个关键字的值小于Pivotkey的记录，将其放到low指向的位置，low+ 从low指向的记录开始，向后找到第一个关键字的值大于Pivotkey的记录，将其放到high指向的位置，high重复2、3,直到low=high，将枢轴记录放在 low( high)指向的位置。程序实现及核心代码的注释：int find(int i,int j)int temp;bool flag=true; temp=sui; while(ivj)if(flag)while(tempv=suj) j-；

9、 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;elsewhile(temp=sui) i+;if(i=j)break;suj=sui;if(i=j)break;while(tempv=suj)j-；if(i=j)break;sui=suj;flag=true;sui=temp;coutvv1排完vvK+vv 次顺序后的结果vvendl;output();return i;void qsort(int low,int high)if(l

10、owvhigh)int mid=find(low,high);qsort(low,mid-1);qsort(mid+1,high);基数排序(i)算法的基本思想 ：基数排序是属于“分配式排序”，又称“桶子法”，它是透过键值的部份资讯，将要排 序的元素分配至某些“桶”中，藉以达到排序的作用。最高位优先法，简称 MSD法：先按k1排序分组，同一组中记录，关键码 k1相等，再 对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关 键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。（2）程序实现及核心代码的注释：for(i=0; ivN; i+)if(maxsu

11、i) max=sui;aH(sui)bH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0)for(j=0; jbi; j+)suk+=aij;coutvv第一躺排序之后的数组为：vvendl; output();/第二次if(max/10=0)return ;for(i=0; i10; i+)bi=0;for(i=0; iN; i+)aHH(sui)bHH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0)for(j=0; jvbi; j+)suk+=aij;coutvv第二躺排序之后的数组为：vvendl;output();/第三

12、次if(max/100=0)return ;for(i=0; i10; i+)bi=0;for(i=0; iN; i+) aHHH(sui)bHHH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0)for(j=0; jbi; j+)suk+=aij;折半排序算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个查找操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所 需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，这般插入排序的时间复杂度仍为O (n2

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

14、关键字非递减有序序列为止。程序实现及核心代码的注释：for(i=1; iN; i+)head=sui;for(j=0; ji; j+)if(headj; k-)suk=suk-1;suj=head;break;【三】详细设计程序代码：#include viostream#include #include #include valgorithm#include #define H(X) (X%10)#define HH(X) (X%100/10)#define HHH(X) (X/100)using namespace std;int ss10000= 32,37,64,87,16,12,24,

15、32;将要排序的数组int ss10000= 372,209,53,942,547,234,645,468,7,83;将要排序的数组 int su10000; /将要排序的数组 int N=10;/数组的长度void input()/数组的输入函数coutvv请输入要排序的数组的长度 N ：;cinN;coutvv请输入需要排序的数组：vvendl;for(int i=0; ivN; i+) cinssi;void output() /数组的输出函数for(int i=0; ivN; i+) coutvvsuivv;coutvvendl;void head(int i,int m)/ 堆排序的

16、一个函数int j;int temp;temp=sui;for(j=2*i+1; jv=m; j=j*2+1)if(j=suj)break;sui=suj;i=j；sui=temp;void dpx()/ 堆排序int i,temp;coutvv排序之前的数组为：vvendl;output();for(i=N/2-1; i=0; i-)head(i,N);for(i=N-1; i0; i-)temp=sui;sui=su0;su0=temp; head(0,i-1);coutvv排序之后的数组为：vvendl;output();int is21000;void bing(int low,int

17、 mid,int high)int i=low,j=mid+1,k=low;while(iv=mid&jv=high) if(suiv=suj) /此处为排序顺序的关键，用小于表示从小到大排 序is2k+=sui+;elseis2k+=suj+;while(iv=mid) is2k+=sui+;while(jv=high) is2k+=suj+;for(i=low; iv=high; i+) / 写回原数组sui=is2i;void g(int a,int b)if(avb)int mid=(a+b)/2;g(a,mid);g(mid+1,b); bing(a,mid,b);void gbpx

18、()/归 并排序coutvv排序之前的数组为：vvendl; output();g(0,N-1);coutvv排序之后的数组为：vvendl; output();void xepx()/希尔排序int i,j,temp;int m=N;coutvv排序之前的数组为：vvendl;output();while(m)m/=2;if(m!=0)for(i=m; ivN; i+) if(suiv sui-m)temp=sui;for(j=i-m; j=0&(tempvsuj); j-=m) suj+m=suj;suj+m=temp;coutvv排序之后的数组为：vvendl;output();void

19、 mppx() 冒泡排序 int i,j,k;int temp,min;bool flag;coutvv排序之前的数组为：vvendl; output();for(i=0; isuj+1) temp=suj; suj=suj+1; suj+1=temp; flag=false; if(flag=true) break;coutvv排序之后的数组为：vvendl; output();int K;int find(int i,int j)int temp;bool flag=true;temp=sui;while(ivj)if(flag)while(tempv=suj)j-; if(i=j) br

20、eak;if(i=j)break;sui=suj; while(temp=sui) i+； if(i=j) break;if(i=j)break;suj=sui; flag=false;elsewhile(temp=sui) i+; if(i=j) break;suj=sui;if(i=j) break;while(temp=j)break;sui=suj; flag=true;sui=temp;coutvv排完K+次顺序后的结果vvendl; output();return i;void qsort(int low,int high)if(lowvhigh)int mid=find(low,

21、high);qsort(low,mid-1);qsort(mid+1,high);void kspx() 快速排序K=0;coutvv排序之前的数组为：vvendl; output();qsort(0,N-1);cout排序之后的数组为：vvendl; output();void jspx()/基数排序int i,j,k;int max=0;int a10100;int b10= 0;coutvv排序之前的数组为：vvendl; output();for(i=0; ivN; i+)if(maxvsui) max=sui; aH(sui)bH(sui)+=sui;k=0;for(i=0; ivl

22、0; i+)if(bi!=0) for(j=0; jvbi; j+) suk+=aij;coutvv第一躺排序之后的数组为：vvendl; output();/第二次if(max/10=0) return ;for(i=0; ivl0; i+)bi=0;for(i=0; ivN; i+)aHH(sui)bHH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0) for(j=0; jbi; j+) suk+=aij;coutvv第二躺排序之后的数组为：vvendl; output();/第三次if(max/100=0)return ;for(i=0; i10; i+

23、)bi=0;for(i=0; iN; i+)aHHH(sui)bHHH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0) for(j=0; jbi; j+) suk+=aij;coutvv第三次排序之后的数组为：vvendl; output();void zbcrpx() /折半插入排序int i,j,k,m;int low,high,temp;coutvv排序之前的数组为：vvendl; output();for(i=1; ihigh+1; j-) suj=suj-1;suhigh+1=temp;coutvv排序之后的数组为：vvendl; output();void zjcrpx() /直接插入排序int i,j,k;int temp,head;coutvv排序之前的数组为：vvendl; output();for(i=1; ivN; i+)head=sui;for(j=0; jvi; j+)if(headvsuj) for(k=i; kj; k