数据结构课程设计设计说明书内部堆排序算法的实现学生姓名金少伟学号********** 班级信管1101成绩指导教师曹阳数学与计算机科学学院2013年3月15日课程设计任务书2012—2013学年第二学期课程设计名称：数据结构课程设计课程设计题目：内部堆排序算法的实现完成期限：自2013年3 月4日至2013年3 月15 日共 2 周设计内容：堆排序（heap sort）是直接选择排序法的改进，排序时，需要一个记录大小的辅助空间。

n个关键字序列K1，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

（即如果按照线性存储该树，可得到一个不下降序列或不上升序列）。

本课程设计中主要完成以下内容：1.设计堆排序算法并实现该算法。

2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。

3.寻找改进堆排序的方法。

基本要求如下：1.程序设计界面友好；2.设计思想阐述清晰；3.算法流程图正确；4.软件测试方案合理、有效。

指导教师：曹阳教研室负责人：申静课程设计评阅摘要堆排序是直接选择排序法的改进。

本课设以VC++6.0作为开发环境，C语言作为编程语言，编程实现了堆排序算法。

程序运行正确，操作简单，易于为用户接受。

关键词：堆排序；C语言；时间复杂度目录1．课题描述 (1)2. 算法描述 (2)2.1 堆排序描述 (2)2.2 堆排序算法的图示 (2)2.3 堆排序算法 (5)3．算法流程图 (6)4．代码实现 (7)5. 算法分析 (10)6. 测试 (11)总结 (12)参考文献 (13)1．课题描述查找是计算机的一项主要功能，为了查找方便，通常希望计算机中的表是按关键字是有序的。

因为有序的顺序表可采用查找效率较高的折半查找法，而无序的表只能进行顺序查找。

因此排序也就是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

因此，学习和研究各种排序方法是计算机工作者的重要课题之一。

本课题利用简单选择排序中的堆排序方法，通过对用户输入的可以组成堆的数据元素建立大、小根堆，并将其进行排序输出，使其成为一个按关键字排序的有序序列，从而有效地提高了查找的效率。

开发工具：vc++6.02. 算法描述2.1 堆排序描述堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。

堆的定义如下：n个元素的序列（k1,k2,．．．．．．,kn）当且仅当满足下关系时，称之为堆。

ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)若将和此程序对应的一维数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或小不于）其左、右孩子结点的值。

由此，若序列{k1,k2,……,kn}是堆，则堆顶元素必须为序列中n 的元素的最大值。

例如，下列一个序列为堆，对应的完全二叉树如图2.1所示。

{96,83,27,38,11,9}图2.1序列{96,83,27,38,11,9}对应的堆若再输出堆顶的最大值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n 元素中的最大值。

如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。

2.2 堆排序算法的图示一组无序序列：{49,38,65,97,76,13,27,49}堆排序算法的演示过程如图2.2.和图2.3所示：(a) (b)(c)(d)(e)图2.2 建初始堆过程示例（a ） (b)(c) (d)(e)(f)(g) (h)（l ）(m)图2.3输出对元素并调整建新堆的过程2.3 堆排序算法堆排序算法代码如下： Typedef Sqlist HeapType;Void HeapAdjust( HeapType &H,int s,int m)//j 建大顶堆函数 { RC=H.r[s];for(j=2*s;j<=m;j*=2){ if(j<m&&LT(H.r[j].Key,H.r[j+1].Key)++j; If(!LT(RC.Key,H.r[j+1].Key)break; H.r[s]= H.r[j]; S=j;}H.r[s]=RC; }Void HeapSort(HeapType &H)//堆排序函数 { for(i=H.length/2;i>0;--i) HeapAdjust( H, i, H.length) for (i=H.length;i>1;--i){ t=H.r[1]; //交换堆顶元素与堆中最后一个元素 H.r[1] =H.r[i]; H.r[i]=t;HeapAdjust(H,1 ,i-1);}}3．算法流程图建堆过程流程图如图3.1所示：图3.1建堆流程图堆排序流程图如图3.2所示：图3.2堆排序流程图4．代码实现程序源代码：#include<stdio.h>#include<stdlib.h>#include<ctype.h>#define MAX 50//////////数据输入子函数void InputData(int list[]){int i=1;printf("请输入要排序的数据（以-1结束）:\n");//用-1表示数据输入结束，-1不包括在排序数据中scanf("%d",&list[i]);while(list[i]!=-1){i++;scanf("%d",&list[i]);}list[0]=i-1;//list[0]用来放list数组的长度}///////////////////////////////////////////////////void panduan(int list[],int n){ int i=1;for(i=1;i<n;i++){if(isdigit(list[i])==0){printf("序列为非完全数字序列，无法排序。

\n");exit(0);}}}///////////////数据输出子函数void OutputData(int list[],int n){int i=1;printf("排序后的数列是:\n");for(i=1;i<=n;i++){if(i%4==0)printf("\n");printf("%d\t",list[i]);}printf("\n");}///////////////创建大顶堆子函数void HeapAdjust(int list[],int s, int m) {int j, rc;rc=list[s];for(j=2*s;j<m;j*=2){if(j<=m&&(list[j]<list[j+1]))++j;if(rc>=list[j])break;list[s]=list[j];s=j;}list[s]=rc;}////////////堆排序子函数void HeapSort(int list[],int n){int i,t;for(i=n/2;i>0;i--)HeapAdjust(list,i,n);for(i=n;i>1;i--){t=list[1];list[1]=list[i];list[i]=t;HeapAdjust(list,1,i-1);}}/////////界面子函数void UI (){ printf("****************内部堆排序程序**************\n");printf("程序操作如下\n"); printf("********************************************\n");}//////////主函数void main(){UI ();int n;int list[MAX];InputData(list);n=list[0];panduan(list,n);HeapSort(list,n);OutputData(list,n);}5.算法分析对深度为h 的堆，筛选算法中进行的关键字比较次数至多为2(h-1)次，则在建立含n 个元素、深度为h 的堆时，总共进行的关键字比较次数不超过4n 。

而n 个结点的完全二叉树的深度为[log2n]+1，则调整建新堆时调用Heapadjust 过程n-1次，总共进行的比较次数12222()[log ]2(1222(2))224n h h i t n i h n nh -+===+++-=-+∑由此，在最坏的情况下，堆排序的时间复杂度为2n ()O O n （log n ）+理论上已经证明任何一种比较排序算法在最坏的情况下所需做的键比较次数至少是22221[log !]log log (1)log n n xdx n n n e ==--⎰故堆排序算法的任何改进已不可能降低数量级，而只能设法降低复杂度因子。

因此，对算法的改进应从降低 t ( n)开始。

6. 测试运行以上程序，输入合法数据，得到运行界面如图6.1所示：图6.1输入合法数据得到运行界面输入不合法数据，得到运行界面如图6.2所示：图6.2输入不合法数据得到运行界面总结课设过程是一个痛苦并且快乐的过程，痛苦的是在完成他的过程是异常艰苦的，快乐是完成它后的欣慰与喜悦。

通过两周的课程设计，我收获了很多东西，在课程设计的过程中我不仅复习了原来学过的知识，而且我对学过知识的应用以及如何操作也有了一个较全面的理解。

本次课设我主要是应用了所学习的C编程语言和软件，以及数据结构的相关知识，并参考相关书籍以及请教老师和同学，综合起来才完成了这次课程设计。

在课设的过程中我遇到了许多问题，每次当觉得自己多的程序无发进行下去时，同组的伙伴都会鼓励我坚持，后来的事实证明坚持就是胜利，再难的问题只要你勇敢的向他挑战，坚持下去，问题总会被解决的，这也是我在这次课设中收获最大的。

排序是计算机程序设计中极其重要的一部分，是计算机程序设计中的一个重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。