c++堆排序设计报告.doc

实验六 堆排序 题目：编制一个利用堆排序进行排序的程序 班级： 计科0906 姓名： 马飞扬 学号： 座机电话号码0622 完成日期： - - 一：需求分析 1：运用堆排序算法对一组数据进行排序后输出。 二：概要设计 进行排序的算法有很多，但堆排序算法是众多算法之中时间复杂度是比较小的。而要实现堆排序必须先将无序的数据组成大顶堆或者小顶堆然后把第一个元素和最后一个元素进行对调即进行“输出”，再调整剩余的n-1个元素为大顶堆或小顶堆，重复上述操作，直至把所有元素都“输出”，这样就完成了堆排序，最后按照由小到大或者由大到小的顺序进行输出就行了。 三：概要设计 #include using namespace std; void heapadjust int*hh,int s,int m ;//建立大顶堆函数 void heapsort int*h,int q ;//堆排序函数 int h[100];//定义待排序数据的存储结构 void main int i 1;// int j 0;//辅助变量 int q 0;//记录当前数据个数 cout 输入待排序数据（-1退出）: endl; cout 第 i 个:;// cin j;// while j! -1 //输入数据 h[i] j; q++; i++; cout 第 i 个:; cin j; heapsort h,q ;//调用堆排序函数 cout 由小到大分别为:;//对排序后的数据循环输出 for i 1;i q;i++ cout h[i] ; cout endl; void heapadjust int*hh,int s,int m //建立大顶堆 int rc 0;//记录当前调整位置的数据大小 int j 0;//控制变量 for j 2*s;j m;s j,j* 2 //j初始化为调整位置的左孩子 rc hh[s]; if j mhh[j] hh[j+1] //有右孩子且右孩子大于左孩子 ++j;//改变j值 if rc hh[j] //无需调整的情况 break; hh[s] hh[j];// hh[j] rc;//换位调整数据和它的某个孩子 void heapsort int*h,int q int i 0;// int a 0;//辅助变量 for i q/2;i 0;--i //从q/2处开始调整 heapadjust h,i,q ;//调用建大堆函数 for i q;i 1;--i //循环调整剩余的元素形成新的大顶堆并不断把最大元素移至相应位置 a h[1]; h[1] h[i]; h[i] a; heapadjust h,1,i-1 ; 四：调试分析 在本次试验中大部分都是在看懂课本上的伪代码之后，用c++的语言翻译了一下 ，但在写大的过程中发现书上的代码有问题，在做了少许的改动之后，程序才能正常运行。在调试时其它地方病没有遇到什么问题。 五：运行结果 六：实验环境 1：window xp 系统下 2:visual c++ 6.0 编程环境 七：实验体会 通过本次试验基本掌握了堆排序算法的思想，把思想化为代码的能力也有了提高，总的来说，收获还可以。但关于排序的算法有很多，所以这方面的内容还要多加练习，体会各种算法的利弊，提高自己的算法设计能力。