北邮数据结构实验报告实验四排序含源码.doc

数据结构实验报告实验名称： 实验4排序学生姓名： 申宇飞班 级： 班内序号： 03学 号： 日 期： 2013年12月18日1实验要求使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2. 程序分析（1）、设计一个菜单，格式如下： 1、直接插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、选择排序 6、堆排序 7、退出（2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。2.1 存储结构2.2 关键算法分析本程序包含了9个函数，它们分别是：（1）、直接插入排序的算法函数InsertSort（）。 void InsertSort(SqList &L)int i,j;for( i=2; i<=L.length;i+)if(L.ri.key < L.ri-1.key)L.r0 = L.ri;L.ri = L.ri-1;for( j=i-2; (L.r0.key < L.rj.key); j-) L.rj+1 = L.rj;L.rj+1 = L.r0;（2）、希尔排序的算法函数ShellSort（）。void ShellSort(SqList &L)int i, j;int dk = 1;/增量while(dk <=L.length/3)dk = 3*dk+1;/增大增量while(dk>0)dk /= 3;/减小增量for (i = dk; i <=L.length; i+) L.r0.key = L.ri.key;j = i;while (j >= dk) && (L.rj-dk.key > L.r0.key) L.rj.key = L.rj-dk.key;j -= dk;L.rj.key = L.r0.key;（3）、冒泡排序算法函数BubbleSort（）。void BubbleSort(SqList &L)int i,j;for(i=0;i<L.length-2;i+)int flag = 1;for(j=0;j<L.length-i-2;j+)if(L.rj.key > L.rj+1.key)flag = 0;int temp;temp = L.rj.key;L.rj.key = L.rj+1.key;L.rj+1.key = temp;/若无交换说明已经有序if(flag=1)break; （4）、快速排序的算法函数Partition（）。void BubbleSort(SqList &L)int i,j;for(i=0;i<L.length-2;i+)int flag = 1;for(j=0;j<L.length-i-2;j+)if(L.rj.key > L.rj+1.key)flag = 0;int temp;temp = L.rj.key;L.rj.key = L.rj+1.key;L.rj+1.key = temp;/若无交换说明已经有序if(flag=1)break; （5）、选择排序算法函数SelectSort（）。void SelectSort(SqList &L)int min;int j;for (int i = 0; i <L.length; i+) / 选择第i小的记录，并交换j = i;min = L.ri.key;for (int k = i; k < L.length; k+) / 在Ri.n-1中选择最小的记录if (L.rk.key < min)min = L.rk.key ;j = k;if (i != j) / 与第i个记录交换int temp = L.ri.key;L.ri.key = L.rj.key;L.rj.key = temp;（6）、堆排序算法函数HeapAdjust（）。 void HeapAdjust(HeapType &H,int s,int m)第6/10页/堆调整，将记录调整为小顶堆 int j;RedType rc = H.rs;/暂时存储根结点for(j=2*s; j<=m; j*=2)/沿着结点记录较小的向下筛选if(j<m && H.rj.key<H.rj+1.key)+j;if(rc.key>= H.rj.key)break;H.rs = H.rj;s = j;H.rs = rc;void HeapSort(HeapType &H)int i;RedType temp;for(i = H.length; i>0; -i)HeapAdjust(H,i,H.length);for(i=H.length; i>1; -i)temp = H.r1;H.r1 = H.ri;H.ri = temp;HeapAdjust(H,1,i-1);（7）、对存储数字的遍历函数Visit（）、初始化函数InitSqList（）。 void Visit(SqList L)for(int i=1; i<=L.length; i+)cout<<L.ri.key<<" "cout<<endl;void InitSqList(SqList &L,int a)for(int i=1;i<=L.length;i+)L.ri.key = ai;（8）、主函数main（）。关键算法的时间、空间复杂度：排序法 平均时间   最差情形      稳定度     额外空间     备注冒泡    O(n2)            O(n2)             稳定         O(1)          n小时较好交换    O(n2)            O(n2)             不稳定     O(1)            n小时较好选择    O(n2)            O(n2)             不稳定     O(1)           n小时较好插入    O(n2)             O(n2)              稳定       O(1)           大部分已排序时较好Shell   O(nlogn)        O(ns) 1<s<2 不稳定    O(1)        s是所选分组快速    O(nlogn)        O(n2)             不稳定      O(nlogn)      n大时较好归并    O(nlogn)      O(nlogn)       稳定         O(1)           n大时较好堆      O(nlogn)     O(nlogn)       不稳定   O(1)           n大时较好2.3 其他3. 程序运行结果主函数流程：主函数main 初始化随机数组快速排序Qsort()冒泡排序BubbleSort()希尔排序ShellSort()直接插入排序InsertSort()堆排序HeapSort() 4. 总结首先，对程序的设计缺少优化，本次程序需要运行之后手动进行输入数据，以后可以尝试把数据改为在源代码中输入，这样就可以运行之后马上显示数据，这样就避免了相同数据的重复输入。此外，生成数组函数及本程序中的代码有的采用了递归形式，如果考虑用栈来模拟的话，效率会有提升，所以运行时间还和代码的实现有关。本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，导致排序的结果以及排序的界面出现了问题，得不到实现。后来对算法进行改进，最终把问题得以解决。而且以后可以试着去写一段可以计算出时间的函数。代码#include<iostream>#include <time.h>#include <windows.h>using namespace std;int i,j,temp,k;/设置全局变量long double GetNowTime() /取系统时间LARGE_INTEGER litmp;LONG64 QPart;QueryPerformanceCounter(&litmp);QPart=litmp.QuadPart;return (long double)QPart;/插入排序void InsertSort(int r, int n) int move=0, compare=0;long double start=0,end=0,time=0;start=GetNowTime();for(i=2;i<n;i+)if(ri<ri-1) /记录后项小于记录前项时进行排序 compare+;r0=ri; /设置哨兵，存放待排序记录值for(j=i-1;r0<rj;j-,compare+) /寻找插入位置rj+1=rj; /比r0大的往后移rj+1=r0; /插入指定记录值move=move+3; /关键码的交换按3次记compare+;end=GetNowTime();time=end-start;for(k=1;k<n;k+)cout<<rk<<" " /输出排序后记录cout<<endl;cout<<"排序所需时间："<<time<<"us 移动次数："<<move<<" 比较次数："<<compare;cout<<endl<<endl;/希尔排序void ShellSort(int r, int n)int move=0,compare=0;long double start=0,end=0,time=0;start=start=GetNowTime();int d; /定义增量 for(d=n/2;d>=1;d=d/2) /以增量为d进行直接插入排序for(i=d+1;i<n;i+)compare+;r0=ri; /设置哨兵，暂存被插入记录for(j=i-d;j>0&&r0<rj;j=j-d,compare+)rj+d=rj; /记录后移d个位置 rj+d=r0; /插入指定记录值 move=move+3;compare+;end=GetNowTime();time=end-start;for(i=1;i<n;i+)cout<<ri<<" " /输出排序后记录cout<<endl; cout<<"排序所需时间："<<time<<"us 移动次数："<<move<<" 比较次数："<<compare;cout<<endl<<endl;/改进型起泡排序void BubbleSort(int r, int n)long double start=0,end=0,time=0;int move=0,compare=0;int exchange;int bound; exchange=n-1; /第一趟起泡排序的范围是r0到rn-1start=GetNowTime();while (exchange) /仅当上一趟排序有记录交换才进行本趟排序bound=exchange; /表示无序的范围exchange=0; for(int j=0;j<bound;j+,compare+) /一趟起泡排序 if (rj>rj+1) temp=rj; /交换ri和ri+1 rj=rj+1; rj+1=temp; move=move+3; exchange=j; /记录每一次发生记录交换的位置，即记录无序区的位置compare+;end=GetNowTime();time=end-start;for(int i=0;i<n;i+) cout<<ri<<" " /输出排序后记录cout<<endl; cout<<"排序所需时间："<<time<<" us 移动次数："<<move<<" 比较次数："<<compare;cout<<endl<<endl;/快速排序一次划分int Emove=0,Ecompare=0;long double Etime;int Partition(int r, int first, int end)i=first; /初始化j=end; while (i<j) /循环的停止条件是i=j while(i<j&&ri<=rj) Ecompare+;j-; /右侧扫描 Ecompare+; if(i<j) temp=ri; /将较小记录交换到前面 ri=rj; rj=temp; Emove=Emove+3; /*i+; */ while(i<j&&ri<=rj) Ecompare+; i+; /左侧扫描，小于轴值的不移动，找到大于轴值的 Ecompare+; if(i<j) temp=rj; rj=ri; ri=temp; /将较大记录交换到后面 Emove=Emove+3; /* j-;*/ return i; /i为轴值记录的最终位置/快速排序，在一次排序结束后，左边区的元素都比右边区的小，只要分开再排序即可void QuickSort(int r,int first,int end2) long double start=0,end=0;start=GetNowTime();if (first<end2) /递归结束int pivot=Partition(r,first,end2); /一次划分 QuickSort(r,first,pivot-1); /递归地对左侧子序列进行快速排序 QuickSort(r,pivot+1,end2); /递归地对右侧子序列进行快速排序end=GetNowTime();Etime=end-start;void Print()cout<<endl<<"排序所需时间："<<Etime<<"us;移动的次数："<<Emove<<"比较的次数："<<Ecompare<<endl<<endl;/简单选择排序,每一趟都找到最小值与比较域内第一个值交换void SelectSort(int r, int n)long double start=0,end=0,time=0;int compare=0,move=0;int index; /设置关键值下标start=GetNowTime(); for(i=0;i<n-1;i+) /对n个记录进行n-1趟简单选择排序index=i;for(j=i+1;j<n;j+,compare+) /在无序区中选取最小记录if(rj<rindex) /有记录小于关键值记录index=j; /更新关键值记录if(index!=i) /若第一个是最小值就不用交换temp=ri; ri=rindex; rindex=temp; /交换ri和关键值记录move=move+3;compare+;end=GetNowTime();time=end-start;for(i=0;i<n;i+) cout<<ri<<" " /输出排序后记录cout<<endl<<"排序所需时间："<<time<<"us 移动次数："<<move<<" 比较次数："<<compare; cout<<endl<<endl;/对数列进行排序void px(int r,int numv)cout<<"n直接顺序排序结果为: " InsertSort(r,numv); cout<<"希尔排序结果为: " ShellSort(r,numv); cout<<"起泡排序结果为: " BubbleSort(r, numv-1); cout<<"快速排序结果为: " QuickSort(r,0,numv-1); for(int i=0;i<numv-1;i+)cout<<ri<<" "Print();Emove=0;Ecompare=0; cout<<"n" cout<<"简单选择排序结果为: " SelectSort(r,numv-1);/主函数int main()const int numv=11; int anumv=0;int bnumv=0;int cnumv=0; /初始化 cout<<"请输入10位正整数."<<endl; cout<<"第一组,正序输入 a= " tryfor(i=1;i<numv;i+)cin>>ai; /从键盘输入待排序记录值catch(char *wrong)cout<<wrong; px(a,numv); /调用排序函数cout<<"n第二组,反序输入 b= " tryfor(i=1;i<numv;i+)cin>>bi; /从键盘输入待排序记录值catch(char *wrong)cout<<wrong; px(b,numv); /调用排序函数cout<<"n第三组,随机输入 c= "tryfor(i=1;i<numv;i+)cin>>ci; /从键盘输入待排序记录值catch(char *wrong)cout<<wrong; px(c,numv); /调用排序函数return 0;