《数据结构（牛小飞）4 排序比较和习题课.ppt》由会员分享，可在线阅读，更多相关《数据结构（牛小飞）4 排序比较和习题课.ppt（28页珍藏版）》请在三一文库上搜索。
1、总结和习题 习题课 各种排序方法的比较 本章的主要内部排序方法 涸 干 谐 亮 壳 魄 荒 模 玲 痛 眯 吞 鞭 七 畏 菇 祖 收 费 烂 芋 兄 鸳 趾 图 纽 檄 虚 宴 堪 汝 钱 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 本章的主要内部排序方法 本章研究的内部排序方法主要有： 插入排序直接插入排序希尔排序 交换类换类 排序起泡排序快速排序 选择类选择类 排序简单选择简单选择 排 序 堆排序 归归并排序 基数排序多关键键字排序 链链式基数排序 豆 姥 帖 仰 荒 价 睡 泣 思 蕴
2、瘫 鸟 拄 蜕 锤 潍 秽 枯 商 崎 鳞 先 谐 尺 啡 每 椰 窿 握 蓬 骨 希 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 1.插入排序 1)基本思想 ： 插入排序：将无序子序列中的一个或几个记录“插入”到 有序序列中，从而增加记录的有序子序列的长度。 本章的主要排序方法 瘸 舰 西 降 童 皑 咯 遍 效 衡 紊 喊 骨 萤 藻 牛 宴 雄 咬 怨 彻 倾 绰 沁 拈 鞍 丢 撼 瞻 温 狈 肌 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （
3、 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 2)常见的插入排序算法 a.直接插入排序（基于顺序查找） b.希尔排序（基于逐趟缩小增量） O(n2) 是一种稳定的排序方法 是一种不稳定的排序方法 本章的主要排序方法 叁 馆 磺 枣 洱 切 颜 搀 卸 飘 堂 义 觅 蒜 荚 跪 兆 倡 代 揩 一 氨 溺 灸 呆 澎 拾 环 囱 多 檀 临 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 2.交换类排序 1)基本思想 ： 依次两两比较相邻关键字，并交换不满足排 序要求的关键字，直至全部有序。
4、 本章的主要排序方法 五 乒 蛮 务 烟 喝 锯 告 壕 乔 吧 逢 获 字 镶 哭 仪 篱 珐 园 瘁 执 芋 由 蝗 疗 桑 蔷 抨 鬃 职 帛 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 2)常见的交换类排序算法 a.起泡排序 b.快速排序 O(n2) 是一种稳定的排序方法 是一种不稳定的排序方法 O(nlogn) 本章的主要排序方法 糙 弃 凰 虐 狼 痪 谬 悠 终 寄 糊 鳖 歇 骨 醇 跟 伸 祷 鉴 讹 庸 状 突 言 幼 善 裔 萤 擎 当 腑 搏 数 据 结 构 （ 牛 小
5、飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 3.选择类排序 1)基本思想 ： 每一趟从待排序的n-i+1（i=1,2,3,n-1）个记 录中选出关键字最小的记录，作为有序序列中 第i个记录，直到全部记录排序完毕。 本章的主要内部排序方法 防 肃 屹 长 劳 芒 组 骋 横 囊 深 躇 榨 苏 淆 如 阁 芭 钳 碳 泌 酌 夫 抽 哨 杂 扔 履 圭 戊 杂 股 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 2)常见的选择类排
6、序算法 O(n2) 是一种不稳定的排序方法 是一种不稳定的排序方法 O(nlogn) a. 简单选择排序 b. 堆选择排序 本章的主要内部排序方法 溢 蝎 香 宅 椎 保 雁 桅 主 圆 敞 颠 垒 叼 旷 窥 空 攀 昌 佐 赎 颇 檬 庞 邹 妖 去 介 犬 摊 篇 台 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 4.归并排序 1)基本思想 ： 将两个或两个以上的有序子序列 “归并” 为一个 有序序列。 时间复杂度为(nlogn)。 是一种稳定的排序方法 本章的主要内部排序方法 药 屎 肪
7、包 拯 慕 砰 尔 弛 毅 财 嚼 歌 仰 活 空 餐 钠 虾 距 蓑 陛 磨 癸 宙 铲 耿 彼 慰 睬 锚 爽 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种内部排序方法的比较 5.链式基数排序 1)基本思想 ： 在多关键字的记录序列中，每个关键字的取值范 围相同，则按LSD法进行排序时，可以采用“分 配-收集”的方法，不需要进行关键字间的比较。 时间复杂度为O(d(n+rd) 是稳定的排序方法 躯 功 龟 讽 翰 安 距 邪 毗 沼 问 讥 力 赏 根 纷 恩 舱 斜 浅 品 帅 纂 畅
8、 聂 游 栋 井 沙 炔 点 染 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种内部排序方法的比较 1. 平均的时间性能 基数排序 时间复杂度为 O(nlogn)： 快速排序、堆排序和归并排序 时间复杂度为 O(n2)： 直接插入排序、起泡排序和简单选择排序 时间复杂度为 O(d(n+rd): 一、时间性能 兹 笆 雀 玖 梨 孜 胃 糙 钟 挚 测 馈 器 在 破 瘪 擅 苍 修 潞 庞 踩 佛 科 怠 岗 秃 杭 薄 逾 芥 息 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和
9、习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种内部排序方法的比较 2. 当待排记录序列按关键字顺序有序时 直接插入排序和起泡排序能达到O(n)的时间 复杂度 快速排序的时间性能蜕化为O(n2) 。 3. 简单选择排序、堆排序和归并排序的时间性能 不随记录序列中关键字的分布而改变。 爽 移 断 暇 册 涎 绳 秀 叛 抡 飞 疵 酬 捻 侮 针 挺 抬 贮 馆 个 纽 苗 胜 凡 淀 悍 压 靶 计 作 呕 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种
10、内部排序方法的比较 二、空间性能 指的是排序过程中所需的辅助空间大小 1. 所有的简单排序方法(包括：直接插入、 起泡和简单选择) 和堆排序的空间复杂度为O(1) ； 2. 快速排序为O(logn)，为递归程序执行过程中 ，栈所需的辅助空间； 牺 握 鸿 椭 活 胶 鹰 恿 次 勺 涩 叛 固 餐 祟 矢 竟 枷 转 紊 伦 攀 哉 葵 生 幌 禁 受 赂 届 坦 犹 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种内部排序方法的比较 3. 归并排序所需辅助空间最多，其空间复 杂度为 O(n);
11、 4. 链式基数排序需附设队列首尾指针， 则空间复杂度为 O(rd)。 订 盂 文 尽 坛 单 迁 揉 唱 彦 疟 郧 冗 卞 消 坛 帅 豁 疏 父 羌 袭 奄 蹦 赊 挖 腊 札 废 皑 杰 哥 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种内部排序方法的比较 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等 的记录，它们在序列中的相对位置，在排序之前 和经过排序之后，没有改变。 排序之前 : Ri(K) Rj(K) 排序之后 : Ri(K) Rj(K) 鸣 疽 须
12、翱 淤 蹈 胯 恰 赊 超 公 弦 导 杀 同 扎 玻 属 寡 丘 汕 添 班 侨 浴 箩 弄 拿 讹 啃 讹 畦 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种内部排序方法的比较 2. 当对多关键字的记录序列进行LSD方法排序时， 必须采用稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实 例说明即可。 4. 快速排序、堆排序和希尔排序是不稳定的 排序方法。 例如 : 对 4, 3, 4, 2 进行快速排序， 得到 2, 3, 4, 4 瞬 访 翅 潍 掣 骂 葵 耐 檀 烘 实
13、 利 慕 腿 掸 隧 漾 达 枚 降 沽 冉 赦 殖 锦 消 祁 澄 系 译 至 帧 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种内部排序方法的比较 四、关于“排序方法的时间复杂度的下限” 本章讨论的各种排序方法，除基数排序外，其 它方法都是基于“比较关键字”进行排序的排序 方法。 可以证明，这类排序法可能达到的最快的时间 复杂度为O(nlogn)。 (基数排序不是基于“比较关键字”的排序方法， 所以它不受这个限制。) 妻 兹 堰 姿 鹰 每 泉 巾 揭 撤 轰 埂 臆 焙 疽 乎 矩 忘
14、萄 巨 跃 骋 介 裔 鹰 律 哄 婉 例 堑 蠕 戳 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 各种内部排序方法的比较 例如:对三个关键字进行排序的判定树如下： K10) AND (Ajx) DO Aj+1:=Aj; j:=j-1 Aj+1=x 1、这段代码所描述的排序方法是_ 。 2、这段代码所描述的排序方法的时间复杂度为_。 3、假设这段代码开始执行时,数组A中的元素已经按值的递增 次序排好了序,则这段代码的执行时间为_。 直接插入排序 O(n2) O(n) 习题课 钝 马 权 矢 遇
15、醚 栈 濒 攀 犁 笛 悸 翟 淹 硒 曼 娱 锤 唾 依 娩 川 塌 八 谁 件 尼 剔 吉 狮 贡 铭 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 14、设有n个无序元素，按非递减次序排序，但只想得到前面长 度为k的部分序列，其中nk，最好采用什么排序方法？ 为什 么？ 如果有这样的一个序列59，11，26，34，17，91，25，得到 的部分序列是11，17，25，对于该例使用所选择的方法实现 时，共执行多少次比较？ 习题课 15、给出如下关键字序列321，156，57，46，28，7，3
16、31，33 ，34，63，请按链式基数排序方法，列出一趟分配和收集的过 程。 卵 劝 峨 而 签 呵 康 食 呐 馅 忍 么 餐 攒 贞 尘 赴 缺 今 霍 酌 狼 良 邯 镣 起 眶 浸 鼻 粹 乙 诅 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 16、给定一个关键字序列24，19，32，43，38，6， 13，22，请写出快速排序第一趟的结果；堆排序时所 建的初始堆；归并排序的全过程。 习题课 17、设有一个数组中存放了一个无序的关键字序列K1, K2,Kn。现要求将Kn放在将元素排序后的正确的位置 上，试编写实现该功能的算法，要求比较关键字的次 数不超过n。 佐 贩 窍 疫 傣 傻 拨 祥 割 诽 垢 绽 熊 调 唾 八 扣 料 储 涅 囚 屯 弓 正 衫 盲 揭 奇 榜 利 菌 孕 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课 数 据 结 构 （ 牛 小 飞 ） 4 排 序 比 较 和 习 题 课