改进的堆排序算法及其复杂度分析.pdfVIP

维普资讯 西 北 师 范 大 学 学 报 (自然科学版) 第38卷2(}02年第3期 JournalofNorthwestNormalUniversity(NaturalScience) V01．38 2002 N0．3 改进的堆排序算法及其复杂度分析 吴尚智 (西北师范大学 数学与信息科学学院，甘肃 兰州 730070) 摘 要：给 出了传统堆排序算法的改进算法 该算法降低了原算法的复杂度 ，在元素个数较大时，能较明显地提 高算 法的效率 ． 关键词：算法；堆排序；复杂度 中图分类号：TP301．6 文献标识码 ：A 文章编号：1001．988 (2002)03．0024-03 Improvedheapson algorithm anditscomplexityanalysis WU Shang-zhi (CollegeofMathematicsandInformationScience，NorthwestNormalUniversiyt，Lallzhou730070，Gansu，China) Abstract：Anew improvedheapsort~ fihtm isgiven．Comparedwithhteoldone，hteconstantfactorofhte complexityhasbeenreducedandhteefificencyisincreasedhighlywhenhtemountofelementsisbigger． Keywords：algorithm ；heapsort；complexity 法是威洛姆斯 (WilliomsJ)在 1964年提出的… ． l 问题的提 出 堆排序只需要一个记录大小的辅助空间，每个待排 大家都知道，排序 (Sorting)是计算机程序设 序的记录仅 占一个存储空间． 计中的一种重要操作，它的功能是将一个数据元素 定义 1 n个元素的序列 { ， ，…， }当且 (或记录)的任意序列 ，重新排列成一个按关键字 仅当满足下列关系时，称之为堆：K ≤K ，Ki≤ 有序的序列 ．假设含 n个记录的序列为 … 或 K ≥K2，K≥ … ，其 中 i=l，2，…， {R ，R2，…，R }， (1) [n／2]． 其相应的关键字序列为 对深度为 h的堆，筛选算法中进行的关键字 { ， ，…， }， 比较次数至多为2(h—1)次，则在建立含 n个元 需确定 l，2，…，n的一种排序P，P：，…，P^，使其 素、深度为 h的堆时，总共进行的关键字比较次 相应关键字满足如下的非递减 (或非递增)的关系 数不超过4n… ．而 n个结点的完全二叉树的深度 ≤ ≤… ≤ ， (2) 为[1og2n]+l，则调整建新堆时调用 Heapadjust过 。 程 n—1次，总共进行的比较次数不超过 即使公式(1)的序列成为一个按关键字有序的序列 ^一1 iRP1，RP2，…，R j． (3)