算法与数据结构程设计报告-堆排序.doc
约13页DOC格式手机打开展开
算法与数据结构程设计报告-堆排序,一．设计题目： 堆排序的算法二．运行环境：1、硬件：计算机2、软件：microsoft visual c++6.0三．目的和意义：目的：创建一个大堆，按从大到小顺序输出堆元素，实现堆排序。意义：利用堆排序，即使在最坏情况下的时间复杂度也是o(nlog2n)，相对于快速排序来说，时间复杂度小，这是堆排序的最大优点，可用于...
内容介绍
此文档由会员 20023286 发布
一． 设计题目：
堆排序的算法
二．运行环境：
1、 硬件：计算机
2、 软件：Microsoft Visual C++6.0
三．目的和意义：
目的：创建一个大堆，按从大到小顺序输出堆元素，实现堆排序。
意义：利用堆排序，即使在最坏情况下的时间复杂度也是O(nlog2n)，相对于快速排序来说，时间复杂度小，这是堆排序的最大优点，可用于对若干元素进行排序，加快排序速度。
四．算法设计的基本思想：
堆排序算法设计基本思想：
堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录变得简单。先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区。再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录r[n]交换，由此得到新的无序区r[1..n-1]和有序区r[n]，且满足r[1..n-1].keys≤r[n].key。由于交换后新的根R[1]可能违反堆性质，故应将当前无序区r[1..n-1]调整为堆。然后再次将r[1..n-1]中关键字最大的记录r[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区r[1..n-2]和有序区r[n-1..n]，且仍满足关系r[1..n-2].keys≤r[n-1..n].keys，同样要将r[1..n-2]调整为堆。直到无序区只有一个元素为止.
内含流程图和源代码，很完整。
堆排序的算法
二．运行环境：
1、 硬件：计算机
2、 软件：Microsoft Visual C++6.0
三．目的和意义：
目的：创建一个大堆，按从大到小顺序输出堆元素，实现堆排序。
意义：利用堆排序，即使在最坏情况下的时间复杂度也是O(nlog2n)，相对于快速排序来说，时间复杂度小，这是堆排序的最大优点，可用于对若干元素进行排序，加快排序速度。
四．算法设计的基本思想：
堆排序算法设计基本思想：
堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录变得简单。先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区。再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录r[n]交换，由此得到新的无序区r[1..n-1]和有序区r[n]，且满足r[1..n-1].keys≤r[n].key。由于交换后新的根R[1]可能违反堆性质，故应将当前无序区r[1..n-1]调整为堆。然后再次将r[1..n-1]中关键字最大的记录r[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区r[1..n-2]和有序区r[n-1..n]，且仍满足关系r[1..n-2].keys≤r[n-1..n].keys，同样要将r[1..n-2]调整为堆。直到无序区只有一个元素为止.
内含流程图和源代码，很完整。
