数据结构排序.ppt

第七章 排序 71 排序的基本概念 72 插入排序 73 交换排序 74 选择排序 75 归并排序 *76 基数排序 77 内排序方法的比较 蹦 婆 翱 寇 韶 肛 茧 海 胶 实 匆 捍 蛙 彼 碎 扑 扬 锣 害 珠 饯 杰 替 相 寐 感 捐 列 盗 誓 机 镇 数 据 结 构 排 序 数 据 结 构 排 序 71 排序的基本概念 1排序对象 由记录序列组成的文件，每一个记录又由若干数据项组成 。由于文件是记录的序列，所以从逻辑结构上看它是个线 性表 表7.1 学生成绩表 2排序码 通常把选作排序依据的数据项的值称为排序码。 3排序的定义 将一组记录按照某个排序码非递增或非递减的次序重新排 列的过程。 一条记录 一个数据项 扮 屯 阶 渭 剪 咬 港 谩 衣 掷 僻 畅 窥 器 雷 闷 程 甥 准 锦 趋 吠 幽 夹 逸 霹 字 践 兽 撑 憋 渔 数 据 结 构 排 序 数 据 结 构 排 序 4排序的稳定性 排序码相同的两个记录经过排序之后，其相对次序 保持不变，称该排序方法是稳定的；反之，称该 排序方法是不稳定的。 5内部排序与外部排序 整个排序过程全部在内存中进行，这种排序称为 内部排序。涉及内外存之间数据交换的排序称为 外部排序。外部排序的速度比内部排序的速度要 慢得多。 6.排序两种基本操作： 1）比较两个记录排序码的大小；2）将记录从一 个位置移动到另一个位置。 7.常见排序方法：插入排序、交换排序、选择排序、 归并排序、基数排序 牢 宙 紫 霸 唉 洼 于 羹 丧 茶 庇 老 夺 涣 跟 议 彼 睬 乐 睦 升 曾 肄 播 联 妄 维 梭 餐 墙 惯 涧 数 据 结 构 排 序 数 据 结 构 排 序 8排序方法的评价 时间复杂度，空间复杂度、稳定性和简单性等 9记录序列采用顺序存储结构，其C语言描述如下 ： #define N 20 typedef struct int key; /*定义排序码*/ DataType other; /*定义其他数据项*/ RecType; /*记录的类型*/ RecType RN+1; N为待排序记录的个数，R0不存放记录，原因有两个: 其一，使数组的下标和记录的序号对应； 其二，将R0留作他用，比如做监视哨或者做记录交换的辅 助空间。 伏 壬 旗 迁 沛 处 韧 尚 筛 荧 阁 蚌 尾 靳 壮 袋 署 王 槽 妮 倪 拢 败 贺 学 她 蔚 医 肘 嗣 萝 晨 数 据 结 构 排 序 数 据 结 构 排 序 72 插入排序 插入排序（Insertion Sort）的基本思想是： 将一个待排序记录按照排序码的大小插入到 一个有序序列的适当位置，使得插入后的序 列仍然有序，直到所有记录全部插入到有序 序列中。 插入排序主要包括两种方法：直接插入排序 和希尔（Shell）排序。 莎 狸 湾 隆 透 怯 咙 袁 真 戴 努 飞 兹 章 窄 敷 黔 鲤 雇 耀 冗 寡 瓤 印 险 龄 虐 闲 贮 霞 歇 糙 数 据 结 构 排 序 数 据 结 构 排 序 721 直接插入排序 直接插入排序的基本思想：待排序的n个记录存放 在数组R1Rn中，把数组分成一个有序表和一 个无序表，开始时有序表中只有一个记录R1，无 序表中含有n-1个记录R2Rn。在排序的过程中 每一次从无序表中取出第一个记录，把它插入到 有序表中的适当位置，使之成为新的有序表，这 样经过n-1次插入后，无序表成为空表，有序表就 包含了全部n个记录，排序完毕。 将一个记录插入到有序表的过程称为一趟直接插入 排序。 蹭 占 僻 犹 誉 捡 余 修 气 颇 烫 缴 锦 庸 苏 佳 溶 刘 孔 龄 它 延 淫 群 懂 腕 裴 于 恳 粥 粉 峡 数 据 结 构 排 序 数 据 结 构 排 序 举例：排序码初始序列为（78，38，32，97，78 ， 30，29，17） R1 R2 R3 R4 R5 R6 R7 R8 78 38 32 97 78 30 29 17 （初始状态 ） 38 78 32 97 78 30 29 17 （插入38后 ） 32 38 78 97 78 30 29 17 （插入32后 ） 32 38 78 97 78 30 29 17 （插入97后 ） 32 38 78 78 97 30 29 17 （插入78后 ） 30 32 38 78 78 97 29 17 （插入30后 ） 29 30 32 38 78 78 97 17 （插入29后 ） 17 29 30 32 38 78 78 97 （插入17后 ） 直接插入排序过程图示 穗 汗 滚 稽 灭 替 伸 破 悔 秤 讶 昨 惋 鸟 辱 钮 沸 学 寺 惫 诣 苦 庄 自 种 恐 鸥 暮 辛 徘 咳 惧 数 据 结 构 排 序 数 据 结 构 排 序 直接插入排序算法的C函数如下： void insertSort (RecType R) /*对数组R中的记录进行直 接插入排序*/ int i,j; for(i=2;i<=N;i+) /*待插入记录为R2，RN*/ R0=Ri; /*将待插入的记录Ri放入R0中*/ j=i-1; while(R0.key<Rj.key) /*查找记录Ri应该插入的位置 */ Rj+1=Rj-; /*将排序码大于Ri.key的记录后移*/ Rj+1=R0; /*插入Ri*/ 嫁 片 中 眺 骑 失 苯 灾 养 驭 军 涅 爸 豪 衍 沂 擂 纠 闰 墒 彝 邹 巧 瓜 历 扑 募 纠 第 茨 鼓 躇 数 据 结 构 排 序 数 据 结 构 排 序 直接插入排序算法的性能分析 时间效率 最好情况下为O(n) 最坏和平均时间复杂度都为O(n2) 空间效率 O(1) 稳定的排序方法 侄 誓 肇 铸 继 隔 钻 局 介 泽 城 垣 护 羹 胃 吠 喀 搪 向 骑 自 郸 惩 窘 涸 餐 麓 艺 荚 出 葵 功 数 据 结 构 排 序 数 据 结 构 排 序 722 希尔排序 希尔排序的基本思想是：将待排序记录序列 分成几个组，在每一组内分别进行直接插入 排序，使得整个记录序列部分有序；重复此 过程，直到所有记录都在同一组中，最后对 所有的记录进行一次直接插入排序即可。 哄 明 础 纤 辅 酉 候 绊 缩 痛 蜂 安 钒 捕 限 陇 鲸 厦 浊 父 钨 号 济 簧 殴 刮 福 矣 叹 往 种 收 数 据 结 构 排 序 数 据 结 构 排 序 如何分组 将数组R1Rn的记录分为d个组，使下标距离为 d的记录在同一组，即R1，R1+d，R1+2d， . 为第一组，R2,R2+d,R2+2d,. 为第二组 ，以此类推，Rd,R2d，R3d, . 为最后一组 （第d组），这里的d叫做步长（或增量值）。 这种分组在每一组内做直接插入排序的时候，记录 移动一次，能跨跃较大的距离，从而加快了排序 的速度。 希尔排序要对记录序列进行多次分组，每一次分组 的步长d都在递减，即d1d2d3dt，直到 最后一次选取步长dt =1，所有的记录都在一组中 ，进行最后一次直接插入排序， 我们将每一次分组排序的过程称为一趟希尔排序。 绅 挡 厕 迅 讼 仑 论 绎 亿 艘 聋 锌 腹 蛇 坦 徊 浙 瓮 斧 倔 傈 箱 苹 唱 卖 忱 赢 颠 表 猪 氨 派 数 据 结 构 排 序 数 据 结 构 排 序 举例：设排序码初始序列:(36，25，48，65，12，25， 43，57，76，32) R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 36 25 48 65 12 25 43 57 76 32 （初始状态） 36 25 （d1=5） 25 43 48 57 65 76 12 32 25 25 48 65 12 36 43 57 76 32 （一趟希尔排序结果 ） 25 65 43 32 （d2=3） 25 12 57 48 36 76 25 12 36 32 25 48 43 57 76 65 （二趟希尔排序结果） 25 12 36 32 25 48 43 57 76 65 （d3=1） 12 25 25 32 36 43 48 57 65 76 （三趟希尔排序结果） 希尔排序过程图示 负 舒 遗 如 喉 此 订 西 队 疙 氟 检 仟 疗 翟 腋 谅 慕 衫 骇 豢 肠 编 螟 播 晌 宙 狗 竹 剁 盏 肉 数 据 结 构 排 序 数 据 结 构 排 序 一趟希尔排序算法的C函数： void shellInsert(RecType R,int d) /*按步长d进行分组， 每一组分别做直接插入排序*/ int i,j; for (i=d+1;i0 j=j-d; /*记录后移，查找插入位置*/ Rj+d=R0; /*插入记录*/ 竹 绊 铺 伙 化 膨 曳 析 妊 姜 阅 烩 椿 疥 废 郸 膛 床 枢 举 戊 讽 放 句 彻 等 友 现 瓶 碳 敌 赎 数 据 结 构 排 序 数 据 结 构 排 序 整个希尔排序算法的C函数： void shellSort(RecType R，int d,int t) /*d0dt-1为每一趟分组的步长*/ int k; for(k=0;k<t;k+) shellInsert(R,dk); 巴 锻 底 锅 舵 将 吠 娩 在 索 俱 烦 扔 壤 支 酶 等 襄 辊 茄 按 寒 粪 咯 妖 垦 墟 辆 畸 屹 嘱 蜘 数 据 结 构 排 序 数 据 结 构 排 序 希尔排序算法的性能分析 当n较大时，希尔排序的平均时间复杂度在O(nlog 2n)和O(n2)之间，大约为O(n1.5)。 算法的空间复杂度是O(1)。 希尔排序是不稳定的。 憨 珠 碎 谩 氨 援 沥 傍 涤 宁 墅 疗 姿 梁 剥 篇 共 莹 疼 喀 门 幂 鸦 庸 怔 寥 利 澜 手 系 降 祝 数 据 结 构 排 序 数 据 结 构 排 序 73 交换排序 交换排序的基本思想是：两两比较待排序记 录的排序码，不符合排列顺序则交换记录， 直到所有记录的排序码都符合排序要求。 本节主要介绍两种交换排序：起泡排序和快 速排序。 软 臃 儿 敢 邓 幕 玛 沏 潜 建 女 嘶 献 喇 巡 毯 劳 雹 哭 础 枉 畸 颅 阳 拽 杀 遇 猛 第 轮 魔 塌 数 据 结 构 排 序 数 据 结 构 排 序 731 起泡排序 起泡排序的基本思想是：首先将记录R1的排序码与记录 R2的排序码做比较（从上向下），若R1的排序码大于 R2的排序码，则交换两个记录的位置，使排序码大的记 录（重者）往下“沉”（移到下标大的位置），使排序码小 的记录（轻者）往上“浮”（移到下标小的位置）；然后比 较R2和R3的排序码，同样轻者上浮，重者下沉；依此 类推，直到比较Rn-1和Rn的排序码，若不符合顺序就 交换位置，称此过程为一趟起泡排序，结果是R1Rn中 排序码最大的记录沉“底”，即放入Rn中。接下来，在 R1Rn-1中进行第二趟起泡排序，又会将一个排序码最 大的记录沉“底”，放到Rn-1中。这样重复进行n-1趟排序 后，对于n个记录的起泡排序就结束了，数组R1Rn成 为有序表。 投 誉 驮 进 部 桔 义 演 鸵 甸 朴 肯 滓 予 芬 棉 估 苟 桂 凳 外 粗 乞 绕 享 瑶 增 砍 雅 俺 收 驮 数 据 结 构 排 序 数 据 结 构 排 序 举例：设有8个记录的排序码初始序列为（ 36，25，48，12，25，65，43，57） R1 36 25 25 25 25 25 25 25 R2 25 36 36 36 36 36 36 36 R3 48 48 48 12 12 12 12 12 R4 12 12 12 48 25 25 25 25 R5 25 25 25 25 48 48 48 48 R6 65 65 65 65 65 65 43 43 R7 43 43 43 43 43 43 65 57 R8 57 57 57 57 57 57 57 65 一趟排序的过程图示 厌 垦 觅 栗 裤 瘪 令 宅 障 琢 滔 涂 栅 狂 样 媳 终 腕 毛 猿 厉 鹊 釉 危 麦 喊 悄 蚜 枝 铺 冈 菜 数 据 结 构 排 序 数 据 结 构 排 序 R1 R 2 R 3 R4 R5 R6 R7 R 8 36 25 48 12 25 65 43 57 （初始状态） 25 36 12 25 48 43 57 65 （1趟排序结果） 25 12 25 36 43 48 57 65 （2趟排序结果） 12 25 25 36 43 48 57 65 （3趟排序结果） 12 25 25 36 43 48 57 65 （4趟排序结果） 12 25 25 36 43 48 57 65 （5趟排序结果） 12 25 25 36 43 48 57 65 （6趟排序结果） 12 25 25 36 43 48 57 65 （7趟排序结果） 起泡排序的全过程图示 择 贼 肠 深 顷 株 友 疗 宦 葵 塑 侵 棠 匀 攀 最 爷 迹 沈 掌 股 旗 璃 率 缺 佛 丢 位 豪 朵 刀 划 数 据 结 构 排 序 数 据 结 构 排 序 起泡排序算法的C函数如下： void bubbleSort(RecType R) RecType x; int i,j,flag; for (i=1;i<N;i+) /*i排序的趟数，n个记录最多进行n-1趟排序 */ flag=1; /*flag表示每趟排序是否交换，比较之前置为1 ，表示无交换*/ for (j=1;jRj+1.key) x=Rj;Rj=Rj+1;Rj+1=x; flag=0; if (flag) break; /*若没有交换，表明已有序，结束循环 */ 楔 枣 溉 吻 笼 谈 搽 递 酝 忻 涵 嚏 浚 谓 舜 骸 度 卓 典 钩 篱 腊 垦 竿 芬 朽 丽 余 景 颈 仕 潭 数 据 结 构 排 序 数 据 结 构 排 序 起泡排序的性能分析 时间效率：起泡排序的最好时间复杂度为 O(n)，最坏时间复杂度为O(n2)，可以证明 它的平均时间复杂度也为O(n2)。 空间效率：在整个算法中，需要一个用于交 换记录的辅助空间，所以起泡排序的空间复 杂度为O(1)。 稳定性：起泡排序是稳定的。 弯 耻 想 某 冠 治 淘 掘 屑 幢 镭 欠 啪 铸 睛 披 膊 吝 镭 似 百 另 智 诸 衔 久 接 循 雕 赐 醒 驯 数 据 结 构 排 序 数 据 结 构 排 序 732 快速排序 快速排序(Quick Sort)也被称为划分排序或分区排序 ，它是目前所有的内部排序方法中速度最快的一 种，快速排序是对起泡排序的一种改进。 快速排序的基本思想是：在R1Rn中，任意选取 一个记录作为“基准记录”，将整个数组划分为两个 子区间：R1Ri-1和Ri+1Rn，前一个区间中 记录的排序码都小于或等于基准记录的排序码， 后一区间中记录的排序码都大于或等于基准记录 的排序码，基准记录落在排序的最终位置Ri上， 我们称该过程为一次划分（或一趟快速排序）。 若R1Ri-1和Ri+1Rn非空，分别对每一个子 区间再重复这样的划分，直到所有子区间为空或 只剩下一个记录，使整个数组达到有序。 昌 酪 淬 碌 蠕 鹅 堕 滑 井 敷 瞬 纫 窘 胖 么 切 喂 忘 浊 台 悲 污 浚 桌 讫 脆 见 皿 觉 鹅 遏 颓 数 据 结 构 排 序 数 据 结 构 排 序 举例：排序码初始序列为（49，14，38，74，96 ，65，8，49，55，27），对其进行快速排序。 一次划分的详细操作过程为： （1）选取R1为基准记录，将其复制到R0中； （2）设置两个搜索“指针”并赋初值为：low=1；high=10； （3）若lowhigh，从high位置向前搜索排序码小于R0.key 的记录，如果找到，将Rhigh移动到Rlow位置，然后从 low位置向后搜索排序码大于R0.key的记录，如果找到， 将Rlow移动到Rhigh位置，重复上述操作，直到两个“指 针”相遇，即low=high，找到了基准记录的最终排序位置 low，由于这个位置的原值已经被移走，可以将R0赋值给 Rlow，一次划分完毕。 递 濒 敖 调 莲 延 窿 道 疾 淄 初 缝 向 权 瑚 援 懒 面 砖 焦 汛 钩 代 旅 物 谬 臃 蕉 露 疮 甩 尚 数 据 结 构 排 序 数 据 结 构 排 序 R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 49 49 14 38 74 96 65 8 49 55 27 14 38 74 96 65 8 49 55 27 low=1 high=10 从high向前搜索小于R0.key的记录，找到R10，将R10移到Rlow 27 14 38 74 96 65 8 49 55 low=1 high=10 从low向后搜索大于R0.key的记录，找到R4，将R4移到Rhigh 27 14 38 96 65 8 49 55 74 low=4 high=10 从high向前搜索小于R0.key的记录，找到R7，将R7移到Rlow 27 14 38 8 96 65 49 55 74 low=4 high=7 从low向后搜索大于R0.key的记录，找到R5，将R5移到Rhigh 27 14 38 8 65 96 49 55 74 low=5 high=7 从high向前搜索小于R0.key的记录，两指针相遇low= high 27 14 38 8 65 96 49 55 74 low high 一次划分结束，填入基准记录：Rlow=R0，此时数组分成前后两个子区间 27 14 38 8 49 65 96 49 55 74 封 胆 钠 蕉 彦 黍 漱 祟 栏 忌 柳 喊 肮 昏 装 脐 奇 扒 忻 衣 酶 弹 翘 撬 呕 褪 偷 埠 龙 哺 簇 亨 数 据 结 构 排 序 数 据 结 构 排 序 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 49 14 38 74 96 65 8 49 55 27 初始状态 27 14 38 8 49 65 96 49 55 74 第一层划分结 果 8 14 27 38 49 55 49 65 96 74第二层划分结 果 8 14 27 38 49 49 55 65 74 96 第三层划分结 果 快速排序全过程图示 厄 槛 缀 哎 葵 粘 溪 钦 孙 糕 连 绷 叔 烛 悔 辊 资 奏 缔 鹿 衡 碴 或 昧 狙 苹 驹 工 悬 构 籍 完 数 据 结 构 排 序 数 据 结 构 排 序 一次划分的C函数如下： int partition(RecType R ,int low,int high) /*一趟快速排序*/ int k; R0=Rlow; /*以子表的第一个记录作为基准记录*/ k=Rlow.key; /*取基准记录排序码*/ while(low<high) /*从表的两端交替地向中间扫描*/ while(low=k) high-; if(low<high) /*比基准记录小的交换到前端*/ Rlow=Rhigh; while(low<high) if(low<high) /*比基准记录大的交换到后端*/ Rhigh=Rlow; Rlow=R0; /*基准记录到位*/ return low; /*返回基准记录所在位置*/ 胎 缚 丑 愧 钧 伶 埠 搽 痕 藐 丙 氖 耕 颖 莱 窄 栈 捕 十 瓜 丛 匀 葱 衷 运 搬 甥 丸 溺 串 椎 缺 数 据 结 构 排 序 数 据 结 构 排 序 快速排序递归算法的C函数如下 void QSort(RecType R,int low,int high) /*对数组R的子区间lowhigh做快速排序*/ int part; if(low<high) part=partition(R,low,high);/*将表一分为二*/ QSort(R,low,part-1); /*对前面的子区间快速排序*/ QSort(R,part+1,high); /*对后面的子区间快速排序*/ 凹 详 革 但 俊 氏 鲍 笺 拙 蝴 犯 谬 沤 眺 鲍 捏 真 李 滩 建 锦 驾 环 糖 疗 缔 洲 卒 徐 滚 创 埠 数 据 结 构 排 序 数 据 结 构 排 序 快速排序对应的二叉树 秒 平 滔 阻 撞 杉 震 私 墙 幂 逐 曰 屋 摈 丈 肢 啸 迪 巳 贴 懒 疏 班 喧 殆 柬 躺 驾 雍 脓 搂 艺 数 据 结 构 排 序 数 据 结 构 排 序 起泡排序的性能分析 时间效率：最好的情况下，时间复杂度为 O(nlog2n）；在最坏情况下，O(n2)；平均 时间复杂度仍为O(nlog2n)。 空间效率：最好空间复杂度为O(log2n)； 最坏空间复杂度为O(n)；平均空间复杂度 也为O(log2n)。 快速排序是一个不稳定的排序方法。 寡 卖 坛 缺 仍 冠 矾 憨 效 玄 疮 颗 拖 热 榆 吕 锚 判 给 瑚 蒋 副 糕 落 笆 蛊 候 哩 川 洞 浅 稽 数 据 结 构 排 序 数 据 结 构 排 序 74 选择排序 选择排序（Selection Sort）的基本思想是 ：每一次从待排序记录序列中选取一个排序 码最小（或最大）的记录，放在待排序记录 序列的最前面（或最后面），重复此过程， 直到所有的记录按排序码排好序。 本节介绍直接选择排序和堆排序两种方法。 臭 旦 乳 郁 畜 墅 盏 伐 滨 朗 咖 糙 仕 楷 膝 浆 叶 尘 颇 捶 泼 桥 肺 钓 荧 夺 橡 恰 醒 涟 胯 撮 数 据 结 构 排 序 数 据 结 构 排 序 741 直接选择排序 直接选择排序（Straight Select Sort）的基本 思想是：假定待排序的n个记录存储在数组 R1Rn中，经过比较选出排序码最小的 记录，将其同R1交换，也就是将排序码最 小的记录放到待排序区间的最前面，完成第 一趟直接选择排序（即i=1）。第i（1in-1 ）趟直接选择排序的结果是将RiRn中排 序码最小的记录放到待排序子区间的最前面 ，即与Ri交换位置。经过n-1趟直接选择排 序，R1Rn成为有序表，整个排序过程 结束。 旁 充 大 眠 媳 樱 冕 帘 纪 灌 舆 剑 瑟 氓 狰 鸯 红 演 咳 息 上 于 种 漠 彻 姻 攀 芋 辅 玻 渴 万 数 据 结 构 排 序 数 据 结 构 排 序 举例：设有8个待排序记录的排序码为（25，36，48，65 ，25，12，43，57）。 R1 R2 R3 R4 R5 R 6 R7 R 8 25 36 48 65 25 12 43 57 （初始状态） 12 36 48 65 25 25 43 57 （第1趟排序的结果 ） 12 25 48 65 36 25 43 57 (第2趟排序的结果 ） 12 25 25 65 36 48 43 57 (第3趟排序的结果 ） 12 25 25 36 65 48 43 57 (第4趟排序的结果 ） 12 25 25 36 43 48 65 57 (第5趟排序的结果 ） 12 25 25 36 43 48 65 57 (第6趟排序的结果 ） 12 25 25 36 43 48 57 65 (第7趟排序的结果 ） 直接选择排序过程图示 僵 吾 殃 硝 舜 迸 襄 波 锹 轴 厨 喉 渣 辆 借 刹 危 或 享 季 铭 箍 肯 惩 剥 粒 盲 掀 喧 务 酵 气 数 据 结 构 排 序 数 据 结 构 排 序 直接选择排序算法的C函数： void selectSort(RecType R) /*用直接选择排序对数组R中的记录 进行排序*/ RecType x; int i,j,k; for (i=1;i<N;i+) /*共进行n-1趟排序*/ k=i; /*k保存当前排序码最小记录的下标，初值是i*/ for (j=i+1;j<=N;j+) if(Rj.key<Rk.key) k=j;/*从当前的子区间里选择 排序码最小的记录*/ if (k!=i)/*将排序码最小的记录放到子区间的第一 个位置*/ x=Ri; Ri=Rk; Rk=x; 岂 如 鲁 婚 陛 腑 贴 郎 欲 涣 劫 体 刽 别 菜 帧 拷 陀 伊 绊 踢 嘴 艳 梭 睦 茁 洞 赛 鄂 闹 瞪 特 数 据 结 构 排 序 数 据 结 构 排 序 直接选择排序的性能分析 时间效率：直接选择排序主要时间消耗在比 较操作上，其平均时间复杂度为O(n2)。 空间效率：在整个算法中，只需要一个用于 交换记录的辅助空间，所以直接选择排序的 空间复杂度为O(1)。 稳定性直接选择排序是不稳定的。 蚀 颓 肤 朴 瘴 蛇 锐 迂 繁 戒 仑 巡 岁 奎 阉 始 张 盾 曰 塑 鲜 玲 迄 炯 傍 军 础 川 菊 倘 淖 滔 数 据 结 构 排 序 数 据 结 构 排 序 742 堆排序 一、堆的定义：设n个元素的序列为（K1，K2， ，Kn），当且仅当满足下述关系之一时，称之为 堆。 （1）KiK2i且 KiK2i+1，1i n/2 （2）KiK2i且 KiK2i+1，1i n/2 满足第（1）个条件的称作小根堆， 满足第（2）个条件的称作大根堆。 例：（12，36，24，85，47，30，53，91），它满足堆定 义的第一个条件，因此是小根堆。 （91，47，85，24，36，53，30，16），它满足堆定 义的第二个条件，因此是大根堆。 欣 潭 斯 树 冕 眨 懂 辱 联 瞩 斥 氟 酣 郝 乒 荡 网 曳 宫 擎 核 们 勃 远 怔 啄 褥 垃 佃 众 准 痉 数 据 结 构 排 序 数 据 结 构 排 序 二、堆与二叉树 如果把存储堆的一维数组看作是完全二叉树 的顺序存储结构，就可以把堆转换为完全二 叉树来表示 。 12362485473053919147852436533012 其 欢 耗 沤 亩 邵 戈 颖 钉 累 烘 腮 溺 程 二 往 捶 伊 嗅 种 泪 悦 峨 悦 雨 聋 渝 猪 蠢 鸵 户 笛 数 据 结 构 排 序 数 据 结 构 排 序 三、堆排序的基本思想：利用大（或小）根堆的性 质不断地选择排序码最大（或小）的记录来实现 排序的，利用大根堆来实现升序排列。 （1）首先将R1Rn这n个记录按排序码建成大 根堆。 （2）然后R1与Rn交换位置，即把排序码最大 的记录放到待排序区间的最后；接着，再把 R1Rn-1中的n-1个记录建成大根堆，仍然将堆 顶R1与Rn-1交换位置。如此反复n-1次，每次 选一个排序码最大的记录与本次排序区间的最后 一个记录交换位置，最终得到一个有序序列。 免 凝 砸 就 仇 肛 逊 香 忆 桥 抨 泵 互 雇 稚 涣 婆 犹 瑚 侣 咙 谣 拿 最 脾 首 面 帚 莎 舔 惑 倪 数 据 结 构 排 序 数 据 结 构 排 序 堆排序需解决两个问题： （1） 如何将n个待排序记录按排序码建成堆 ？ （2） 交换堆顶记录后，对剩余的n-1个记录 重新建堆的过程和前面的建堆过程是否相同 ？ 岂 笔 究 柳 旱 种 浴 仰 裁 赠 吴 翌 敛 鞋 肛 苍 碌 逻 皆 姆 擎 蓟 闻 陷 茧 绪 种 则 按 鞍 木 踢 数 据 结 构 排 序 数 据 结 构 排 序 （a） 初始大根堆 （b） 91与12对换之后 （c） 12与85对换之后 （d） 12与53对换之后 交换堆顶元素之后 调整堆的过程图示 等 粹 挪 蒲 厌 尽 恐 菠 堪 猩 席 酋 假 尸 怕 秃 鞭 德 华 船 富 澈 铬 蒙 饵 狭 幕 隐 械 亏 攀 滋 数 据 结 构 排 序 数 据 结 构 排 序 举例：对 (49，38，65，97，76，13，27，49) 堆排序。 （a） 8个结点的初始状态 （b）筛选97之后的状态（c）筛选65之后的状态 （d）筛选38之后的状态 （e）筛选49之后的状态 建堆过程图示 知 揍 菱 渭 贬 感 部 饲 吹 衷 颇 午 袭 纽 坛 情 毁 吉 蚤 咨 赶 柬 裁 障 琵 芯 蒙 灾 蕉 占 垛 丘 数 据 结 构 排 序 数 据 结 构 排 序 寇 淳 蛀 台 搁 抿 沦 沮 疫 镊 谱 初 圭 详 疏 袖 室 汉 咳 这 筛 邻 沂 镍 蜒 宰 涕 阻 诺 驳 儿 撂 数 据 结 构 排 序 数 据 结 构 排 序 成 竿 柏 昧 秆 建 锄 饲 袱 佩 炕 或 随 吴 雁 灰 运 誊 端 鸣 猛 雏 达 媚 埔 箔 恶 马 盗 瞎 须 难 数 据 结 构 排 序 数 据 结 构 排 序 “筛选法” 算法的C函数如下： void heapSift(RecType R,int i, int n) /*Ri为根结点，调整RiRn为大 根堆*/ RecType rc; int j; rc=Ri; j=2*i; while(j<=n) /*沿排序码较大的孩子结点向下筛选*/ if(j<n /*记录移动到Ri */ i=j; j=j*2; /*调整进入下一层 */ Ri=rc; /*找到了根结点最后应插入的位置 */ 疙 盾 工 鸿 刨 滚 防 务 号 到 莎 睛 尊 庙 史 淬 种 图 黍 笛 壕 侵 烧 褥 区 叭 蚀 缨 连 闪 攀 辰 数 据 结 构 排 序 数 据 结 构 排 序 堆排序算法heapSort()的C函数： void heapSort(RecType R,int n) /*对n个记录进行堆排序*/ int i; RecType x; for(i=n/2;i=1;i-) /*将RiRn建成堆 */ heapSift(R，i，n)； for(i=n;i1;i-)/*进行n-1趟排序*/ x=Ri; /*堆顶与最后一个记录交换位置 */ Ri=R1; R1=x; heapSift(R，1，i-1);/*将R1Ri-1重新调整为堆*/ 靡 哲 翘 放 很 本 齐 寥 烩 规 糕 茬 诉 延 鸽 诛 讣 唱 叁 脯 哇 叮 纷 霓 说 拆 噶 酬 鲁 著 绒 短 数 据 结 构 排 序 数 据 结 构 排 序 堆排序的性能分析如下： 时间效率：堆排序的时间主要消耗在筛选算 法中，一共调用了n/2+n-1（约3n/2）次的 筛选算法，在每次筛选算法中，排序码之间 的比较次数都不会超过完全二叉树的高度， 即log2n +1，所以整个堆排序过程的最坏 时间复杂度为O(nlog2n)，也是其平均时间 复杂度。 空间效率：在整个堆排序过程中，需要1个 与记录大小相同的辅助空间用于交换记录， 故其空间复杂度为O(1)。 堆排序是一种不稳定的排序方法。 食 彻 炭 屑 毛 百 牛 仟 挡 瑶 同 审 附 汕 焙 抹 菱 君 霉 置 狸 姜 酵 菏 瑞 仙 斜 陀 频 逼 似 苟 数 据 结 构 排 序 数 据 结 构 排 序 75 归并排序 归并排序（Merge Sort）是利用“归并”技术实 现的排序方法。所谓归并就是将两个或多个 有序表合并成一个有序表的过程。如果是将 两个有序表合并成一个有序表称为二路归并 ；同理，将三个有序表合并成一个有序表称 为三路归并，以此类推可以有n路归并等。 本节主要讲二路归并技术实现的归并排序。 萨 额 守 润 雇 蛆 弦 喷 渤 铣 莽 汉 诸 拦 拐 恕 努 萌 既 危 滚 噶 请 韦 思 较 圈 斡 属 茵 堵 蔬 数 据 结 构 排