《数据结构与算法》PPT课件

数 据 结 构 课 程 的 内 容 9.1 概 述9.2 插 入 排 序9.3 交 换 排 序9.4 选 择 排 序9.5 归 并 排 序9.6 基 数 排 序 9.1 概 述1. 什 么 是 排 序 ？ 将 一 组 杂 乱 无 章 的 数 据 按 一 定 的 规 律 顺 次 排 列 起来 。2. 排 序 的 目 的 是 什 么 ？存 放 在 数 据 表 中 按 关 键 字 排 序3.排 序 算 法 的 好 坏 如 何 衡 量 ？ 时 间 效 率 排 序 速 度 （ 即 排 序 所 花 费 的 全 部 比 较 次 数 ） 空 间 效 率 占 内 存 辅 助 空 间 的 大 小 稳 定 性 A和 B的 关 键 字 若 两 个 记 录 值 相 等 ， 但 排 序 后 A、B的 先 后 次 序 保 持 不 变 ， 则 称 这 种 排 序 算 法 是 稳 定 的 。 便 于 查 找 ！ 4. 什 么 叫 内 部 排 序 ？ 什 么 叫 外 部 排 序 ？ 若 待 排 序 记 录 都 在 内 存 中 ， 称 为 内 部 排 序 ；若 待 排 序 记 录 一 部 分 在 内 存 ， 一 部 分 在 外 存 ， 则称 为 外 部 排 序 。注 ： 外 部 排 序 时 ， 要 将 数 据 分 批 调 入 内 存 来 排 序 ， 中 间结 果 还 要 及 时 放 入 外 存 ， 显 然 外 部 排 序 要 复 杂 得 多 。 5.待 排 序 记 录 在 内 存 中 怎 样 存 储 和 处 理 ？ 顺 序 排 序 排 序 时 直 接 移 动 记 录 ； 链 表 排 序 排 序 时 只 移 动 指 针 ； 地 址 排 序 排 序 时 先 移 动 地 址 ， 最 后 再 移 动 记 录 。注 ： 地 址 排 序 中 可 以 增 设 一 维 数 组 来 专 门 存 放 记 录 的 地 址 。 注 ： 大 多 数 排 序 算 法 都 是 针 对 顺 序 表 结 构 的 (便 于 直 接 移 动 元 素 )6. 顺 序 存 储 （ 顺 序 表 ） 的 抽 象 数 据 类 型 如 何 表 示 ？Typedef struct /定 义 每 个 记 录 （ 数 据 元 素 ） 的 结 构 KeyType key ; /关 键 字 InfoType otherinfo; /其 它 数 据 项RecordType ;Typedef struct /定 义 顺 序 表 的 结 构 RecordType r MAXSIZE +1 ; /存 储 顺 序 表 的 向 量 /r0一 般 作 哨 兵 或 缓 冲 区 int length ; /顺 序 表 的 长 度SqList ;# define MAXSIZE 20 /设 记 录 不 超 过 20个typedef int KeyType ; /设 关 键 字 为 整 型 量 （ int型 ） 7. 内 部 排 序 的 算 法 有 哪 些 ？按 排 序 的 规 则 不 同 ， 可 分 为 5类 ： 插 入 排 序 交 换 排 序 （ 重 点 是 快 速 排 序 ） 选 择 排 序 归 并 排 序 基 数 排 序 d 关 键 字 的 位 数 (长 度 )按 排 序 算 法 的 时 间 复 杂 度 不 同 ， 可 分 为 3类 ：简 单 的 排 序 算 法 ： 时 间 效 率 低 ， O(n2)先 进 的 排 序 算 法 : 时 间 效 率 高 ， O( nlog2n )基 数 排 序 算 算 法 ： 时 间 效 率 高 ， O( d n) 9.2 插 入 排 序插 入 排 序 有 多 种 具 体 实 现 算 法 ： 1) 直 接 插 入 排 序 2) 折 半 插 入 排 序 3) 表 插 入 排 序 4) 希 尔 排 序 新 元 素 插 入 到 哪 里 ？例 1： 关 键 字 序 列 T=（ 13， 6， 3， 31， 9， 27， 5， 11） ， 请 写 出 直 接 插 入 排 序 的 中 间 过 程 序 列 。【 13】 , 6, 3, 31, 9, 27, 5, 11【 6, 13】 , 3, 31, 9, 27, 5, 11【 3, 6, 13】 , 31, 9, 27, 5, 11【 3, 6, 13， 31】 , 9, 27, 5, 11【 3, 6, 9, 13， 31】 , 27, 5, 11【 3, 6, 9, 13， 27, 31】 , 5, 11【 3, 5, 6, 9, 13， 27, 31】 , 11【 3, 5, 6, 9, 11， 13， 27, 31】 在 已 形 成 的 有 序 表 中 线 性 查 找 ， 并 在适 当 位 置 插 入 ， 把 原 来 位 置 上 的 元 素 向 后 顺 移 。 直 接 插 入 排 序 算 法Void InsertSort(SqList i=L.length;+i) L.r0=L.ri; /设 定 监 视 哨 j=i-1; if (LT(L.ri.key,L.ri-1.key) for (j=i-1;LT(L.r0.key,L.r j .key);- -j) L.rj+1=L.rj; /记 录 后 移 L.rj+1=L.r0; /插 入 记 录 例 2： 关 键 字 序 列 T= （ 21， 25， 49， 25*， 16， 08） ，请 写 出 直 接 插 入 排 序 的 具 体 实 现 过 程 。 *表 示 后 一 个 250 1 2 3 4 5 625 49 25* 16 08解 ： 假 设 该 序 列 已 存 入 一 维 数 组 V7中 ， 将 V0作 为 缓 冲 或暂 存 单 元 （ Temp） 。 则 程 序 执 行 过 程 为 ：初 态 ：时 间 效 率 ： 因 为 在 最 坏 情 况 下 ， 所 有 元 素 的 比 较次 数 总 和 为 （ 0 1 n-1) O(n 2)。 其 他 情 况下 还 要 加 上 移 动 元 素 的 次 数 。 空 间 效 率 ： 因 为 仅 占 用 1个 缓 冲 单 元算 法 的 稳 定 性 ： 因 为 25*排 序 后 仍 然 在 25的 后 面 。 1111 22142 221nini nnniRMN nnniKCN /)()( ,/)( 22 优 点 ： 比 较 的 次 数 大 大 减 少 ， 全 部 元 素 比 较 次 数 仅 为 O(nlog2n)。时 间 效 率 ： 虽 然 比 较 次 数 大 大 减 少 ， 可 惜 移 动 次 数 并 未 减 少 ，所 以 排 序 效 率 仍 为 O(n2) 。空 间 效 率 ： O（ 1）稳 定 性 ： 稳 定新 元 素 插 入 到 哪 里 ？讨 论 ： 若 记 录 是 链 表 结 构 ， 用 直 接 插 入 排 序 行 否 ？ 折 半 插 入 排序 呢 ？答 ： 直 接 插 入 不 仅 可 行 ， 而 且 还 无 需 移 动 元 素 ， 时 间 效 率 更 高 ！ 在 已 形 成 的 有 序 表 中 折 半 查 找 ， 并 在 适当 位 置 插 入 ， 把 原 来 位 置 上 的 元 素 向 后 顺 移 。 回 忆 ： 链 表 排 序 排 序 时 只 移 动 指 针 ； 地 址 排 序 排 序 时 先 移 动 地 址 ， 最 后 再 移 动 记 录 。 1例 ： 关 键 字 序 列 T=(21， 25， 49， 25*， 16， 08） ， 请 写 出 表 插 入 排 序 的 具 体 实 现 过 程 。解 ： 假 设 该 序 列 （ 结 构 类 型 )已 存 入 一 维 数 组 V7中 ， 将 V0作 为 表 头 结 点 。 则 算 法 执 行 过 程 为 ：i 关 键 字 Vi.key 指 针 Vi.link0 MaxNum1 212 253 494 25*5 166 08 指 向 第 1个 元 素指 向 头 结 点03002 *表 示 后 一 个 25 int LinkInsertSort ( staticlinklis list.v0. Link = 1; list.v1.Link = 0; /形 成 循 环 链 表for ( int i = 2; i = list.length; i+ ) int current = list.v0. Link; /current=当 前 记 录 指 针 int pre = 0; /pre=当 前 记 录 current的 前 驱 指 针 while ( list.vcurrent. Key link)list.vi. Link = current; /新 记 录 vi找 到 合 适 序 位 开 始 插 入 list.vpre. Link = i; /在 pre与 current之 间 链 入 表 插 入 排 序 算 法 分 析 ： 无 需 移 动 记 录 ， 只 需 修 改 2n次 指 针 值 。 但 由 于 比 较次 数 没 有 减 少 ， 故 时 间 效 率 仍 为 O(n2) 。 空 间 效 率 肯 定 低 ， 因 为 增 开 了 指 针 分 量 （ 但 在 运 算过 程 中 没 有 用 到 更 多 的 辅 助 单 元 ） 。 稳 定 性 ： 25和 25*排 序 前 后 次 序 未 变 ， 稳 定 。讨 论 ： 此 算 法 得 到 的 只 是 一 个 有 序 链 表 ， 查 找 记 录 时 只能 满 足 顺 序 查 找 方 式 。改 进 ： 可 以 根 据 表 中 指 针 线 索 ， 很 快 对 所 有 记 录 重 排 ，形 成 真 正 的 有 序 表 （ 顺 序 存 储 方 式 ） ， 从 而 能 满 足折 半 查 找 方 式 。 具 体 实 现 见 教 材 P269。 ） 38例 ： 关 键 字 序 列 T=(49， 38， 65， 97, 76, 13, 27, 49*， 55, 04） ， 请 写 出 希 尔 排 序 的 具 体 实 现 过 程 。0 1 2 3 4 5 6 7 8 9 1049 38 65 97 76 13 27 49* 55 04初 态 ：第 1趟 (dk=5)第 2趟 (dk=3)第 3趟 (dk=1) 49 1313 4938 2765 49*97 5576 0427 38 65 49* 975513 55 7604 5527 042704 4949* 7638 65 975513 2704 4949* 38 76 65 9713 27 04 49* 76 97 算 法 分 析 ： 开 始 时 dk 的 值 较 大 ， 子 序 列 中 的 对 象 较 少 ， 排 序 速 度较 快 ； 随 着 排 序 进 展 ， dk 值 逐 渐 变 小 ， 子 序 列 中 对 象 个 数逐 渐 变 多 ， 由 于 前 面 工 作 的 基 础 ， 大 多 数 对 象 已 基 本 有 序 ，所 以 排 序 速 度 仍 然 很 快 。 void ShellSort(SqList j=j-dk) rj+dk=rj； rj+dk=r0； 参 见 教 材 P272/对 顺 序 表 L进 行 一 趟 增 量 为 dk的 Shell排 序 ， dk为 步 长 因 子/开 始 将 ri 插 入 有 序 增 量 子 表/暂 存 在 r0/关 键 字 较 大 的 记 录 在 子 表 中 后 移/在 本 趟 结 束 时 将 ri插 入 到 正 确 位 置 课 堂 练 习 ：1. 欲 将 序 列 （ Q, H, C, Y, P, A, M, S, R, D, F, X） 中 的 关 键 码 按字 母 升 序 重 排 ， 则 初 始 步 长 为 4的 希 尔 排 序 一 趟 的 结 果 是 ？答 ： 原 始 序 列 ： Q, H, C, Y, P, A, M, S, R, D, F, X shell一 趟 后 ：2. 以 关 键 字 序 列 （ 256， 301， 751， 129， 937， 863， 742， 694，076， 438） 为 例 ， 分 别 写 出 执 行 以 下 算 法 的 各 趟 排 序 结 束 时 ， 关键 字 序 列 的 状 态 ， 并 说 明 这 些 排 序 方 法 中 ， 哪 些 易 于 在 链 表 （ 包括 各 种 单 、 双 、 循 环 链 表 ） 上 实 现 ？ 直 接 插 入 排 序 希 尔 排 序 （ 取 dk=5,3,1）P, Q, R,A, D, H,C, F, M,S, X , Y答 ： 显 然 ， 直 接 插 入 排 序 方 法 易 于 在 链 表 上 实 现 ； 但 希 尔 排序 方 法 因 为 是 按 增 量 选 择 记 录 ， 不 易 于 在 链 表 上 实 现 。 两 种 排 序 方 法 的 中 间 状 态 分 别 描 述 如 后 ： 原 始 序 列 ： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438256， 301， 751， 129， 937， 863， 742， 694， 076， 438256， 301， 751， 129， 937， 863， 742， 694， 076， 438129， 256， 301， 751， 937， 863， 742， 694， 076， 438129， 256， 301， 751， 937， 863， 742， 694， 076， 438129， 256， 301， 751， 863， 937， 742， 694， 076， 438129， 256， 301， 742， 751， 863， 937， 694， 076， 438129， 256， 301， 694， 742， 751， 863， 937， 076， 438076， 129， 256， 301， 694， 742， 751， 863， 937， 438076， 129， 256， 301， 438， 694， 742， 751， 863， 937第 1趟第 2趟第 3趟第 4趟第 5趟第 6趟第 7趟第 8趟 第 9趟 原 始 序 列 ： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438256， 301， 751， 129， 937， 863， 742， 694， 076， 438， ， ， ， ， ， ， ， ， ， 694， ， ， ， ， 751， ， ， ， 076， ， ， ， ， 129， ， ， ， 4 8， ， ， ， ， 9 7第 1趟dk=5第 2趟dk=3第 3趟dk=1 256， 301， 694， 076， 438， 863， 742， 751， 129， 937， ， ， ， ， ， ， ， ，07 ， ， ， 25 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 129， ， ， 694， ， ， 863，076， 301， 129， 256， 438， 694， 742， 751， 863， 937， ， ， ， ， ， ， ， ， 129， 256， 301， ， ， ， ， ， 9.3 交 换 排 序交 换 排 序 的 主 要 算 法 有 ： 1) 冒 泡 排 序 2) 快 速 排 序 1) 基 本 思 路 ： 每 趟 不 断 将 记 录 两 两 比 较 ， 并 按 “ 前 小 后 大 ”（ 或 “ 前 大 后 小 ” ） 规 则 交 换 。优 点 ： 每 趟 结 束 时 ， 不 仅 能 挤 出 一 个 最 大 值 到 最 后 面 位 置 ，还 能 同 时 部 分 理 顺 其 他 元 素 ； 一 旦 下 趟 没 有 交 换 发生 ， 还 可 以 提 前 结 束 排 序 。前 提 ： 顺 序 存 储 结 构 例 ： 关 键 字 序 列 T=(21， 25， 49， 25*， 16， 08） ， 请 写 出冒 泡 排 序 的 具 体 实 现 过 程 。21， 25， 49， 25*， 16， 0821， 25， 25*， 16， 08 ， 4921， 25， 16， 08 ， 25*， 4921， 16， 08 ， 25， 25*， 4916， 08 ， 21， 25， 25*， 49 08， 16， 21， 25， 25*， 49初 态 ：第 1趟第 2趟第 3趟第 4趟第 5趟 冒 泡 排 序 的 算 法 分 析详 细 分 析 ：最 好 情 况 ： 初 始 排 列 已 经 有 序 ， 只 执 行 一 趟 起 泡 ， 做 n-1 次 关 键 码 比 较 ， 不 移 动 对 象 。最 坏 情 形 ： 初 始 排 列 逆 序 ， 算 法 要 执 行 n-1趟 起 泡 ， 第 i趟(1 i n) 做 了 n- i 次 关 键 码 比 较 ， 执 行 了 n-i 次 对 象 交 换 。此 时 的 比 较 总 次 数 KCN和 记 录 移 动 次 数 RMN为 ： 1111 1233 121nini nninRMN nninKCN )()( )()( ( )， 设 以 首 元 素 为 枢 轴 中 心例 1： 关 键 字 序 列 T=(21， 25， 49， 25*， 16，08） ， 请 写 出 快 速 排 序 的 算 法 步 骤 。21， 25， 49， 25*， 16， 08初 态 ：第 1趟 ：第 2趟 ：第 3趟 ： 08， 16， 21， 25， 25*， (49)2116， 08 ， ( )25， 25*， 49(08)， 16， 21， 25， (25*， 49) 编 程 时 ： 每 一 趟 的 子 表 的 形 成 是 采 用 从 两 头 向 中 间 交 替 式 逼 近 法 ； 由 于 每 趟 中 对 各 子 表 的 操 作 都 相 似 ， 主 程 序 可 采 用 递 归 算 法 。见 教 材 P275int (SqList /以 子 表 的 首 记 录 作 为 支 点 记 录 ， 放 入 r0单 元（ 续 下 页 ）一 趟 快 速 排 序 算 法 （ 针 对 一 个 子 表 的 操 作 ） pivotkey=rlow.key; /取 支 点 的 关 键 码 存 入 pivotkey变 量while(low high) /从 表 的 两 端 交 替 地 向 中 间 扫 描while(low=pivotkey ) rlow=rhigh; /将 比 支 点 小 的 记 录 交 换 到 低 端 ；while(lowhigh /将 比 支 点 大 的 记 录 交 换 到 高 端 ；rlow=r0; /支 点 记 录 到 位 ；return low; /返 回 支 点 记 录 所 在 位 置 。/ 例 2： 关 键 字 序 列 T=(21， 25， 49， 25*， 16， 08） ， 请写 出 快 速 排 序 算 法 的 一 趟 实 现 过 程 。ri 0 1 2 3 4 5 6初 态 21 25 49 25* 16 08第 1趟 highlow21 0825 1649 25*21pivotkey=2108 2516 49( 08 ， 16 ） 21 （ 25* ， 49， 25 ） j从 高 端 扫 描寻 找 小 于pivot的 元 素i从 低 端 扫 描寻 找 大 于pivot的 元 素 i=low; j=high;r0=rlow; pivot=rlow.key;i ji =pivot-j;ri = rj;i j rj = ri; ri = r0;return ok; void QSort ( SqList &L, int low, int high ) if ( low 1/对 顺 序 表 L中 的 子 序 列 r lowhigh 作 快 速 排 序/一 趟 快 排 ， 将 r 一 分 为 二/在 左 子 区 间 进 行 递 归 快 排 ， 直 到 长 度 为 1/在 右 子 区 间 进 行 递 归 快 排 ， 直 到 长 度 为 1/QSort 新 的 low 1, L.length 例 3： 以 关 键 字 序 列 （ 256， 301， 751， 129， 937， 863，742， 694， 076， 438） 为 例 ， 写 出 执 行 快 速 算 法 的 各趟 排 序 结 束 时 ， 关 键 字 序 列 的 状 态 。原 始 序 列 ： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438第 1趟第 2趟第 3趟第 4趟 256， 301， 751， 129， 937， 863， 742， 694， 076， 438， 129， ， ， 937， 863， 742， 694， 301， 438要 求 模 拟 算 法 实 现 步 骤07 301129 751， ， ， 438， 301， 694， ， ， 863， 9 7， ， ， ， 301， 694， 742， ， ， 937， ， ， 301， ， ， ， ， ， ， ， ， ， ， 742， ， ， 快 速 排 序 是 递 归 的 ， 需 要 有 一 个 栈 存 放 每 层 递 归 调 用 时 的 指针 和 参 数 （ 新 的 low和 high） 。可 以 证 明 ， 函 数 quicksort的 平 均 计 算 时 间 也 是 O(nlog2n)。 实验 结 果 表 明 ： 就 平 均 计 算 时 间 而 言 ， 快 速 排 序 是 我 们 所 讨 论的 所 有 内 排 序 方 法 中 最 好 的 一 个 。最 大 递 归 调 用 层 次 数 与 递 归 树 的 深 度 一 致 ， 理 想 情 况 为 log2(n+1) 。 因 此 ， 要 求 存 储 开 销 为 o(log2n)。如 果 每 次 划 分 对 一 个 对 象 定 位 后 ， 该 对 象 的 左 侧 子 序 列 与 右侧 子 序 列 的 长 度 相 同 ， 则 下 一 步 将 是 对 两 个 长 度 减 半 的 子 序列 进 行 排 序 ， 这 是 最 理 想 的 情 况 。 此 时 ， 快 速 排 序 的 趟 数 最少 。 在 最 坏 的 情 况 ， 即 待 排 序 对 象 序 列 已 经 按 其 关 键 码 从 小到 大 排 好 序 的 情 况 下 ， 其 递 归 树 成 为 单 支 树 ， 每 次 划 分 只得 到 一 个 比 上 一 次 少 一 个 对 象 的 子 序 列 。 这 样 ， 必 须 经 过 n-1 趟 才 能 把 所 有 对 象 定 位 ， 而 且 第 i 趟 需 要 经 过 n-i 次 关 键 码 比 较 才 能 找 到 第 i 个 对 象 的 安 放 位 置 ， 总 的 关 键码 比 较 次 数 将 达 到 n2/2 快 速 排 序 是 一 个 不 稳 定 的 排 序 方 法 设 每 个 子 表 的 支 点 都 在 中 间 （ 比 较 均 衡 ） ， 则 ：第 1趟 比 较 ， 可 以 确 定 1个 元 素 的 位 置 ；第 2趟 比 较 （ 2个 子 表 ） ， 可 以 再 确 定 2个 元 素 的 位 置 ；第 3趟 比 较 （ 4个 子 表 ） ， 可 以 再 确 定 4个 元 素 的 位 置 ；第 4趟 比 较 （ 8个 子 表 ） ， 可 以 再 确 定 8个 元 素 的 位 置 ； 只 需 log2n 1趟 便 可 排 好 序 。而 且 ， 每 趟 需 要 比 较 和 移 动 的 元 素 也 呈 指 数 下 降 ， 加 上 编 程时 使 用 了 交 替 逼 近 技 巧 ， 更 进 一 步 减 少 了 移 动 次 数 ， 所 以 速 度特 别 快 。教 材 P276有 证 明 ： 快 速 排 序 的 平 均 排 序 效 率 为 O(nlog 2n)；但 最 坏 情 况 (例 如 已 经 有 序 )下 仍 为 O(n2),改 进 措 施 见 P277。