第二章 程序设计基础知识

第3节 排序算法

一、内排序和外排序的定义

由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：内排序与外排序。

1. 内排序：待排序记录存放在计算机内存中进行的排序过程。插入排序、快速排序、选择排序、归并排序、基数排序等目前竞赛研究的算法基本上都是内排序方法。
2. 外排序：待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。

二、衡量效率的方法

1. 内排序：比较次数，也就是时间复杂度。
2. 外排序：I/O次数，也就是读写外存的次数。

三、排序稳定性

排序前后相同元素的相对位置不变，则称排序算法是稳定的，否则排序算法是不稳定的。如原序列$r_i=r_j$且$r_i$位于$r_j$之前，排序后$r_i$仍在$r_j$之前，则称该排序是稳定的。 如：数据57, 491, 26, 3, 492, 5进行升序排序。

• 稳定算法排序后为：3, 5, 26, 491, 492, 57。
• 不稳定算法排序后可能为：3, 5, 26, 492, 491, 57。

四、常用排序算法复杂度