各种排序实验报告word文档良心出品

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

2、结下性质的完全二叉树：树中任一非叶结点的元素均不大于程序实现及核心代码的注释：for(j=2*i+1; j=m; j=j*2+1)if(j=suj) break; sui=suj;i=j; sui=tem p;/堆排序void dp x()int i,tem p; coutvv排序之前的数组为：vvendl; out pu t();for(i=N/2-1; i=0; i-)head(i,N);for(i=N-1; i0; i-)temp=sui; sui=su0; su0=tem p; head(0,i-1);coutvv排序之后的数组为：vvendl; out pu t();2. 归并排序算

3、法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。程序实现及核心代码的注释：int is21000;void bin(int low,int mid,int high)int i=low,j=mid+1,k=low;while(iv=mid&jv=hig h)if(suiv=suj)/此处为排序顺序的关键，用小于表示从小到大排序is2k+=sui+;elseis2k+=suj+;while(iv=mid) is2k+=sui+;while(jv=high) is2k+=suj+;for(i=low

4、; 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);bin(a,mid,b);3. 希尔排序算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的 逐段分割”而是将分隔某个 增量”的记录组成一个子序列。程序实现及核心代码的注释：while(m)m/=2;if(m!=0)for(i=m; ivN; i+) if(suiv sui-m) temp=sui

5、;for(j=i-m; j=0&( tem pvsuj); j-=m) suj+m=suj;suj+m=tem p;4. 冒泡排序2、然后再将数组的最后一个数与算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小 的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比 较到第一个数，即可得到第一个数是所有数中最小的数;3、倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数, 如此循环到只剩最后两个比较，即得到排好序的一组数。程序实现及核心代码的注释:for(i=0; ivN; i+)flag=true;for(j=0;

6、 jvN-1-i; j+)if(sujsuj+1) temp=suj; suj=suj+1;suj+1=tem p; flag=false;if(flag=true) break;coutvv排序之后的数组为：vvendl;out pu t();int K;int find(int i,int j)int tem p;bool flag=true; tem p=sui;while(ivj)if(flag)while(tem pv=suj) if(i=j) break;if(i=j)break; sui=suj; while(tem p=sui) i+;if(i=j)break;if(i=j)

7、break; suj=sui;flag=false; elsewhile(tem p=sui) i+； if(i=j) break;suj=sui;if(i=j) break;while(tem pv=suj) if(i=j) break; sui=suj; flag=true;for(i=1; ivN; i+) head=sui;for(j=0； jvi； j+)if(headvsuj)for(k=i; kj; k-) suk=suk-1;suj=head; break;for(i=1; iN; i+) head=sui;for(j=0; ji; j+) if(headj; k-) suk=

8、suk-1; suj=head; break;5. 快速排序(1)任取待排序记录序列中的某个记录作为基准，按照该记录的关键字大小，将整个记录 序列划分为左右两个子序列。右侧子序列中所左侧子序列中所有记录的关键字都小于或等于基准记录的关键字。 有记录的关键字都大于基准记录的关键字。取序列第一个记录为枢轴记录，其关键字为Pivotkey;指针low指向序列第一个记录位置(low=1)，指针high指向序列最后一个记录位置( High=SeqList.Len)(2)从high指向的记录开始，向前找到第一个关键字的值小于Pivotkey的记录，将其放到low指向的位置，low+ 从low指向的记录开始

9、，向后找到第一个关键字的值大于Pivotkey的记录， 将其放到high指向的位置，high重复2、3,直到low=high，将枢轴记录放在 low ( high)指向的位置。(2)程序实现及核心代码的注释：int find(int i,int j)int tem p;bool flag=true; temp=sui;while(i=j) break;if(i=j)break; sui=suj; while(tem p=sui) i+;if(i=j) break;if(i=j)break;suj=sui; flag=false;elsewhile(tem p=sui) i+;if(i=j)br

10、eak;suj=sui;if(i=j)break;while(tem pv=suj) if(i=j) break;sui=suj; flag=true;sui=tem p;coutvv排完VVK+VV 次顺序后的结果vvendl; out pu t();return i;void qsort(int low,int high)if(lowvhigh)int mid=find(low,high); qsort(low,mid-1); qsort(mid+1,high);6. 基数排序(1)算法的基本思想 ：基数排序是属于“分配式排序”，又称“桶子法”，它是透过键值的部份资讯，将要排序的元素分配至

11、某些“桶”中，藉以达到排序的作用。最高位优先法，简称 MSD法：先按k1排序分组，同一组中记录，关键码 k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关 键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。（2）程序实现及核心代码的注释：for(i=0; ivN; i+)if(maxvsui) max=sui;aH(sui)bH(sui)+=sui; k=0;for(i=0; ivl0; i+)if(bi!=0) for(j=0; jvbi; j+)suk+=aij;coutvv第一躺排序之后的数组为：endl;out pu t();/第二

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

13、0) for(j=0; jvbi; j+)suk+=aij;7. 折半排序这个查找”算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入, 操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所 需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的程序实现及核心代码的注释：for(i=1; ihigh+1; j-) suj=suj-1; suhigh+1=tem p;8. 直接插入排序算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1

14、起往前搜索的过程中，可以同时后移记录。整个排序过程为进行 n-1趟插入，即:先将序列中的第一个 记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按 关键字非递减有序序列为止。程序实现及核心代码的注释：for(i=1; ivN; i+)head=sui; for(j=0; jvi; j+) if(headj; k-) suk=suk-1; suj=head; break;程序代码：【三】详细设计#include viostream#include vcstdio#include vcstdlib#include valgorithm#include vcmath#de

15、fine H(X) (X%10)#define HH(X) (X%100/10)#define HHH(X) (X/100) using names pace std;/int ss10000= 32,37,64,87,16,12,24,32;将要排序的数组int ss10000= 372,209,53,942,547,234,645,468,7,83;将要排序的数组 int su10000; /将要排序的数组int N=10;/数组的长度void inpu t() /数组的输入函数coutvv请输入要排序的数组的长度 N:;cinN;coutvv请输入需要排序的数组：vvendl; for(

16、int i=0; ivN; i+)cinssi;void out putO/数组的输出函数for(int i=0; ivN; i+) coutvvsuivv; coutvvendl;void head(int i,int m)/ 堆排序的一个函数int j;int tem p;temp=sui;for(j=2*i+1; jv=m; j=j*2+1)if(jvm-1 &(sujvsuj+1) j+;if(tem p=suj) break; sui=suj;i=j; sui=tem p;/堆排序void dp x()int i,tem p;coutvv排序之前的数组为：vvendl;out pu

17、t();for(i=N/2-1; i=0; i-) head(i,N);for(i=N-1; i0; i-)temp=sui; sui=su0; su0=tem p; head(0,i-1);coutvv排序之后的数组为：vvendl; out pu t();int is21000;void bing(int low,int 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) i

18、s2k+=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 gbp x()归并排序coutvv排序之前的数组为: out pu t();g(0,N-1);coutvv排序之后的数组为: out pu t();vvendl;vvendl; void xep x()/希尔排int i,j,tem p; int m=N;vvendl;

19、coutvv排序之前的数组为: out pu t();while(m) m/=2;if(m!=0)for(i=m; ivN; i+) if(suiv sui-m) temp=sui;for(j=i-m; j=0&(tem pvsuj); j-=m) suj+m=suj;suj+m=tem p;coutvv排序之后的数组为：vvendl; out pu t();void mpp x()冒泡排序int i,j,k;int tem p,min; bool flag; coutvv排序之前的数组为：suj+1) temp=suj; suj=suj+1; suj+1=tem p; flag=false;

20、 if(flag=true) break;coutvv排序之后的数组为：vvendl; out pu t();int K;int find(int i,int j)int tem p;bool flag=true; temp=sui;while(ivj)if(flag)while(tem pv=suj)if(i=j) break; if(i=j) break;sui=suj; while(tem p=sui) i+; if(i=j) break; if(i=j) break; suj=sui; flag=false;elsewhile(tem p=sui) i+; if(i=j) break;

21、 suj=sui; if(i=j) break; while(tem pv=suj) if(i=j) break; sui=suj; flag=true;sui=tem p; coutvv排完VVK+VV 次顺序后的结果vvendl; out pu t();return i;void qsort(int low,int high)if(lowvhig h)int mid=find(low,high);qsort(low,mid-1);qsort(mid+1,high); II 快快速排序void ksp x()K=0;coutvv排序之前的数组为：vvendl; out pu t();qsor

22、t(0,N-1);coutvv排序之后的数组为：vvendl; out pu t();II基数排序void jsp x()int i,j,k;int max=0;int a10100;int b10= 0;coutvv排序之前的数组为：vvendl; out pu t();for(i=0; ivN; i+) if(maxvsui) max=sui;aH(sui)bH(sui)+=sui;k=0;for(i=0; ivl0; i+)if(bi!=0) for(j=0; jvbi; j+) suk+=aij; coutvv第一躺排序之后的数组为：vvendl; out pu t();III第二次i

23、f(maxI10=0) return ;for(i=0; ivl0; 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; out pu t();/第三次if(max/100=0) return ;for(i=0; ivl0; i+) bi=0;for(i=0; ivN; i+) aHHH(sui)bHHH(sui)+=sui; k=0;for(i=0; ihigh+1; j-)

24、suj=suj-1; suhigh+1=tem p;coutvv排序之后的数组为: out pu t();vvendl;void zjcrpx() /直接插入排序int i,j,k;int tem p,head;coutvv排序之前的数组为:out pu t();for(i=1; ivN; i+) head=sui; for(j=0; jvi; j+) vvendl;if(headvsuj) for(k=i; kj; k-) suk=suk-1; suj=head; break;coutvv排序之后的数组为：vvendl; out pu t();void jiemian()cout*endi；

25、cout*vvend|cout*endi；1:cout*endi；2:cout*endi；3:cout*endi；4:cout*endi；5:cout*vvend|；7:折半插入排cout*endi；直接插入排cout*endi；9:重新输cout*endi；0:退Xcout*vvendl；int main() system(color 1a); int test;jiemian(); cintest;while(test!=0) for(int i=0;itest;vvendl;vvendl;vvendl;1界面【四】调试结果III 7 C:Use rsh uyu nD esko实验报告,e

26、xb l.c1=堆排序X xx“xx“xX xx“xx“xX xx“xx“xX xxxxxxxxx2堆排序2=归并排序3=希尔排序4：冒泡排序5：快速排序6:基数排序7=折半插入排序8：直接插入排序9：重新输入0：退岀Xx“xx“xx“xxxxxxxxxxxxxxxxx*总、AT T-V T T AT Th T T T-V Th AT T-V T T *7T Th T T T-V T T AT*f 刖/ KKMMKKHi eifl4taeit4fl4teit4fle5teifl4taeit4fl4teit4fle5t4fl4ll卜 KKXKKKXKKKXXKKXXKKXXKKXXKKfB：退岀、斗-1KMKMK：=：常r Ji