个 长 度 为 2 或 1 的 有 序 子 序 列 ； 再 两 两 归 并 ， ......， 如 此 重 复， 直至得到一个长度为 n 的有序序列为止。 3.2 算法比较
表 1 从理论角度上对常用排序算法进行了比较， 分别给 出了不同算法的时间复杂度、 空间复杂度、 稳定性和复杂性 的分析。
表 1 算法比较
(上接第 19 页)
车时间比例大， 说明路面管理有问题。 棒状图可以直观反映
果， 也可以对某个时间范围内的或所有的上行或下行调查结
一条路中每段的速度情况， 直观、 快速地为决策者提供科学
果进行汇总和统计 （累加值、 平均值和标准偏差）， 还可以对
依据。
某段时期多条调查线路的上下行调查数据进行汇总和统计，
快速排序 653 464 0.000 13059 6114 0.000 199954 77002 0.002
选择排序 4950 282 0.000 499500 2975 0.010 49995000 29231 0.760
堆排序 1026 1215 0.000 16620 15520 0.000 235022 188954 0.013
参考文献 [ 1] 王 莉 . 各 种 内 部 排 序 算 法 的 比 较 . 黑 龙 江 科 技 信 息 ，
2009， （29）. [2] 严 蔚 敏 ， 吴 伟 民. 数 据 结 构 [M] . 北 京 ： 清 华 大 学 出 版
社， 2012.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
（4） 从稳定性来比较， 冒泡排序、 插入排序和归并排序 是稳定的， 而选择排序、 快速排序、 堆排序和希尔排序等时 间性能较好的排序方法都是不稳定的。
4 结语
排序算法的性能分析与比较是一个比较复杂的问题， 从 空间复杂度、 时间复杂度、 比较次数、 移动次数、 运行时间 等方面来看， 没有哪一种是绝对最优的。 有的适用于问题规 模 n 较大的情况， 有的适用于 n 较小的情况。 在实际应用中， 应根据经验和实际情况合理选择算法， 甚至可以将多种方法 融合。
2014.21 23
3.3 性能分析 使用课题组设计开发的数据结构内部排序算法分析与比
较系统对各种不同的排序算法进行了定量的性能分析。 考虑 从各种排序算法在处理不同规模数据问题时， 所消耗的时间、 空间复杂度、 比较次数、 移动次数以及稳定性等方面来分析。 3.3.1 实验数据
（1） 待排序数据元素有一个数据项， 且为整型， 由随机 数产生器生成。
3 内部排序算法的比较与分析
3.1 基本思想 （1） 直接插入排序 算法思想： 将一个待排序的记录插入到已排好序的有序
表中的适当位置， 从而得到一个新的、 记录数增 1 的有序表。 （2） 希尔排序 算法思想： 希尔排序是对直接插入排序改进后提出的，
又称 “缩小增量排序”。 先将整个待排记录序列分割成为若干 子序列分别进行直接插入排序， 待整个序列中的记录 “基本 有序” 时， 再对全体记录进行一次直接插入排序。
2 排序算法性能评价的因素
一个问题可用不同的算法解决， 而一个算法性能的优劣 将影响解决问题的效率。 通常， 评价一个算法性能的好坏主 要从时间复杂度和空间复杂度来考虑。 对于排序算法， 主要 采用插入、 交换和选择等方法， 涉及到比较和移动等基本操 作， 因此， 评价排序算法， 考虑从各种算法在处理不同规模 数据问题时， 所消耗的时间、 空间复杂度、 比较次数、 移动 次数以及稳定性等方面来分析。
（3） 冒泡排序 算法思想： 对待排序的记录关键字进行两两比较， 若两 个记录是反序的， 则进行交换， 直到无反序的记录为止。 （4） 快速排序 算法思想： 是对冒泡排序的一种改进。 通过一趟排序将
待排记录分割成独立的两部分， 其中一部分记录的关键字均 比另一部分记录的关键字小， 则可分别对这两部分记录进行 排序， 已达到整个序列有序。
排序方法 平均时间 最坏情况 最好情况 空间复杂度 稳定性 复杂性
插入排序 O (n2) O (n2) O (n)
O (1)
稳定 简单
希尔排序
O (n1.25)
O (1)
不稳定 复杂
冒泡排序 O (n2) O (n2) O (n)
O (1)
稳定 简单
快速排序 O (nlog2n) O (n2) 简单选择排序 O (n2) O (n2)
打印出来， 结果一目了然。 通过饼状图可以非常直观地看出
口按键， 因为该键在整个键盘的左上方， 非常容易找准。 用
偶然停车时间和红灯停车时间在行程时间中的比例。 如红灯
空格键代表红灯停车， 这是因为空格键最长， 容易找准， 偶
停车时间占比例大， 说明信号的绿信比没有调好。 如偶然停
然停车可以不按键自动识别。
24 2014. 21
（2） 考虑到能灵活有效地对每种算法处理大、 中、 小型 规模数据排序的性能比较， 问题规模 n 由用户交互输入。
（3） 考虑实验结果的有效性， 课题组采用多次平行实验 测定结果的平均值作为算法分析的依据。 3.3.2 实验结果
为了更好地研究和比较各种排序算法， 分析每种算法的 时间复杂度与待排序数据规模的关系， 评估不同算法在处理 同 一 数 据 问 题 的 效 率 ， 课 题 组 开 发 设 计 了 基 于 VC++6.0 的 内 部排序算法的比较与分析系统， 在同样的计算机软硬件环境 下 ， 对 给 定 长 度 （100,1000,10000） 的 待 排 序 数 据 进 行 排 序 测 试， 然后统计每种算法的执行时间， 比较次数、 移动次数。
归并排序 516 1344 0.000 8284 19952 0.000 112035 267232 0.008
3.3.3 结果分析 通过以上实验统计结果， 可以得出以下结论： （1） 每种算法的执行时间、 比较次数及移动次数与问题
规模 n 有关。 当数据规模较小时， 各种排序算法的性能差距 不是很显著， 考虑减少移动操作次数， 用简单选择排序较好。 但随着排序数据逐渐增长， 算法性能的优劣就明显了， 其中 快速排序、 堆排序和归并排序性能较优。
O (nlog2n) O (log2n)
O (n2)
O (1)
不稳定 较复杂 不稳定 简单
堆排序
O (nlog2n) O (nlog2n) O (nlog2n) O (1)
不稳定 较复杂
归并排序 O (nlog2n) O (nlog2n) O (nlog2n) O (n)
稳定 较复杂
基金项目：新疆医科大学大学生创新性实验项目 （CX2013027）。 作者简介：李莉 （1978-）， 女， 通讯作者， 副教授。 收稿日期：2014-08-15
N=10000
比较 次数
移动 次数
排序 时间
直插排序 2524 2629 0.000 249275 250274 0.003 25033776 25042517 0.698
希尔排序 792 1079 0.000 14652 21687 0.002 237514 387194 0.005
冒泡排序 4712 7397 0.000 482864 744829 0.009 48447146 75071333 1.229
采 取 了 10 组 不 同规模的随机数进行 排 序 实 验 ， 将 所 统 计 的每种算法的执行时间、 比较次数、 移动次数进行平均， 得到 更有代表性的实验结果， 如表 2 （排序时间单位： 秒） 所示。
表 2 实验结果
方法
N=100
性能
比较 移动 排序 次数 次数 时间
N=1000
比较 移动 排序 次数 次数 时间
本系统在设计时充分考虑到人机工程因素， 例如， 在调
以便为管理部门Байду номын сангаас供决策的依据。 统计结果以报表或统计图
查时， 只使用两个键即可完成全部调查， 并且在键位选择上
（饼图和柱状图） 的形式显示在屏幕上 （预览） 或从打印机上
也 做 了 周 密 的 考 虑 ， 用 标 准 计 算 机 键 盘 的 ESC 键 表 示 通 过 路
内部排序算法的分析与比较
江燕，周军，罗冬梅，尼亚孜买买提，李莉 *
（新疆医科大学医学工程技术学院，乌鲁木齐 830011）
摘 要： 通过分析直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序等常用的内 部排序算法的思想，统计各种算法的时间、空间复杂性、比较次数、移动次数以及稳定性，以期能够掌握这些算法 及其特点，在实际应用中能够结合具体问题设计出正确而高效率的数据排序程序。 关键词： 排序算法；比较；分析
1 引言
排序是计算机科学研究领域的一个基本课题， 是指将无序的 数据元素， 通过一定的方法按关键字顺序排列的过程。 若整个排 序过程不需要访问外存就能完成的排序问题称为内排序， 反之 为外排序。 内排序的方法繁多， 按所用策略不同， 可分为插入 排序、 选择排序、 交换排序、 归并排序和分配排序。 因此， 研 究比较各种排序算法的性能可对于实际应用选择起到理论指导 的作用。 对数据结构中常用的 7 种 （直接插入、 希尔、 冒泡、 快速、 简单选择、 堆和归并） 内排序进行讨论， 介绍了每种排 序算法的基本思想， 从时间复杂度、 空间复杂度、 比较次数、 移 动次数和稳定性对各种算法进行了分析和比较。 以期为读者在实 际应用中提供依据， 结合具体问题设计正确而高效的排序程序。
（5） 简单选择排序 算 法 思 想 ： 每 一 趟 排 序 是 通 过 进 行 n-i 次 关 键 字 的 比 较 ， 从 n-i+1 个待排序记录中选出关键字最小的记录后和第 i 个 记 录进行交换， 直到待排序的数据元素有序为止。 （6） 堆排序 算法思想： 堆排序是一种树形选择排序。 首先需要将待 排序记录按排序关键字建成一个小 （或大） 顶堆， 即子结点 的关键字总是小于 (或者大于) 它的父节点。 然后输出堆顶的 元 素 ， 把 剩 余 n-1 个 元 素 的 序 列 重 新 调 整 成 一 个 堆 ， 重 复 此 过程， 直到待排序的数据元素有序为止。 （7） 归并排序 算法思想： “归并” 是将两个或两个以上的有序表合并 成一个新的有序表。 若待排序记录有 n 个， 则可看成是 n 个 有序的子序列， 每个子序列的长度为 1， 然后两两归并， 得到