能容 纳全 部记 录 ， 排序 过程 中 尚需 对 外存 进 行 在 访 问 的排 序过 程 ．
② 一组 待排 序记 录存 放在 静 态链 表 中 ， 录 记
之间 的次 序关 系 由指 针 指示 ， 则实 现 排序 不 需要
移动记 录 ， 需 移动 指针 即可 ． 仅
③ 待排 序 记 录 本 身存 储 在 一 组 地 址 连续 的 存 储单 元 内 ， 同时另设 一个 指 示各 个 记 录存 储位
杨 有 （９ ５一） 男 ， 庆 粱 平 人 ， 士 ， 教 授 ， 要 从 事 数 字 图像 处 理方 面 的研 究 １６ ， 重 博 副 主 ４５
认 为按升序 排序 ．
记 录 Ｒ ｋ 将 它 与无 序 区 的第 １个 记 录 Ｒ ０ ［ ］， ［］ 交 换 ， 有序 区记 录增 加 １ ， 序 区记 录减少 １ 使 个 无 个； ③第 ｉ 次排 序． 在开始 时 ， 当前 有序 区和无 序 区分别 为 Ｒ［ ， ，］ Ｒ［ ＋１ … ， ０ … ｉ和 ｉ ， ｎ一１ ０≤ ］（
…
，
ｎ一１ ）其存 储 位 置 也 相邻 ． 这 种存 储 方式 在
中 ， 录之 间 的 次序 关 系 由其 存 储 的位 置 决 定 ， 记
排 序 通过移 动 记录来 实 现．
及 的存 储 器 ， 可将 排 序 方 法 分 为两 大类 … ： 类 一 是 内部排 序 ， 的是 待排 序记 录存放 在 计算 机 存 指 储器 中进 行 的排 序 过 程 ； 一类 是 外 部排 序 ， 另 指 的是 待排 序记 录 的数量 很大 ， 以致 于 内存 一次 不
通 过描 述 冒泡 、 选择 、 入 、 并和 快 速 ５种 排 序 算 法 ， 结 了它们 的 时 间复 杂 性பைடு நூலகம்和 空 间复 杂 插 归 总
性 ， 出 ５种排 序 算 法可分 为 平方 阶排序 和 线性 对数 阶排序 两类． 指 通过 实验 验证 了 ５种排序 算
法在 随机 、 正序和 逆序 ３种 情 况下 的性 能 ， 出排序 算 法 的适 用原 则 ： 指 当记 录较 小 时 ， 可采 用插
序 、 择 排序 、 选 归并 排序 和快 速排 序等 ５类 ．
［ 收稿日期 ］０ ０— ４—１ ２１ ０ ５
［ 基金项 目］ 云南省 ２０ ０ ９年社会 发展科技计划项 目（０ ９ Ｃ ２ Ｍ） ２ ０ Ｚ １８ ． ［ 作者简 介］ 淦艳 （９ ８一） 男 ， １８ ， 重庆南岸 区人 ， 主要从事软件理论与技术方面的研究．
Ｊｎ ｕ ．，２ １ ００
Ｖ０． ９ Ｎｏ ３ １２ ．
第２ ９卷
第 ３期
五 种 排序 算 法 的性 能分 析
淦
（ 重庆 师范大学
艳， 杨 有
沙坪坝 ４０４ ） ０ ０ ７
信息科学与工程学院 ， 重庆
［ 摘
要］ 排序 是计 算机 科 学 中基 本 的研 究课题 之 一 ， 目的 是 方便记 录 的查找 、 入 和删 除 ． 其 插
方法 进行 分 类 ， 大 致 可 分 为 插 入 排 序 、 则 冒泡 排
储 位 置． 为便 于后 续讨论 ， 行如 下假设 ： 进 考虑 到易 于理解 、 机访 问 和尽 量添 加 更少 随 的附加信息来实现记录的存储（ 形式② 、 需要 ③ 另外 记 录指 针 和地址 信 息 ， 附加信 息 比较 多 ） 将 ， 待排 序记 录 的一组 记 录以形 式① 进 行存 储 ， 且 而 记 录 的关键 字 为 整 数 ； 有 特 殊 说 明时 ， 序均 没 排
入 或选择 排 序 ； 当记 录基本 有序 时 ， 可选 用插 入或 冒泡排序 ； 当记 录较 大时 ， 则应选择 快速 排序
或 归并排序 ．
［ 关键 词 ］ 排序 算 法 ； 冒泡排序 ； 选择排 序 ； 插入排 序 ； 归并排序 ； 速排 序 快
［ 中图分类号 ］Ｐ ０ ［ Ｔ ３ １ 文献标志码］ ［ Ａ 文章编号］６３— ０２ ２ １ ）３ ０４ — ６ １７ ８ １ （００ ０ — ０ ５ ０
后合 并 ） ， 将其 划分 成几 段合 适 的待排 序记 录 ， 然后 对每 一 小段 采 用 内 部排 序 方 法 ． 句 话 说 ， 换 就是 将外 部排 序转 化为 内部 排序 ， 以为 了进 一 所 步研 究外 部排 序 ， 先对 内部排 序进 行 深 入 的讨 需 论． 如果 在排序 过程 中依 据 不 同原 则对 内部排 序
２１ ０ ０年 ６月
重庆 文理 学 院学 报 （ 自然 科 学 版 ） Ｊｕ ａ ｆ ｈｎ ｑｎ ｎｖｒｔ ｆ ｒ ｎ ｃ ｎ ｅ Ｎ ｔｒｌ ｃｅｃ ｄｔ ｎ ｏｒｌ ｏ ｏｇ ｉｇＵ ｉ ｓ ｙｏ ｔ ａｄＳｉ ｃｓ（ ａｕａ ＳｉｎｅＥ ｉｏ ） ｎ Ｃ ｅｉ Ａ ｓ ｅ ｉ
置 的地址 向量 ， 排 序 过 程 中 不 移 动记 录本 身 ， 在
而移 动地 址 向量 中这 些 记 录 的 “ 址 ” 在 排 序 地 ， 结 束 之后再 按 照 地 址 向量 中的 值 调 整记 录 的存
考虑 到外部 排 序涉及 的 待排 序 记 录数 量 大 ，
可 以采取 分治 的思 想 （ 即先分 解 ， 递 归求 解 ， 再 然
排序 是计算 机 程序设 计 中的一 种 重要 操 作 ， 通常 ， 排序 记 录存储 具有 如下 ３种形 式 ：
它 的功能 是将 任 意 序 列 的数 据 元 素 或 记 录 重 新 按关 键字 顺序 排列 成有 序 的序 列． 序 序 列 为记 有 录 的查找 、 入 和 删 除 提 供 了方 便 ， 以有 效 提 插 可 高搜 索效 率 ． 因此 ， 究 各 类 排 序 方 法 是 计 算 机 研
研究 中 的重要课 题 之一 ． 根据 待排 序 记 录 数 量 及 其 在 排 序 过 程 中涉
① 待 排 序 的一 组 记 录存 放 在 地 址 连续 的一 组存 储单 元 上． 类 似 于线 性 表 的顺 序 存 储 结 它 构 ， 序 列 中相 邻 的 ２个记 录 尺 和 尺 （ 在 … ＝１ ２ ，，