各种排序实验报告(共25页).doc
精选优质文档-倾情为你奉上 【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序， 快速排序，基数排序，折半插入排序，直接插入排序。为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计1.堆排序算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素AN看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。程序实现及核心代码的注释： 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;void dpx() /堆排序 int i,temp; cout<<"排序之前的数组为："<<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=temp; head(0,i-1); cout<<"排序之后的数组为："<<endl; output();2.归并排序 算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。程序实现及核心代码的注释：int is21000;void bin(int low,int mid,int high) int i=low,j=mid+1,k=low; while(i<=mid&&j<=high) if(sui<=suj) / 此处为排序顺序的关键，用小于表示从小到大排序 is2k+=sui+; else is2k+=suj+; while(i<=mid) is2k+=sui+; while(j<=high) is2k+=suj+; for(i=low; i<=high; i+) / 写回原数组 sui=is2i;void g(int a,int b) if(a<b) 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; 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、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，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();int K;int find(int i,int j) int temp; bool flag=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; sui=suj; flag=true; 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; 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）任取待排序记录序列中的某个记录作为基准，按照该记录的关键字大小，将整个记录 序列划分为左右两个子序列。 左侧子序列中所有记录的关键字都小于或等于基准记录的关键字。 右侧子序列中所有记录的关键字都大于基准记录的关键字。 取序列第一个记录为枢轴记录，其关键字为Pivotkey；指针low指向序列第一个记录位置（low=1），指针high指向序列最后一个记录位置（High=SeqList.Len） (2) 从high指向的记录开始，向前找到第一个关键字的值小于Pivotkey的记录，将其放到low指向的位置，low+ (3) 从low指向的记录开始，向后找到第一个关键字的值大于Pivotkey的记录，将其放到high指向的位置，high 重复2、3，直到low=high，将枢轴记录放在low（high）指向的位置。（2）程序实现及核心代码的注释：int find(int i,int j) int temp; bool flag=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; sui=suj; flag=true; sui=temp; cout<<"排完 "<<K+<<" 次顺序后的结果"<<endl; output(); return i;void qsort(int low,int high) if(low<high) int mid=find(low,high); qsort(low,mid-1); qsort(mid+1,high); 6.基数排序（1）算法的基本思想 ： 基数排序是属于“分配式排序”，又称“桶子法”，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。 最高位优先法，简称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; 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!=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=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=(low+high)/2; if(temp<sum) high=m-1; else low=m+1; for(j=i; j>high+1; j-) suj=suj-1; suhigh+1=temp; 8.直接插入排序算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。程序实现及核心代码的注释：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; 【三】详细设计程序代码:#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#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,32; /将要排序的数组int ss10000= 372,209,53,942,547,234,645,468,7,83; /将要排序的数组int su10000; /将要排序的数组int N=10; /数组的长度void input() /数组的输入函数 cout<<"请输入要排序的数组的长度N：" cin>>N; cout<<"请输入需要排序的数组："<<endl; for(int i=0; i<N; i+) cin>>ssi;void output() /数组的输出函数 for(int i=0; i<N; i+) cout<<sui<<" " cout<<endl;void head(int i,int m) /堆排序的一个函数 int j; int temp; 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;void dpx() /堆排序 int i,temp; cout<<"排序之前的数组为："<<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=temp; head(0,i-1); cout<<"排序之后的数组为："<<endl; output();int is21000;void bing(int low,int mid,int high) int i=low,j=mid+1,k=low; while(i<=mid&&j<=high) if(sui<=suj) / 此处为排序顺序的关键，用小于表示从小到大排序 is2k+=sui+; else is2k+=suj+; while(i<=mid) is2k+=sui+; while(j<=high) is2k+=suj+; for(i=low; i<=high; i+) / 写回原数组 sui=is2i;void g(int a,int b) if(a<b) int mid=(a+b)/2; g(a,mid); g(mid+1,b); bing(a,mid,b); void gbpx() /归 并 排 序 cout<<"排序之前的数组为："<<endl; output(); g(0,N-1); cout<<"排序之后的数组为："<<endl; output();void xepx() /希 尔 排 序 int i,j,temp; int m=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();void mppx() /冒 泡 排 序 int i,j,k; int temp,min; bool flag; 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();int K;int find(int i,int j) int temp; bool flag=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; sui=suj; flag=true; sui=temp; cout<<"排完 "<<K+<<" 次顺序后的结果"<<endl; output(); return i;void qsort(int low,int high) if(low<high) int mid=find(low,high); qsort(low,mid-1); qsort(mid+1,high); void kspx() /快 速 排 序 K=0; cout<<"排序之前的数组为："<<endl; output(); qsort(0,N-1); cout<<"排序之后的数组为："<<endl; output();void jspx() /基 数 排 序 int i,j,k; int max=0; int a10100; int b10= 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; 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!=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=0; for(i=0; i<10; i+) if(bi!=0) for(j=0; j<bi; j+) suk+=aij; cout<<"第三次排序之后的数组为："<<endl; output();void zbcrpx() /折半插入排序 int i,j,k,m; int low,high,temp; cout<<"排序之前的数组为："<<endl; output(); for(i=1; i<N; i+) temp=sui; low=0; high=i-1; while(low<=high) m=(low+high)/2; if(temp<sum) high=m-1; else low=m+1; for(j=i; j>high+1; j-) suj=suj-1; suhigh+1=temp; cout<<"排序之后的数组为："<<endl; output();void zjcrpx() /直接插入排序 int i,j,k; int temp,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-)
