1 《数据结构》实验报告 排序 实验题目： 输 入 十 个 数 ， 从 插 入 排 序 ， 快 速 排 序 ， 选 择 排 序 三 类 算 法 中 各 选 一 种 编 程 实现 。 实验所使用的数据结构内容及编程思路： 1.插 入 排 序 ： 直 接 插 入 排 序 的 基 本 操 作 是 ， 将 一 个 记 录 到 已 排 好 序 的 有 序 表中 ， 从 而 得 到 一 个 新 的 ， 记 录 增 一 得 有 序 表 。 一 般 情 况 下 ， 第 i 趟 直 接 插 入 排 序 的 操 作 为 ： 在 含 有 i-1 个 记 录 的 有 序 子 序列 r［ 1..i-1］中 插 入 一 个 记 录 r［ i］后 ，变 成 含 有 i 个 记 录 的 有 序 子 序 列 r［ 1..i］；并 且 ， 和 顺 序 查 找 类 似 ， 为 了 在 查 找 插 入 位 置 的 过 程 中 避 免 数 组 下 标 出 界 ， 在 r［ 0］ 处 设 置 哨 兵 。 在 自 i-1 起 往 前 搜 索 的 过 程 中 ， 可 以 同 时 后 移 记 录 。 整 个 排序 过 程 为 进 行 n-1 趟 插 入 ， 即 ： 先 将 序 列 中 的 第 一 个 记 录 看 成 是 一 个 有 序 的 子 序列 ， 然 后 从 第 2 个 记 录 起 逐 个 进 行 插 入 ， 直 至 整 个 序 列 变 成 按 关 键 字 非 递 减 有 序序 列 为 止 。 2.快 速 排 序 ： 基 本 思 想 是 ， 通 过 一 趟 排 序 将 待 排 记 录 分 割 成 独 立 的 两 部 分 ，其 中 一 部 分 记 录 的 关 键 字 均 比 另 一 部 分 记 录 的 关 键 字 小，则可 分 别对这两 部 分 记录 继续进 行 排 序 ， 以 达到 整 个 序 列 有 序 。 假设 待 排 序 的 序 列 为 {L.r[s]，L.r[s+1],…L.r[t]},首先 任意选 取一 个 记 录(通 常可 选 第 一 个 记 录 L.r[s])作 为 枢轴（或支点）（pivot）， 然 后 按 下 述原则重新 排 列 其 余记 录 ： 将 所有 关 键 字 较它小的 记 录 都安置 在 它的 位 置 之前 ， 将 所有 关键 字 较大的 记 录 都安置 在 它的 位 置 之后 。 由此可 以 该“枢轴”记 录 最后 所罗的 位置i 作 为 界 线...
