课程设计报告内排序算法比较.doc

《数据结构》课程设计报告提交日期： 8月20日 成绩： 指导老师：实验题目： 内排序算法比较问题解析（对问题的分析、理解和解题方法）：1. 伪随机数的产生是由 time. h 头文件,以rand(time(0))为随机种子的函数rand()产生，可以保持数据的无序性2. 生成三种文件，分别保存正序.逆序.和随机产生的数据，并在程序执行过程中可选择用某一文件中的数据3. 用类涵盖六种排序算法的内部操作，并定义数组元素类4. 输入以文件的方式来进行，必须保证对六种排序算法的输入数据是一样且连续的5. 对于比较次数的统计加在比较判断的前边，在判断失败时也能统计到比较次数6. 对于存在递归的快速排序和存在子函数的堆排序的比较次数.移动次数统计采用以引用做函数参数数据结构选择：选用动态数组为内部基本运算结构，外部数据选用文件算法设计：构建动态数组元素类，六种排序操作.输出操作为该类的函数，输入操作包含在构造函数中需求分析：外部数据只可以手动输入随机数的个数程序运行中可选择采用多种文件用各种算法测试多次程序主线：产生正序文件f1.txt，倒序文件f2.txt，并生成三个随机文件f3.txt f4.txt f5.txt。

选择将某一文件导入程序，进行排序，并测试各种算法的移动和比较次数最后对结果进行分析任务分工、进度计划：周一：六种排序算法嵌入各主程序，并进行初步测算周二：主要解决程序文件输入，输出问题和各函数的接口问题周三：对程序进行调整，解决部分错误输出用户手册： 用户需要选择是否生成新的文件，还需要外部输入待排序数组元素个数即可，程序运行中用户可选择用某一文件进行排序测试结果：请输入排序元素个数:10000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)0Bubble:比较次数=9999 移动次数：=0InsertSort:比较次数=9999 移动次数：=19998SSort:比较次数=49995000 移动次数：=29997QSort:比较次数=19998 移动次数：=39996ShellSort:比较次数=120009 移动次数：=240018HeapSort:比较次数=264502 移动次数：=394251是否继续测试:(按任意键继续，按0退出:)1请输入排序元素个数:10000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)1Bubble:比较次数=49995000 移动次数：=149985000InsertSort:比较次数=9999 移动次数：=19998SSort:比较次数=49995000 移动次数：=29997QSort:比较次数=19998 移动次数：=39996ShellSort:比较次数=120009 移动次数：=240018HeapSort:比较次数=264502 移动次数：=394251是否继续测试:(按任意键继续，按0退出:)1请输入排序元素个数:12000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)2Bubble:比较次数=71963151 移动次数：=109210041InsertSort:比较次数=11999 移动次数：=23998SSort:比较次数=71994000 移动次数：=35997QSort:比较次数=19742 移动次数：=38153ShellSort:比较次数=144012 移动次数：=288024HeapSort:比较次数=324068 移动次数：=482526是否继续测试:(按任意键继续，按0退出:)1请输入排序元素个数:13000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)3Bubble:比较次数=84487519 移动次数：=126842301InsertSort:比较次数=12999 移动次数：=25998SSort:比较次数=84493500 移动次数：=38997QSort:比较次数=21614 移动次数：=41570ShellSort:比较次数=156009 移动次数：=312018HeapSort:比较次数=353720 移动次数：=526605是否继续测试:(按任意键继续，按0退出:)1请输入排序元素个数:14000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)4Bubble:比较次数=97891310 移动次数：=146827053InsertSort:比较次数=13999 移动次数：=27998SSort:比较次数=97993000 移动次数：=41997QSort:比较次数=23354 移动次数：=44780ShellSort:比较次数=168011 移动次数：=336022HeapSort:比较次数=383566 移动次数：=571275是否继续测试:(按任意键继续，按0退出:)总结（对所做程序进行分析、评价运行结果、总结遇到的问题及解决办法）：总结：能输出各种算法对同一数组的比较.交换次数，能较直观的比较各种算法在不同情况下的优劣。

遇到如下问题：问题1：快速排序的递归中和堆排序的子函数中比较次数和移动次数无法同时返回解决办法:引用比较次数compare和移动次数move作为函数的参数问题2：在数组很大>10000，正序或逆序时，快速排序堆栈溢出解决办法：在编译器中修改了堆栈上限程序清单：#include#include#includeusing namespace std;class lists{public: int n; void savefile(); lists(); int getlist(int n){return list[n];} void output(); void Bubble(); void InsertSort(); void SSort(); void Sort(int m,int n,int &,int &); void QSort(); void ShellSort(); void Restore(int *tree,const int root,const int n,int &,int &); void HeapSort();private: int *list;};lists::lists(){ int s0; savefile(); cout<<"请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)"<>s0; list=new int[n]; switch(s0){ case 0:{ifstream infile("f1.txt",ios::in); for(int i=0;i>list[i]; infile.close();break;} case 1:{ifstream infile("f2.txt",ios::in); for(int i=0;i>list[i]; infile.close();break;} case 2:{ifstream infile("f3.txt",ios::in); for(int i=0;i>list[i]; infile.close();break;} case 3:{ifstream infile("f4.txt",ios::in); for(int i=0;i>list[i]; infile.close();break;} case 4:{ifstream infile("f5.txt",ios::in); for(int i=0;i>list[i]; infile.close();break;} }}void lists::output(){ for(int i=0;ilist[j+1]){ move+=3; e=list[j]; list[j]=list[j+1]; list[j+1]=e; t=j; } } bound=t; } cout<<"Bubble:比较次数="<点击阅读更多内容