《算法与数据结构》第8章排序及基本算法ppt151

算 法 与 数 据 结 构第 8章 排 序 及 基 本 算 法 排 序 及 基 本 算 法n为 了 便 于 检 索 ， 人 们 通 常 希 望 能 在 计 算 机 中 保 存 的 数 据 是按 关 键 字 值 大 小 排 列 的 有 序 表 。n这 是 因 为 对 于 有 序 表 可 以 采 用 检 索 效 率 较 高 的 二 分 法 检 索算 法 ， 其 平 均 检 索 长 度 为 log2(n+1)-1;而 对 于 无 序 表 只 能 进行 顺 序 检 索 ， 其 平 均 检 索 长 度 为 (n+1)/2。n又 如 为 了 方 便 检 索 ， 需 要 构 造 二 叉 检 索 树 、 B树 和 B+树 等 树表 ， 构 造 这 些 树 表 的 过 程 本 身 就 是 一 个 排 序 的 过 程 。 n在 现 今 的 计 算 机 系 统 中 ， 有 相 当 大 的 一 部 分 CPU时 间 开 销是 用 于 对 数 据 的 排 序 整 理 上 的 。n因 此 ， 学 习 和 研 究 各 种 排 序 算 法 ， 分 析 并 设 计 出 高 效 适 用的 排 序 算 法 ， 是 摆 在 计 算 机 科 学 工 作 者 面 前 的 重 要 课 题 之一 。 第 8章 排 序 及 基 本 算 法8.1 排 序 的 基 本 概 念8.2 插 入 排 序8.3 交 换 排 序8.4 选 择 排 序8.5 归 并 排 序8.6 基 数 排 序8.7 各 种 内 部 排 序 方 法 的 比 较 和 选 择8.8 外 部 排 序 简 介 8.1 排 序 的 基 本 概 念 n 排 序 是 数 据 处 理 中 的 重 要 运 算 ， 其 功 能 是 将 一 组数 据 元 素 （ 或 记 录 ） 的 任 意 序 列 ， 经 重 新 排 列 整 理成 为 按 关 键 字 值 大 小 有 序 的 序 列 。n 排 序 的 实 际 应 用 领 域 也 是 非 常 广 泛 的 。 例 如 在 实际 问 题 的 数 据 处 理 中 常 会 遇 到 这 样 的 情 况 ， 需 要 把若 干 名 字 如 人 名 、 地 名 、 国 名 、 书 名 、 校 名 、 物 名等 按 字 母 顺 序 列 表 ； 需 要 把 若 干 数 值 如 各 种 考 试 分数 、 田 赛 的 长 度 、 径 赛 的 时 间 等 按 成 绩 次 序 排 名 ；需 要 把 若 干 不 同 属 性 的 记 录 按 照 某 种 方 法 排 列 次序 。 所 有 这 些 都 是 排 序 问 题 ， 都 需 要 把 一 组 数据 元 素 或 记 录 按 照 某 种 特 定 的 次 序 排 列 起 来 。 排 序 的 基 本 概 念 （ 续 ） n 排 序 的 确 切 定 义 可 以 描 述 为 ：n设 （ R1， R2 Rn） 是 某 文 件 的 n个 记 录 ， 其 相 应 的 关 键字 为 （ K1， K2 Kn） 。n排 序 （ sort） 是 这 样 一 种 操 作 ， 它 确 定 文 件 中 n个 记 录的 一 种 排 列 （ Rj1， Rj2 Rjn） ， 使 得 其 相 应 关 键 字 满 足递 增 （ 即 不 减 ） 关 系 Kj1Kj2Kjn或 递 减 （ 即 不 增 ） 关系 Kj1Kj2Kjn。 n若 关 键 字 满 足 递 增 （ 即 不 减 ） 关 系 时 ， 称 作 按 关 键 字 升序 排 序 (ascending sort)；n若 关 键 字 满 足 递 减 （ 即 不 增 ） 关 系 时 ， 称 作 按 关 键 字 降序 排 序 (descending sort)。 排 序 的 基 本 概 念 （ 续 ） n在 前 面 定 义 中 ， 关 键 字 Ki(i=1， 2 n)称 作 排 序码 （ sort code） 。n排 序 码 可 以 是 记 录 的 主 关 键 字 ， 也 可 以 是 次 关 键字 ， 或 者 是 多 个 关 键 字 的 组 合 （ 即 组 合 关 键 字 ） 。n当 排 序 码 是 主 关 键 字 时 ， 由 于 主 关 键 字 可 以 惟 一标 识 一 个 记 录 ， 所 以 排 序 结 果 是 惟 一 的 。n当 排 序 码 是 次 关 键 字 时 ， 同 一 关 键 字 值 可 能 标 识了 两 个 或 两 个 以 上 的 记 录 ， 所 以 排 序 结 果 不 惟 一 。 排 序 的 基 本 概 念 （ 续 ） n若 相 同 关 键 字 值 的 记 录 在 排 序 前 后 的 相 对 位 置 不会 发 生 改 变 ， 即 若 Ri与 Rj的 关 键 字 相 同 （ Ki=Kj） 且在 排 序 前 Ri在 Rj之 前 ， 排 序 后 的 Ri仍 在 Rj之 前 ， 则称 所 用 的 排 序 算 法 是 稳 定 的 (stable)；n否 则 ， 若 排 序 前 后 相 同 关 键 字 值 的 记 录 其 相 对 位置 可 能 发 生 改 变 ， 即 排 序 之 后 的 序 列 中 有 可 能 出现 Rj在 Ri之 前 的 情 况 ， 则 称 所 用 的 排 序 算 法 是 不 稳定 的 。 n当 排 序 码 是 组 合 关 键 字 时 ， 通 常 称 作 多 关 键 字 排序 ， 其 排 序 结 果 的 惟 一 性 取 决 于 组 合 关 键 字 是 否能 惟 一 标 识 一 个 记 录 。 排 序 的 分 类 n根 据 排 序 过 程 中 待 排 序 文 件 存 放 的 位 置 不 同 ， 可 以把 排 序 分 为 内 部 和 外 部 排 序 两 大 类 。n内 部 排 序 是 指 待 排 序 文 件 放 在 内 存 中 进 行 排 序的 排 序 ； 内 部 排 序 适 用 于 记 录 个 数 不 很 多 的 较 小待 排 序 文 件 的 排 序 ；n外 部 排 序 是 指 在 待 排 序 文 件 很 大 时 ， 内 存 中 不能 一 次 容 纳 全 部 记 录 ， 还 要 借 助 于 外 存 存 放 待 排序 文 件 ， 在 排 序 过 程 中 需 要 对 外 存 进 行 访 问 的 排序 ； 外 部 排 序 则 适 用 于 记 录 个 数 太 多 不 能 一 次 全部 放 入 内 存 的 较 大 待 排 序 文 件 的 排 序 。 排 序 的 分 类 （ 续 ） n按 排 序 中 所 用 策 略 的 不 同 ：n内 部 排 序 通 常 可 以 分 为 插 入 排 序 、 选 择 排 序 、交 换 排 序 、 归 并 排 序 和 分 配 排 序 这 五 类 ， 每 一类 中 不 同 的 排 序 算 法 都 是 基 于 同 一 策 略 的 不 同方 法 。n外 部 排 序 多 是 采 用 多 路 归 并 方 法 进 行 排 序 。 内 部 排 序 文 件 的 组 织 形 式n 每 种 内 部 排 序 方 法 均 可 在 不 同 的 存 储 结 构 上 实 现 。通 常 待 排 序 文 件 的 组 织 形 式 有 三 种 方 式 ：n以 一 维 数 组 作 为 组 织 形 式 ， 排 序 过 程 是 对 记 录 本 身 进行 物 理 重 排 ， 通 过 比 较 和 判 定 把 记 录 移 动 到 合 适 的 位 置 ；n以 链 表 （ 动 态 链 表 或 静 态 链 表 ） 作 为 组 织 形 式 ， 排 序过 程 中 无 需 移 动 记 录 ， 仅 需 修 改 指 针 即 可 ， 通 常 把 这 类排 序 称 为 表 排 序 ； n为 待 排 序 文 件 组 织 一 个 辅 助 表 ， 如 组 织 一 张 含 关 键 字和 指 向 记 录 指 针 的 索 引 表 ， 在 排 序 过 程 中 只 需 对 辅 助 表的 表 目 进 行 物 理 重 排 ， 不 需 移 动 记 录 本 身 ， 在 排 序 结 束后 按 辅 助 表 调 整 记 录 位 置 。 排 序 的 基 本 概 念 （ 续 ）n排 序 的 方 法 很 多 ， 每 一 种 方 法 都 有 自 己 的 优 缺 点 ，适 用 于 在 不 同 的 环 境 下 使 用 ， 很 难 说 哪 一 种 方 法是 最 好 的 方 法 。n由 于 所 需 的 辅 助 空 间 的 量 一 般 都 不 大 ， 所 以 排 序的 时 间 代 价 是 衡 量 排 序 算 法 的 最 重 要 的 因 素 。 n内 部 排 序 的 时 间 代 价 主 要 用 关 键 字 的 比 较 次 数 和 记 录的 移 动 次 数 来 衡 量 ；n而 外 部 排 序 的 时 间 代 价 主 要 用 访 问 外 存 储 器 的 次 数 来衡 量 。 排 序 的 基 本 概 念 （ 续 ）n在 本 章 主 要 讨 论 内 部 排 序 算 法 ， 以 记 录 数 组 作 为待 排 序 文 件 的 组 织 形 式 ， 并 假 定 关 键 字 均 为 整 数 ，按 递 增 次 序 讨 论 排 序 算 法 （ 即 讨 论 升 序 排 序 问 题 ） 。n待 排 序 文 件 中 记 录 结 构 类 型 定 义 如 下 ： typedef struct int key; /*关 键 字*/ elemtype otheritems; /*其它 域*/ recordtype /*记 录 类 型 标 识 符*/ 第 8章 排 序 及 基 本 算 法8.1 排 序 的 基 本 概 念8.2 插 入 排 序8.3 交 换 排 序8.4 选 择 排 序8.5 归 并 排 序8.6 基 数 排 序8.7 各 种 内 部 排 序 方 法 的 比 较 和 选 择8.8 外 部 排 序 简 介 插 入 排 序n插 入 排 序 的 基 本 方 法 是 ： 每 次 将 一 个 待 排 序 的 记录 Ri， 按 其 关 键 字 Ki的 大 小 插 入 到 前 面 已 经 排 好 序的 部 分 文 件 中 的 适 当 位 置 ， 直 到 全 部 记 录 插 完 整个 文 件 已 排 好 序 为 止 。n本 节 介 绍 的 插 入 排 序 方 法 有 直 接 插 入 排 序 和 希 尔排 序 ； 并 简 介 二 分 法 插 入 排 序 、 二 路 插 入 排 序 和共 享 栈 插 入 排 序 。 8.2 插 入 排 序8.2.1 直 接 插 入 排 序8.2.2 希 尔 排 序8.2.3 其 它 插 入 排 序 简 介 直 接 插 入 排 序 n直 接 插 入 排 序 （ straight insertion sort） 是 一 种 最 简单 的 排 序 方 法 。n它 的 基 本 思 路 是 ：n依 次 把 待 排 序 的 记 录 逐 个 插 入 已 排 好 序 的 序 列 中 。n一 开 始 ， 第 一 个 记 录 是 一 个 长 度 为 1的 有 序 序 列 ； n从 第 二 个 记 录 起 ， 每 次 用 第 i(i=2， 3 n)个 记 录 的 关 键字 Ki与 前 面 有 序 序 列 中 记 录 的 关 键 字 Ki-1、 Ki-2 K1进 行比 较 ， 从 而 找 到 Ki所 在 记 录 应 该 插 入 的 位 置 并 依 次 后 移各 记 录 后 插 入 之 ， 使 得 有 序 序 列 的 长 度 加 1；n这 样 插 入 n-1次 就 会 得 到 n个 记 录 的 有 序 序 列 ， 从 而 完 成整 个 文 件 的 排 序 工 作 。 直 接 插 入 排 序 举 例n例 如 ， 已 知 待 排 序 文 件 中 记 录 的 关 键 字 序 列 为 （ 23，48， 32， 107， 86， 75， ， 68） ， 直 接 插 入 排 序 的 过程 可 示 意 如 下 ： n其 中 ， 方 括 号 表 示 已 排 好 序 的 序 列 ， i表 示 插 入 第 i个 记 录 。 直 接 插 入 排 序 （ 续 ） n 在 插 入 第 i个 记 录 时 ， 用 Ki和 前 面 已 排 好 序 记 录 的 关 键 字比 较 ， 若 Ki小 则 后 移 一 个 记 录 ， 直 到 Ki不 小 于 时 插 入 位 置 找到 了 ， 直 接 插 入 Ki完 成 第 i个 记 录 的 插 入 。n由 于 后 移 操 作 会 覆 盖 第 i个 记 录 ， 在 算 法 描 述 中 可 在 进 行第 i个 记 录 插 入 之 前 ， 先 保 存 其 于 R0中 再 进 行 比 较 后 移 操 作 ；这 个 附 加 的 R0还 可 起 到 “ 监 视 哨 ” 的 作 用 ， 即 当 Ki小 于 前 面有 序 序 列 中 的 每 一 个 关 键 字 时 ， 在 和 R0中 关 键 字 （ 它 本 身 ）比 较 时 不 会 小 于 ， 既 找 到 了 正 确 的 插 入 位 置 ， 又 避 免 了 循环 控 制 变 量 的 越 界 检 查 。 n设 置 监 视 哨 是 一 种 程 序 设 计 技 巧 ， 既 使 程 序 控 制 简 单 ， 又节 省 了 测 试 时 间 提 高 了 检 索 效 率 。 直 接 插 入 排 序 的 算 法 描 述 n 直 接 插 入 排 序 的 算 法 描 述 如 下 ： void insertsorting(recordtype R,int n) int i,j; for(i=2;i=n;i+) R0=Ri; j=i-1; while(R0.key R0和 R0=Ri） ,无 需 记 录 后 移 ；其 比 较 次 数 为 n-1次 ， 移 动 操 作 次 数 为 2（ n-1） 次 ，算 法 的 时 间 复 杂 度 为 O(n)。 直 接 插 入 排 序 的 算 法 分 析 (续 ) n在 最 坏 的 情 况 下 是 待 排 序 文 件 中 各 记 录 为 关 键 字 的逆 序 排 列 （ 即 递 减 序 列 ） ， 每 一 趟 中 需 要 和 前 面 已排 好 序 的 i-1个 记 录 以 及 监 视 哨 中 R0进 行 关 键 字 值的 比 较 ， 即 第 i趟 中 需 进 行 i次 比 较 操 作 ；n向 后 移 动 次 数 为 i-1次 ， 加 上 与 监 视 哨 之 间 的 两 次 移动 ， 第 i趟 需 要 移 动 记 录 i+1次 ； 总 的 比 较 次 数 为 次 ， 总 的 移 动 次 数 为 次 ， 算法 的 时 间 复 杂 度 为 O(n2)。 直 接 插 入 排 序 的 算 法 分 析 (续 ) n若 初 始 文 件 中 各 记 录 是 随 机 排 列 ， 即 关 键 字 的 各 种排 列 的 出 现 概 率 相 同 时 ， 我 们 可 取 上 述 最 好 与 最 坏情 况 的 平 均 值 作 为 比 较 和 移 动 的 平 均 次 数 ， 约 为 n2/4,由 此 可 得 直 接 插 入 排 序 的 时 间 复 杂 度 为 O(n2)。n由 于 直 接 插 入 排 序 在 整 个 排 序 过 程 中 只 需 一 个 记 录的 辅 助 空 间 （ 即 R0） ， 所 以 其 空 间 复 杂 度 为 O(1)。由 于 对 于 相 同 关 键 字 值 的 记 录 在 排 序 前 后 相 对 位 置不 会 发 生 变 化 （ 如 上 例 中 的 48和 ） ， 所 以 直 接 插 入排 序 是 一 种 稳 定 的 排 序 方 法 。 8.2 插 入 排 序8.2.1 直 接 插 入 排 序8.2.2 希 尔 排 序8.2.3 其 它 插 入 排 序 简 介 希 尔 排 序n希 尔 排 序 （ shells method） ， 又 称 作 缩 小 增 量 排 序（ diminishing increatment） 。 它 是 1959年 由 D.L.Shell提 出 来的 对 直 接 插 入 排 序 的 一 种 改 进 方 法 。n希 尔 排 序 是 不 稳 定 的 排 序 算 法 。 n由 直 接 插 入 排 序 的 分 析 可 知 ， 在 待 排 序 文 件 已 按 关 键 字 值递 增 有 序 时 的 时 间 复 杂 度 为 O(n)， 在 逆 序 时 的 时 间 复 杂 度 为O(n2)。n换 句 话 说 ， 如 果 待 排 序 文 件 能 够 基 本 有 序 ， 则 文 件 中 的 大多 数 记 录 都 不 需 要 进 行 插 入 （ 即 后 移 ） 操 作 ， 整 个 排 序 的 时间 开 销 就 可 以 大 大 减 少 。 n另 外 ， 当 n的 值 很 小 时 ， n2的 值 受 n的 值 的 影 响 也 不 太 大 ， 直接 插 入 排 序 的 效 率 也 比 较 高 。 希 尔 排 序 正 是 基 于 这 两 点 考 虑而 得 到 的 对 直 接 插 入 排 序 的 一 种 改 进 方 法 。 希 尔 排 序 的 方 法n希 尔 排 序 的 方 法 是 ：n先 选 取 一 个 小 于 n的 整 数 d1作 为 第 一 个 增 量 ， 把待 排 序 文 件 中 的 全 部 记 录 分 成 d1个 组 ， 将 所 有 距离 为 d1倍 数 的 记 录 放 在 同 一 个 组 中 ， 在 各 组 内 进行 直 接 插 入 排 序 ；n然 后 选 取 第 二 个 增 量 d2d1， 重 复 上 述 的 分 组 和排 序 工 作 ； 如 此 不 断 地 选 取 更 小 的 增 量 d3，d4 并 重 复 上 述 的 分 组 和 排 序 工 作 ， n直 到 所 选 取 增 量 di=1(didi-1d2d1)时 所 有 记录 放 在 同 一 组 中 进 行 直 接 插 入 排 序 后 为 止 。 希 尔 排 序 的 方 法 （ 续 ）n希 尔 排 序 方 法 的 一 开 始 组 数 较 多 而 组 中 记 录 较 少 ， 各 组 中记 录 的 直 接 插 入 排 序 是 处 在 n值 很 小 的 情 况 下 进 行 ， 有 着 较高 的 效 率 ； 并 且 在 不 满 足 次 序 时 的 移 动 ， 是 用 较 少 的 移 动 次数 而 得 到 了 记 录 的 较 大 移 动 距 离 。n随 着 di减 小 ， 组 数 变 少 组 中 记 录 个 数 变 多 的 同 时 ， 组 中 记 录也 逐 步 变 得 基 本 有 序 ， 使 得 在 一 趟 中 进 行 直 接 插 入 排 序 时 的效 率 大 大 地 提 高 。n所 以 希 尔 排 序 始 终 是 在 较 高 的 效 率 下 工 作 。 希 尔 排 序 中 增量 di的 选 择 可 以 有 不 同 的 取 法 ， 一 般 是 采 用 希 尔 在 最 早 时 提出 的 方 法 ， 即 d1=,di+1=(i=2， 3， 4 )。 n但 也 有 人 提 出 不 同 的 di选 取 方 法 ， 如 克 努 特 （ Knuth） 提 出的 方 法 是 d1=,di+1=(i=2， 3， 4 )。 如 何 选 取 增 量 序 列 才 能 产生 最 好 的 排 序 效 果 ， 至 今 仍 无 法 从 数 学 角 度 得 出 圆 满 的 结 论 ；然 而 逐 步 缩 小 增 量 和 最 后 一 次 增 量 为 1是 大 家 不 争 的 事 实 。 希 尔 排 序 举 例n设 待 排 序 文 件 中 有 10个 记 录 ， 初 始 关 键 字 序列 为 (52,38,66,87,77,16,30,62,07)， 增 量 序 列 依次 为 5,3,1， 排 序 过 程 如 下 ： 希 尔 排 序 举 例 （ 续 ） 希 尔 排 序 举 例 （ 续 ）n第 一 趟 排 序 时 d1=5， 把 待 排 序 文 件 分 成 五 组 ， 即（ R1， R6） 、 （ R2， R7） 、 （ R3， R8） 、 （ R4， R9）和 （ R5， R10） ， 各 组 中 第 一 个 记 录 都 自 成 长 度 为 1的有 序 区 ， 依 次 把 各 组 的 第 二 个 记 录 插 入 有 序 区 中 得 到第 一 趟 排 序 结 果 ；n第 二 趟 排 序 时 d2=3， 把 待 排 序 文 件 分 成 三 组 ， 即（ R1， R4， R7， R10） 、 （ R2， R5， R8） 和 （ R3， R6，R9） ， 对 各 组 进 行 直 接 插 入 排 序 后 得 到 第 二 趟 排 序 结果 ； n第 三 趟 排 序 时 d3=1， 整 个 待 排 序 文 件 为 一 组 ， 对 整个 文 件 做 直 接 插 入 排 序 得 到 的 第 三 趟 排 序 结 果 ， 使 整个 待 排 序 文 件 按 关 键 字 值 有 序 ， 即 得 到 最 终 的 排 序 结果 。 希 尔 排 序 的 算 法 描 述 (不 设 置 监 视 哨 )n 若 不 设 置 监 视 哨 ， 希 尔 排 序 的 算 法 可 描 述 如 下 ： void shellsorting(recordtype R,int n) int i,j,d; d = n; do d = (d+1)/2; for(i = d+1;i d) /*shellsorting end*/ 希 尔 排 序 （ 续 ）n需 要 说 明 的 是 ， 算 法 中 没 有 调 用 直 接 插 入 排 序 算 法insertsorting， 而 是 独 立 设 计 直 接 插 入 排 序 的 部 分 ； 这是 因 为 希 尔 排 序 中 距 离 为 d的 倍 数 的 记 录 为 一 组 ， 组中 成 员 记 录 之 间 有 间 隔 不 连 续 不 能 直 接 调 用 的 缘 故 。n另 外 ， 在 for循 环 中 的 分 组 执 行 直 接 插 入 排 序 的 过 程 ，是 依 次 先 插 入 d个 组 中 的 第 二 个 记 录 ， 再 插 入 d个 组 中的 第 三 个 记 录 最 后 插 入 d个 组 中 的 最 后 一 个 记 录 ；是 d个 组 的 交 替 插 入 过 程 ， 而 不 是 一 个 组 的 直 接 插 入排 序 完 成 后 再 进 行 下 一 组 ， 这 样 有 利 于 算 法 设 计 的 简洁 性 和 算 法 描 述 的 方 便 性 。 希 尔 排 序 （ 续 ）n 如 果 考 虑 设 置 监 视 哨 ， 很 自 然 地 会 考 虑 到 仿 照 直 接 插 入 排 序算 法 中 的 监 视 哨 设 置 办 法 。 对 于 增 量 为 d的 一 趟 希 尔 排 序 ， 待排 序 文 件 被 分 成 d 组 ， 各 组 中 记 录 之 间 的 距 离 为 d； 需 要 在 R1到 Rd处 设 置 监 视 哨 ， 而 在 Rd+1到 Rd+n处 安 排 待 排 序 文 件中 的 n个 记 录 。 由 于 在 各 趟 排 序 中 的 增 量 d1,d2 di是 逐 次 缩 小的 ， 而 待 排 序 文 件 中 各 记 录 的 位 置 空 间 安 排 好 之 后 不 宜 变 动（ 移 动 需 时 间 开 销 ） ， 所 以 d可 选 为 di中 的 最 大 值 d1， 即 一 次 性安 排 监 视 哨 空 间 并 固 定 不 变 ；n另 外 ， 监 视 哨 中 的 值 应 在 不 同 组 中 的 不 同 记 录 插 入 时 安 排 不同 的 值 （ 即 待 插 入 记 录 的 值 ） ， 但 是 多 次 更 换 监 视 哨 中 的 值 既繁 琐 又 影 响 效 率 ， 我 们 可 以 考 虑 在 排 序 之 前 一 次 性 设 置 各 监 视哨 的 值 ， 可 设 置 为 不 超 过 待 排 序 文 件 中 最 小 关 键 字 值 的 某 一 个值 如 -maxint。 这 种 监 视 哨 的 设 置 方 法 ， 没 有 在 监 视 哨 中 保 存各 组 中 的 一 个 个 待 插 入 记 录 ， 但 可 以 统 一 保 存 待 插 入 记 录 于R0中 。 希 尔 排 序 的 算 法 描 述 (设 置 监 视 哨 )n 设 置 监 视 哨 的 希 尔 排 序 算 法 可 描 述 如 下 ： void shellsort(recordtype R,int n) int i,j,d; for(i=1;i=(n+1)/2;i+) Ri.key = -maxint; d = n; do d = (d+1)/2; for(i=2*d+1;i=d+n;i+) j = i; R0 = Rj; while(R0.key 1); /*shellsort end*/ 希 尔 排 序 的 算 法 分 析n在 前 面 给 出 的 两 个 算 法 ， 除 了 是 否 设 置 监 视 哨 外 ， 排序 的 方 法 是 相 同 的 ， 其 时 间 复 杂 度 也 是 相 同 的 ； 其 增量 序 列 为 d1= ， di= (i2)。 算 法 中 的 主 要 时 间开 销 在 于 三 重 循 环 ：n外 层 do-while循 环 控 制 排 序 趟 数 ， 共 执 行 log2n次 。n中 层 的 for循 环 控 制 一 趟 中 各 组 记 录 的 直 接 插 入 排 序 ， 执 行次 数 依 次 为 次 ； 其 平 均 次 数 为 ； 即中 层 for循 环 的 平 均 执 行 次 数 不 超 过 n。 n内 层 的 while循 环 确 定 各 组 中 每 个 记 录 的 插 入 位 置 ， 进 行 关键 字 的 比 较 和 记 录 的 移 动 操 作 ； 希 尔 排 序 的 算 法 分 析 （ 续 ）n在 最 好 的 情 况 下 只 执 行 一 次 比 较 而 无 记 录 移 动 ， 其 一 趟 中总 的 比 较 次 数 与 中 层 f o r 循 环 的 执 行 次 数 相 同 ，为 ；n而 一 趟 中 执 行 插 入 的 次 数 为 n-di， 即 平 均 比 较 次 数 不 超过 ,更 不 会 超 过 log2n次 ；n由 于 希 尔 排 序 算 法 中 开 始 时 两 个 记 录 一 组 ， 以 后 随 着 组 数的 减 少 组 中 记 录 增 多 也 逐 步 基 本 有 序 ， 所 以 在 n较 大 时 的 其它 情 况 下 的 平 均 比 较 次 数 也 是 接 近 于 最 好 情 况 下 的 次 数 log2n或 是 它 的 线 性 函 数 ， 而 移 动 次 数 或 平 均 移 动 次 数 是 远 远 小 于比 较 次 数 和 平 均 比 较 次 数 的 ； n由 此 得 内 层 while循 环 的 平 均 执 行 次 数 为 O(log2n)阶 函 数 。 由算 法 分 析 的 乘 法 法 则 可 知 ， 前 面 给 出 的 两 个 希 尔 排 序 算 法 ，shellsorting和 shellsort的 时 间 复 杂 度 为 O(n(log2n)2)。 8.2 插 入 排 序8.2.1 直 接 插 入 排 序8.2.2 希 尔 排 序8.2.3 其 它 插 入 排 序 简 介 1.二 分 法 插 入 排 序 n 由 第 七 章 的 讨 论 我 们 知 道 ， 对 有 序 表 采 用 二 分 法 检 索 ， 检索 性 能 大 大 优 于 顺 序 检 索 。n如 果 我 们 把 直 接 插 入 排 序 中 的 由 后 向 前 顺 序 检 索 寻 找 插 入位 置 的 方 法 改 为 用 二 分 法 检 索 来 实 现 ， 当 n较 大 时 就 可 以 大幅 度 地 降 低 关 键 字 的 比 较 次 数 。 我 们 把 经 过 这 种 改 进 后 的 插入 排 序 方 法 ， 称 作 二 分 法 插 入 排 序 （ binary insertion sort） 。n二 分 法 插 入 排 序 与 直 接 插 入 排 序 相 比 较 ， 仅 是 减 少 了 寻 找插 入 位 置 时 的 关 键 字 比 较 次 数 ， 记 录 的 移 动 次 数 没 有 改 变 ，其 时 间 复 杂 度 仍 为 O(n 2)；n所 需 的 辅 助 存 储 空 间 也 与 直 接 插 入 排 序 相 同 ， 也 是 稳 定 的排 序 方 法 （ 在 检 索 位 置 出 现 关 键 字 值 相 等 时 需 后 移 插 入 位 置指 示 器 变 量 ， 否 则 为 不 稳 定 方 法 ） 。 2.二 路 插 入 排 序 n二 路 插 入 排 序 （ 2-way insertion sort） 是 在 二 分 法 插 入 排 序基 础 上 的 进 一 步 改 进 ， 改 进 的 目 标 是 减 少 排 序 过 程 中 记 录 的移 动 次 数 ， 但 为 此 多 开 销 了 n个 记 录 大 小 的 辅 助 存 储 空 间 。n其 具 体 方 法 是 ：n另 设 一 个 和 R同 类 型 的 数 组 S， 先 将 R1赋 给 S1， 并 将S1看 成 是 在 已 排 好 序 序 列 中 处 于 中 间 位 置 的 记 录 ；n然 后 从 R中 第 二 个 记 录 起 ， 依 次 插 入 到 S1之 前 或 S1之后 的 有 序 序 列 中 去 ， n若 待 插 记 录 的 关 键 字 小 于 S1.key则 插 入 S1之 前 的 有 序表 中 ， 否 则 插 入 S1之 后 的 有 序 表 中 。n在 算 法 实 现 时 ， 把 S数 组 看 成 是 一 个 循 环 数 组 ， 并 设 两 个 指针 first和 final分 别 指 示 排 序 过 程 中 得 到 的 有 序 序 列 中 的 第 一个 记 录 和 最 后 一 个 记 录 在 S中 的 位 置 。 二 路 插 入 排 序 举 例 二 路 插 入 排 序 举 例 （ 续 ） 二 路 插 入 排 序 （ 续 ） n在 二 路 插 入 排 序 中 ， 记 录 的 移 动 次 数 约 为 n2/8， 比直 接 插 入 排 序 减 少 移 动 次 数 约 一 半 。 它 只 能 减 少 移动 次 数 而 不 能 绝 对 避 免 移 动 记 录 ， 若 要 大 幅 度 降 低移 动 次 数 ， 可 改 变 存 储 结 构 为 静 态 链 表 ， 进 行 表 插入 排 序 。n此 外 ， 二 路 插 入 排 序 中 ， 当 R1为 待 排 序 文 件 中 最小 或 最 大 关 键 字 的 记 录 时 ， 完 全 失 去 优 越 性 退 化 为直 接 插 入 排 序 的 时 间 效 率 。 n二 路 插 入 排 序 ， 是 一 种 稳 定 的 排 序 方 法 。 3.共 享 栈 插 入 排 序 n共 享 栈 插 入 排 序 （ shared stack insertion sort）也 是 对 直 接 插 入 排 序 的 一 种 改 进 方 法 。n其 基 本 思 想 是 ：n把 待 排 序 的 记 录 数 组 R看 作 是 一 个 静 态 的 共 享 栈 （ 栈 1和栈 2） ， 栈 1按 数 组 下 标 由 小 到 大 方 向 增 长 ， 栈 2按 数 组 下标 由 大 到 小 方 向 增 长 ； 栈 1中 按 关 键 字 升 序 排 列 压 入 待 排序 记 录 ， 栈 2中 按 关 键 字 降 序 排 列 压 入 待 排 序 记 录 。 n一 开 始 先 比 较 R1和 Rn的 关 键 字 值 大 小 ， 若 R1Rn则 交 换 ； top1=1,top2=n；n然 后 把 R2到 Rn-1逐 一 插 入 两 个 栈 中 ， 插 入 的 过 程 中始 终 保 证 栈 1的 栈 顶 记 录 的 关 键 字 值 都 不 大 于 栈 2 的 栈 顶记 录 的 关 键 字 值 。 共 享 栈 插 入 排 序 （ 续 ）n为 此 需 要 区 分 以 下 三 种 情 况 并 作 相 应 处 理 ：n当 待 插 入 记 录 Ri的 关 键 字 值 不 小 于 栈 1 的 栈 顶 记 录 的 关键 字 值 且 不 大 于 栈 2的 栈 顶 记 录 的 关 键 字 值 时 ， 将 待 插 记 录压 入 栈 1 中 。 即 R i . k e y R t o p 1 . k e y 且Ri.keyRtop2.key时 进 栈 1， 只 须 改 变 top1的 值 为top1+1即 可 。n当 Ri.keytop2.key时 ， 由 栈 2反 复 传 送 记 录 到 栈 1，直 到 Ri.keytop2.key时 将 Ri插 入 栈 2。 由 栈 2传 送 到栈 1一 个 记 录 ， 需 要 把 Ri+1到 Rtop2-1的 记 录 后 移 一 个位 置 。 共 享 栈 插 入 排 序 举 例 共 享 栈 插 入 排 序 举 例 （ 续 ） 共 享 栈 插 入 排 序 （ 续 ）n共 享 栈 插 入 排 序 不 需 要 增 加 额 外 的 存 储 开 销 ， 在 时间 性 能 上 与 二 路 插 入 排 序 相 当 ， 而 且 有 效 地 避 免 了因 R1为 待 排 序 记 录 中 关 键 字 值 为 最 大 或 最 小 记 录时 完 全 失 去 优 越 性 的 不 足 。n若 增 加 存 储 开 销 另 设 与 R相 同 类 型 的 数 组 作 为 共 享栈 ， 则 可 以 进 一 步 减 少 移 动 次 数 ， 且 排 序 结 果 不 象二 路 插 入 排 序 那 样 要 使 用 循 环 数 组 解 释 。n共 享 栈 插 入 排 序 是 一 种 稳 定 的 排 序 方 法 。 第 8章 排 序 及 基 本 算 法8.1 排 序 的 基 本 概 念8.2 插 入 排 序8.3 交 换 排 序8.4 选 择 排 序8.5 归 并 排 序8.6 基 数 排 序8.7 各 种 内 部 排 序 方 法 的 比 较 和 选 择8.8 外 部 排 序 简 介 交 换 排 序n交 换 排 序 的 基 本 方 法 是 ， 两 两 比 较 待 排 序 记 录的 关 键 字 值 ， 并 交 换 那 些 不 满 足 顺 序 要 求 的 记 录对 ， 直 到 全 部 待 排 序 记 录 都 已 满 足 顺 序 要 求 时 为止 。n本 节 介 绍 两 种 交 换 排 序 的 方 法 ：n一 种 是 冒 泡 排 序 ， n一 种 是 快 速 排 序 。 8.3 交 换 排 序8.3.1 冒 泡 排 序8.3.2 快 速 排 序 冒 泡 排 序n冒 泡 排 序 （ bubble sort） 也 称 作 起 泡 排 序 ， 是一 种 简 单 的 排 序 方 法 。n它 是 通 过 相 邻 记 录 之 间 的 关 键 字 比 较 和 记 录 交 换 ，使 关 键 字 值 较 小 的 记 录 由 底 部 向 上 移 动 ， 而 关 键字 值 较 大 的 记 录 由 顶 部 向 下 移 动 ， 就 象 水 中 的 气泡 向 上 飘 浮 （ 冒 泡 ） 一 样 。 冒 泡 排 序 算 法n冒 泡 排 序 的 具 体 做 法 是 ：n将 关 键 字 纵 向 排 列 ， 然 后 自 下 而 上 地 对 相 邻 两 个 记 录 的关 键 字 进 行 比 较 ， 若 为 逆 序 （ 即 Rj-1.keyRj.key，j=n,n-12） 则 交 换 两 个 记 录 ， 直 到 全 部 记 录 都 比 较 和 交换 完 毕 （ 即 j=2） ， 第 一 趟 冒 泡 排 序 结 束 ；n此 时 最 小 关 键 字 值 的 记 录 上 浮 到 了 R1的 位 置 上 。 然 后对 n-1个 记 录 重 复 类 似 的 操 作 ， 次 小 关 键 字 值 的 记 录 上 浮到 R2的 位 置 上 。 n重 复 进 行 这 样 的 过 程 ， 直 到 没 有 记 录 需 要 交 换 为 止 （ 最多 需 n-1趟 冒 泡 排 序 ） ， 整 个 待 排 序 文 件 就 按 关 键 字 值 升序 排 列 完 毕 。 冒 泡 排 序 算 法 举 例n例 如 ， 对 于 8个 记 录 的 关 键 字 序 列 （ 46， 26， 43， 18，74， 21, ,57） ， 冒 泡 排 序 的 过 程 如 下 图 所 示 ： 冒 泡 排 序 算 法 （ 续 ）n由 该 冒 泡 排 序 的 实 例 ， 也 证 实 了 至 多 需 要 n-1趟 冒 泡排 序 即 可 完 成 整 个 排 序 。n事 实 上 存 在 不 需 要 n-1趟 就 可 以 完 全 排 好 序 的 情 况 ，如 上 例 的 第 五 趟 排 序 后 就 已 经 排 好 序 了 ；n其 识 别 办 法 是 ， 若 某 一 趟 冒 泡 排 序 过 程 中 没 有 进 行记 录 的 位 置 交 换 ， 则 说 明 待 排 序 文 件 已 经 完 全 排 好 序了 。 n为 此 ， 需 在 算 法 中 引 入 一 个 交 换 状 态 变 量 flag， 在每 一 趟 排 序 之 前 置 flag为 0， 每 次 交 换 时 给 flag加 1，若 一 趟 结 束 时 flag为 0则 终 止 算 法 。 冒 泡 排 序 的 算 法 描 述 void bubblesort(recordtype R,int n) int i,j,flag; recordtype temp; for(i=1;i= i+1;j-) if(Rj-1.key Rj.key) temp=Rj-1; Rj-1=Rj; Rj=temp; flag=flag+1; /*置 已 交 换 标 志 */ if(flag=0) break; /*bubblesort end */ 冒 泡 排 序 算 法 分 析n冒 泡 排 序 也 是 一 种 稳 定 的 排 序 方 法 。n其 时 间 复 杂 度 可 以 如 下 分 析 ：n在 最 好 的 情 况 下 ， 是 初 始 记 录 的 关 键 字 已 递 增 有 序 时 ，只 需 一 趟 排 序 ， 比 较 次 数 为 n-1， 没 有 交 换 记 录 即 记 录 的移 动 次 数 为 0；n在 最 坏 的 情 况 下 ， 是 初 始 记 录 递 减 有 序 （ 即 逆 序 ） 时 ，需 进 行 n-1趟 排 序 ， 比 较 次 数 为 ， 交 换 次数 为 ， 每 次 交 换 需 三 次 移 动 记 录 ， 其 移 动次 数 为 。 n在 平 均 情 况 下 ， 关 键 字 的 比 较 次 数 和 记 录 的 移 动 次 数 大约 为 最 坏 情 况 下 的 一 半 ， 因 此 冒 泡 排 序 算 法 的 时 间 复 杂 度为 O(n2)。 冒 泡 排 序 算 法 分 析 （ 续 ）n上 述 的 冒 泡 排 序 算 法 还 可 以 作 一 些 改 进 来 提 高 排 序速 度 ， 比 如 ：n在 每 趟 排 序 中 记 住 最 后 一 次 发 生 交 换 记 录 的 位 置 K， 因 为位 置 K之 前 的 记 录 都 已 排 好 了 序 ， 下 一 趟 的 排 序 可 以 终 止于 位 置 K而 不 必 进 行 到 预 定 的 下 界 位 置 i。n在 排 序 过 程 中 交 替 变 化 扫 描 比 较 的 方 向 ， 即 前 一 趟 由 后向 前 扫 描 ， 后 一 趟 则 由 前 向 后 扫 描 ， 而 不 是 一 直 都 由 后 向前 扫 描 。 由 后 向 前 扫 描 比 较 交 换 一 趟 ， 可 使 最 轻 的 气 泡 上浮 到 顶 部 ， 但 只 能 使 最 重 的 气 泡 下 沉 一 个 位 置 ； 由 前 向 后扫 描 比 较 交 换 一 趟 ， 可 使 最 重 的 气 泡 下 沉 到 底 部 ， 但 只 能使 最 轻 的 气 泡 上 浮 一 个 位 置 。 交 替 变 化 扫 描 方 向 可 以 加 速最 轻 和 最 重 的 气 泡 向 两 端 迅 速 沉 浮 ， 有 利 于 加 速 排 序 过 程 。 8.3 交 换 排 序8.3.1 冒 泡 排 序8.3.2 快 速 排 序 快 速 排 序n快 速 排 序 （ quick sort） 也 称 作 分 区 交 换 排 序 ， 是 对 冒 泡排 序 的 一 种 改 进 排 序 方 法 。 它 是 目 前 各 种 内 部 排 序 方 法 中 较快 的 方 法 ， 故 称 之 为 快 速 排 序 。n快 速 排 序 的 基 本 思 想 是 ：n在 待 排 序 文 件 的 n个 记 录 中 ， 任 取 一 个 记 录 （ 通 常 是 选取 第 一 个 记 录 ） 作 为 基 准 ；n经 过 一 趟 排 序 后 以 基 准 记 录 的 关 键 字 把 全 部 记 录 分 为 两部 分 ， 所 有 关 键 字 值 比 基 准 记 录 关 键 字 值 小 的 记 录 都 排列 在 基 准 记 录 之 前 ， 而 所 有 关 键 字 值 比 基 准 记 录 关 键 字值 大 的 记 录 都 排 列 在 基 准 记 录 之 后 ； n然 后 对 基 准 记 录 前 后 的 这 两 个 部 分 分 别 重 复 这 样 的 过 程 ，得 到 本 趟 排 序 的 两 个 新 到 位 的 基 准 和 四 个 部 分 如 此重 复 上 述 过 程 ， 直 到 每 一 个 部 分 只 剩 下 一 个 记 录 （ 即 全部 到 位 ） 时 为 止 。 快 速 排 序 算 法n设 两 个 指 示 器 变 量 i和 j， 分 别 指 向 待 排 序 区 间 的 第 一 个 记录 和 最 后 一 个 记 录 ；n先 将 第 一 个 记 录 移 到 暂 存 变 量 temp中 ， 然 后 j从 区 间 的 最后 一 个 记 录 起 向 前 扫 描 ， 直 到 找 到 满 足 Rj.keytemp.key的 记 录 时 ， 将 Ri移 入 Rj中 ； n就 这 样 j自 j-1从 后 向 前 扫 描 一 次 移 入 一 个 Rj于 Ri中 ，i自 i+1从 前 向 后 扫 描 一 次 移 入 一 个 Ri于 Rj中 ， 反 复 交替 的 扫 描 和 移 动 记 录 ；n直 到 i=j时 把 temp移 入 Ri中 （ 区 间 中 第 一 个 记 录 应 在 的位 置 ） ， 它 把 整 个 待 排 序 区 间 分 割 为 相 互 独 立 的 两 个 更 小的 区 间 。 快 速 排 序 的 算 法 描 述n这 种 把 一 个 待 排 序 区 间 通 过 基 准 记 录 （ 第 一 个 记 录 ） 分 割成 为 两 个 区 间 的 一 次 分 割 排 序 算 法 如 下 ： int divideareasort(recordtype R,int s,int t) int i,j; recordtype temp; i=s; j=t; temp=Rs; do while(Rj.key=temp.key) if(ij) Ri=Rj; i+; 快 速 排 序 的 算 法 描 述 （ 续 ） while(Ri.key=temp.key) if(ij) Rj=Ri; j-; while(ij); Ri=temp; return i; /*divideareasort end*/ 快 速 排 序 的 算 法 描 述 （ 续 ）n 对 于 待 排 序 文 件 R利 用 一 次 分 割 区 间 排 序 算 法 时 ， 令s=1和 t=n即 可 完 成 第 一 趟 排 序 ； 由 此 得 到 的 两 个 更 小 的 区间 R1i-1和 Ri+1n， 继 续 利 用 算 法 divideareasort分 割 为 更 小 的 四 个 区 间 ； 如 此 一 直 进 行 下 去 ， 直 到 都 分 割为 只 有 一 个 记 录 时 排 序 结 束 。 调 用 divideareasort对 R 进 行 快 速 排 序 的 递 归 算 法 可 描 述 如 下 ： void quicksort(recordtype R,int s,int t) int i; if(st) i=divideareasort(R,s,t); quicksort(R,s,i-1); quicksort(R,i+1,t); /*quicksort end*/ 快 速 排 序 的 算 法 举 例n下 面 我 们 使 用 快 速 排 序 算 法 对 关 键 字 序 列 （36，73，65，97，13，27， ，29） 排 序 ， 在 下 面 的 排 序 过 程 示 例 中 ，先 给 出 第 一 趟 中 的 区 间 分 割 的 整 个 过 程 ， 然 后 给 出 各 趟 的排 序 结 果 ； 用 方 括 号 表 示 区 间 ， 用 方 框 表 示 暂 存 变 量temp的 关 键 字 值 （ 并 未 参 加 交 换 ， 在 分 割 完 成 后 才 放 入 最 终 位置 上 ） 。 快 速 排 序 的 算 法 举 例 （ 续 ） 快 速 排 序 的 算 法 举 例 （ 续 ） 快 速 排 序 的 算 法 举 例 （ 续 ） 快 速 排 序 的 算 法 分 析n快 速 排 序 过 程 中 各 趟 中 所 选 择 的 基 准 可以 用 一 棵 二 叉 树 来 表 示 ， 如 上 例 中 的 基准 二 叉 树 如 右 图 所 示 。 基 准 二 叉 树 反 映了 快 速 排 序 的 递 归 调 用 过 程 ， 也 便 于 我们 对 快 速 排 序 算 法 进 行 性 能 分 析 。 n快 速 排 序 的 基 准 二 叉 树 是 关 键 字 的 一 棵 二 叉 检 索 树 ， 其 中序 遍 历 序 列 就 是 关 键 字 的 升 序 排 列 。 n在 最 好 的 情 况 下 ， 基 准 二 叉 树 是 一 棵 理 想 的 平 衡 二 叉 检 索树 ， 深 度 为 ， 递 归 所 需 栈 的 存 储 开 销 为 O(log2n)，时 间 开 销 为 结 点 数 乘 平 均 检 索 长 度 ， 即 O(nlog2n)。 快 速 排 序 的 算 法 分 析 （ 续 ）n在 最 坏 情 况 下 ， 基 准 二 叉 树 是 一 棵 单 枝 二 叉 检 索 树 ， 深 度为n， 存 储 开 销 为O(n)， 时 间 开 销 为O(n2)。n在 平 均 情 况 下 ， 基 准 二 叉 树 是 一 棵 随 机 的 二 叉 检 索 树 ， 由于 二 叉 检 索 树 的 平 均 检 索 长 度 为O(log2n)， 故 时 间 开 销 也是O(nlog2n)。n为 了 避 免 初 始 关 键 字 序 列 有 序 或 基 本 有 序 时 快 速 排 序 蜕 化为 冒 泡 排 序 （ 即 基 准 二 叉 树 为 单 枝 或 近 似 单 枝 二 叉 树 ） 的 情况 ， 通 常 采 取 “ 三 者 取 中 ” 的 基 准 记 录 选 取 办 法 改 进 之 。 n所 谓 三 者 取 中 是 指 在Rs、Rt和R(s+t)/2三 者 中选 取 关 键 字 值 居 中 的 记 录 作 为 分 割 区 间 的 基 准 ， 这 种 选 取 基准 记 录 的 方 法 可 以 大 大 改 善 快 速 排 序 在 最 坏 情 况 下 的 性 能 。n快 速 排 序 算 法 是 一 种 不 稳 定 的 排 序 方 法 。 第 8章 排 序 及 基 本 算 法8.1 排 序 的 基 本 概 念8.2 插 入 排 序8.3 交 换 排 序8.4 选 择 排 序8.5 归 并 排 序8.6 基 数 排 序8.7 各 种 内 部 排 序 方 法 的 比 较 和 选 择8.8 外 部 排 序 简 介 选 择 排 序n选 择 排 序 的 基 本 方 法 是 ， 每 次 从 待 排 序 文 件 的各 个 记 录 中 ， 依 次 选 出 关 键 字 值 最 小 的 记 录 放 在已 排 好