常 见 排 序 算 法 总 结 【 转 载 +整 合 】 2009-09-14 15:17 1、 稳 定 排 序 和 非 稳 定 排 序 简 单 地 说 就 是 所 有 相 等 的 数 经 过 某 种 排 序 方 法 后 ，仍 能 保 持 它 们 在 排 序 之 前 的 相对 次 序 ， 我 们 就 说 这 种 排 序 方 法 是 稳 定 的 。 反 之 ， 就 是 非 稳 定 的 。 要 注 意 的 是 ，排 序 算 法 的 稳 定 性 是 针 对 所 有 输 入 实 例 而 言 的 。 即 在 所 有 可 能 的 输 入 实 例 中 ， 只要 有 一 个 实 例 使 得 算 法 不 满 足 稳 定 性 要 求 ， 则 该 排 序 算 法 就 是 不 稳 定 的 。 比 如 ： 一 组 数 排 序 前 是 a1,a2,a3,a4,a5， 其 中 a2=a4， 经 过 某 种 排 序 后 为a1,a2,a4,a3,a5， 则 我 们 说 这 种 排 序 是 稳 定 的 ， 因 为 a2排 序 前 在 a4的 前 面 ， 排序 后 它 还 是 在 a4的 前 面 。 假 如 变 成 a1,a4,a2,a3,a5就 不 是 稳 定 的 了 。 2、 内 排 序 和 外 排 序 在 排 序 过 程 中 ， 所 有 需 要 排 序 的 数 都 在 内 存 ， 并 在 内 存 中 调 整 它 们 的 存 储 顺 序 ，称 为 内 排 序 ； 在 排 序 过 程 中 ， 只 有 部 分 数 被 调 入 内 存 ， 并 借 助 内 存 调 整 数 在 外 存 中 的 存 放 顺 序排 序 方 法 称 为 外 排 序 。 3、 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度 所 谓 算 法 的 时 间 复 杂 度 ， 是 指 执 行 算 法 所 需 要 的 计 算 工 作 量 。 一 个 算 法 的 空 间 复 杂 度 ， 一 般 是 指 执 行 这 个 算 法 所 需 要 的 内 存 空 间 。 ======================================= 一 .插 入 排 序 首 先 新 建一 个 空 列表， 用于保 存 已排 序 的 有 序 数 列（我 们 称 之 为 "有 序 列表"）。 从原数 列中 取出一 个 数 ， 将其 插 入 "有 序 列表"中 ， 使 其 仍 旧保 持 有 序 状态。 重复 2号步骤， 直至原数 列为 空 。 插 入 排 序 的 平...
