《牛小飞《数据结构》7.1排序问题、插入排序和希尔排序.ppt》由会员分享，可在线阅读，更多相关《牛小飞《数据结构》7.1排序问题、插入排序和希尔排序.ppt（38页珍藏版）》请在三一文库上搜索。
1、排序问题和插入排序 排序问题 插入排序 小结和作业 味 馁 识 恃 凋 空 方 疑 诫 送 找 申 试 盂 锹 戚 臣 拉 平 蛹 隧 病 额 给 房 躁 痒 佣 卿 宅 饯 贞 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 排序的定义 内部排序和外部排序 内部排序方法的分类 排序问题 稳定性 昏 闽 渝 婴 忧 犀 蜜 蕊 禁 粮 岭 习 莱 棚 鹃 州 雍 糖 骄 碧 馏 邮 佃 吸 畅 厦 柔 较 挚 尼 筏 尸 牛 小 飞 数 据 结 构 7
2、 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 排序的定义 排序是计算机内经常进行的一种操作，其目的是 将一组“无序”的序列调整为“有序”的序列。 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 庐 勾 源 芒 渣 兄 月 陛 林 秃 渍 背 缘 粒 新 磺 歌 座 脑 搀 情 淋 娱 琴 获 观 黄 凋 肠 烩 瓮 钢 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题
3、 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 排序的定义 一般情况下， 假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在 它们之间存在着这样一个关系 ： Kp1Kp2Kpn 按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。 似 警 兢 吊 尿 蚀 登 集 绅 旺 崔 挫 涩 犹 郝 船 企 瘴 郎 父 塘 瓷 网 提 铜 馋 凸 拢 恢 母 掂 莎 牛 小 飞 数 据 结 构 7 .
4、1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 排序的定义 关键字(key): 数据对象有多个属性域, 即多个数据成员组 成, 其中有一个属性域可用来区分对象, 作为排 序依据，称为关键字。也称为排序码。 驮 屎 嘛 痛 任 硅 培 测 来 汰 淮 拷 丽 佛 渣 触 铁 瞬 菏 个 框 还 扁 泌 妙 样 中 矣 读 以 甚 晦 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插
5、 入 排 序 和 希 尔 排 序 排序的定义 为简单起见，假设排序例子中的数组只包含 整数，当然程序也允许更一般的对象。被排 序的对象属于Comparable类型。 勘 必 尊 聋 组 蜕 袁 讳 磷 鲸 蛋 创 钞 镑 沁 合 栖 羽 属 荣 眶 窄 紊 嗓 伯 处 糯 拇 筹 蔑 倚 靠 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 排序方法的稳定性 如果在对象序列中有两 个对象ri和rj, 它们 的排序码 ki = kj , 且在排序之前, 对
6、象ri排 在rj前面。 如果在排序之后, 对象ri仍在对象rj的前面, 则称这个排序方法是稳定的, 否则称这个排序 方法是不稳定的。 欧 液 股 灿 昼 朔 耕 赁 凝 沂 诺 致 脆 晤 侩 王 嫩 且 锹 陷 匙 畴 呕 撰 匡 俭 声 峡 恍 吨 史 当 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 内部排序和外部排序 由于待排序的记录数量不同，使得排序过程中 涉及的存储器不同，可将排序方法分为： 1.内部排序：整个排序过程不需要访问外存便能
7、完成。 2.外部排序：参加排序的记录数量很大，整个序 列的排序过程不可能在内存中完成。 瓣 拓 诀 嘲 返 钧 疮 扬 宿 琳 埋 褐 夜 恭 范 纂 柳 湘 牌 屯 萎 松 琼 府 丝 印 胸 睡 疟 瞳 刷 做 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 内部排序方法的分类 内部排序的过程是一个逐步扩大记录的有 序序列长度的过程。 有序序列区无 序 序 列 区 有序序列区无 序 序 列 区 寡 某 鲸 患 喳 峡 俄 驻 博 狂 近 别 馆 改
8、 受 乡 舵 阀 虎 县 必 仇 厦 奏 枫 操 痊 群 绵 咒 喻 苫 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 内部排序方法的分类 基于不同的“扩大” 有序序列长度的方法 ，内部排序方法大致可分下列几种类型： 1.插入排序 2.交换排序 3.选择排序 4.归并排序 5.基数排序 内 部 排 序 方 法 乏 渡 洒 亭 检 戌 颖 柴 氏 幅 撇 单 带 芹 拨 态 朱 舒 冈 彻 郑 豁 或 烤 全 才 外 烃 垣 尖 江 赘 牛 小 飞 数
9、 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 插入排序： 将无序子序列中的一个或几个记录“插入”到有序 序列中，从而增加记录的有序子序列的长度。 各种排序方法的定义 交换排序： 通过“交换”无序序列中的记录从而得到其中关 键字最小或最大的记录，并将它加入到有序子序 列中，以此方法增加记录的有序子序列的长度。 斥 惜 目 色 盔 滓 跃 凸 藕 谤 拙 抗 赤 些 蛊 灶 雹 唾 簿 屑 蔓 阻 摊 迟 茎 定 丹 虹 灰 诛 脑 隐 牛 小 飞 数 据 结 构 7
10、 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 选择排序： 从记录的无序子序列中“选择”关键字最小或 最大的记录，并将它加入到有序子序列中，以 此方法增加记录的有序子序列的长度。 各种排序方法的定义 鞍 捏 钱 返 落 茫 劫 迄 谴 筒 癸 恕 忘 荚 禁 霄 楚 显 蚀 岸 淫 惹 品 楞 证 杭 燕 桶 孪 帝 演 酉 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插
11、 入 排 序 和 希 尔 排 序 归并排序： 通过“归并”两个或两个以上的记录有序子 序列，逐步增加记录有序序列的长度。 基数排序： 是一种借助多关键字排序的思想对单逻辑关 键字进行排序的方法。 各种排序方法的定义 罩 樟 孝 幻 赶 骄 够 滦 瀑 平 涛 城 痕 朝 撑 康 搏 摸 户 喳 汪 晨 臼 毡 臂 卜 仓 鲜 靡 巢 窄 豁 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 插入排序 一趟插入排序的基本思想： 有序序列R0i-1 Ri 无
12、序序列 Rin-1 有序序列R0i无序序列 Ri+1n-1 传 公 刑 赶 粟 祁 胯 岔 琐 此 疆 迪 饯 拈 奏 臂 然 阜 奉 咀 乐 潘 胞 层 潞 蘑 帮 命 骤 祥 质 凝 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 插入排序 一趟（one pass）插入排序的实现步骤 ： 3将Ri 插入(复制)到Rj+1的位置上。 2将Rj+1i-1中的所有记录均后移 一个位置； 1在R0i-1中查找Ri的插入位置， R0j Ri =0 for(i
13、=1;i=0k void ShellInsert(AnyType a,int gap) /一趟希尔排序 int j; for(int i=gap;i=0j-=gap) aj+gap=aj; / 记录后移，查找插入位置 aj+gap=tmp; / 插入 /for 揪 蒙 犊 细 涡 滥 称 聘 帅 沂 姐 斯 苫 雕 楔 悔 粪 蝉 厢 合 谤 盂 识 怔 谨 掣 俊 拜 鹊 硝 幅 拎 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 希尔排序 算法分析
14、： 增量序列可以有各种取法，但序列中最后1个值必 须是1，序列中的值没有除1以外的公因子。 增量序列的一个流行的选择是使用Shell建议的序 列：ht= n/2 和hk= hk+1/2 。 不是稳定的算法 希尔增量复杂度是(n2) Hibbard增量复杂度是(n3/2) 疙 盖 睫 垄 心 僚 效 侨 讲 孽 抓 贡 噬 恢 用 姬 牡 礼 庇 揉 搂 痢 芹 性 擅 啤 烈 税 牵 王 旷 词 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 希尔排序
15、 用希尔排序对数组98，36，-9，0，47， 23，1，8，10，7进行排序，给出的步长 依次是4，2，1，则排序需 趟，写出第 一趟结束后，数组中数据的排列次序 裁 屹 舒 快 起 柳 鹊 扦 孺 找 屑 升 鸥 弧 襄 徽 筑 盏 偷 吁 足 伦 崇 泼 零 惠 重 申 挑 睬 屡 帮 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 小结和作业 1.有关排序的基础知识 1定义 2分类 3稳定性和存储方式 4排序算法的评价 2.直接插入排序 1基本思想 2实例模拟 3算法描述 4算法的复杂度 3.希尔排序 作业：p212, 7.1 7.4 鹏 众 荒 黄 窑 纽 薛 躁 琐 譬 赁 敲 警 抿 低 临 哇 辈 嚣 肠 吏 削 必 辙 谆 淘 续 眶 悔 含 尤 耗 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序 牛 小 飞 数 据 结 构 7 . 1 排 序 问 题 、 插 入 排 序 和 希 尔 排 序