目录
排序问题的基本概念
- 排序(sorting)，也被称为分类、整序等,指按规定的顺序排列一个给定对象集合中的诸元素
- 记录： R 1 , R 2 , . . . , R n R_1,R_2,...,R_n R1,R2,...,Rn
- 文件：K待排序数据对象的有限集合
- 存储：数组和链表
- 关键词：K1,K2,…,Kn，用来排序的属性域
- 通常数据对象由多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键词域。每个文件用哪个属性域作为关键词，要视具体的应用需要而定。即使是同一个文件表，在解决不同问题的场合也可能取不同的域做关键词
排序
- 排序 ：记录按关键词域递增或递减的顺序排列
- 排序的目标就是寻找一个置换
ρ = ( 1 2 ⋯ n ρ ( 1 ) ρ ( 2 ) ⋯ ρ ( n ) ) \rho = \begin{pmatrix} 1 & 2 & \cdots & n \\ \rho(1) & \rho(2) & \cdots & \rho(n) \end{pmatrix} ρ=(1ρ(1)2ρ(2)⋯⋯nρ(n)) - 使得诸关键词按照非递减的次序排列，即有
K ρ ( 1 ) ≤ K ρ ( 2 ) ≤ ⋯ ≤ K ρ ( n ) K_{\rho(1)} \leq K_{\rho(2)} \leq \cdots \leq K_{\rho(n)} Kρ(1)≤Kρ(2)≤⋯≤Kρ(n) - 如果进一步要求具有相同关键词的记录保持它们原来的相对次序，即要求：当 K ρ ( i ) = K ρ ( j ) K_{\rho(i)} = K_{\rho(j)} Kρ(i)=Kρ(j) 且 i < j i < j i<j 时，总有 ρ ( i ) < ρ ( j ) \rho(i) < \rho(j) ρ(i)<ρ(j)，这里 1 ≤ i , j ≤ n 1 \leq i, j \leq n 1≤i,j≤n，则称该排序过程具有稳定性
- 排序的目标就是寻找一个置换
- 排序算法的稳定性：如果在对象序列中有两个对象 r [ i ] r[i] r[i] 和 r [ j ] r[j] r[j]，它们的关键词 k [ i ] = k [ j ] k[i] = k[j] k[i]=k[j]，且在排序之前，对象 r [ i ] r[i] r[i] 排在 r [ j ] r[j] r[j] 前面。如果在排序之后，对象 r [ i ] r[i] r[i] 仍在对象 r [ j ] r[j] r[j] 的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的
排序算法的评价
- 排序的时间开销：排序的时间开销是衡量算法好坏的重要的标志
- 排序的时间开销可用算法执行中关键词的比较次数与数据的移动次数来衡量
- 给出各算法运行时间代价的大略估算，一般都按进行估算
- 对于那些受对象关键词序列初始排列及对象个数影响较大的， 需要按最坏情况和最好情况分别进行估算
- 算法执行时所需的附加存储空间：评价算法好坏的另一标准
排序问题分类
- 从元素的存储设备角度：内排序和外排序
- 内排序： 所有待排序的记录都在内存中
- 外排序：输入文件中的记录所占存储空间大到计算机内存不能容纳，排序过程必需借助外存完成
- 关键词的操作角度：基于关键词比较的排序算法和分布排序算法
- 基于关键词比较的排序算法
- 插入排序（直接插入排序及 Shell 排序）
- 交换排序（冒泡排序及快速排序）
- 选择排序（直接选择排序和堆排序）
- 合并排序
- 分布排序算法不以关键词比较为基础，有较低的时间代价（即 O ( n ) O(n) O(n)），但是需要对数据集有一定先验知识，比如数据分布于哪个区间内等
- 基于关键词比较的排序算法
- 时间代价角度
- 平方阶排序算法：一般都比较简单，特点是容易实现，但时间复杂度相对较高，最坏情况下时间复杂度一般为 O ( n 2 ) O(n^2) O(n2)
- 线性对数阶算法： 以分治策略算法为主，最坏情况下时间复杂度一般为 O ( n log 2 n ) O(n \log_2 n) O(nlog2n)
插入排序
直接插入排序的思想：将一个记录插入到已经排序号的有序列表中，从而得到一个新的、记录数增加1的有序表
例：
原有序表:(9 15 23 28 37) 20
找插入位置: (9 15 ↑ 23 28 37) 20
新有序表: (9 15 20 23 28 37)
直接插入排序算法
InsertSort(R,n)
{
for j=2 to n
{
i = j-1 ;
k = kj;
R = Rj;
while i>0 and k <ki
{
R(i+1) = Ri;
i = i-1;
R(i+1) = R;
}
}
}
改进后的插入算法
引入虚拟记录K0 = -inf
InsertSort(R,n)
{
for j=1 to n
{
i = j-1 ;
k = kj;
R = Rj;
while k <ki
{
R(i+1) = Ri;
i = i-1;
R(i+1) = R;
}
}
}
二分插入排序算法
-
将顺序查找改为二分查找，构造二分插入排序算法
- 即在插入第 i i i 个元素时，不像直接插入排序那样顺序寻找插入的位置，而是采用对半（或二分）的方法插入
-
对半插入排序基本思想
- 设在顺序表中有一个记录序列 R [ 1 ] , R [ 2 ] , … , R [ n ] R[1], \; R[2], \; \dots, \; R[n] R[1],R[2],…,R[n]。其中， R [ 1 ] , R [ 2 ] , … , R [ i − 1 ] R[1], \; R[2], \; \dots, \; R[i-1] R[1],R[2],…,R[i−1] 是已排好序的记录集合。在插入 R [ i ] R[i] R[i] 时，利用对半搜索法寻找 R [ i ] R[i] R[i] 的插入位置
-
对半插入排序就平均性能来说比直接插入排序要快
- 原因：比较次数减少
-
需要的关键词比较次数与待排序记录序列的初始排列无关，仅依赖于记录个数
- 在插入第 i i i 个记录时，需要经过 ⌈ log 2 i ⌉ + 1 \lceil \log_2 i \rceil + 1 ⌈log2i⌉+1 次关键词比较，才能确定它应插入的位置
- 当 n n n 较大时，总关键词比较次数比直接插入排序的最坏情况要好得多，但比其最好的情况要差
- 在记录的初始排列已接近关键词排好序或接近有序时，直接插入排序比对半插入排序执行的关键词比较次数要少
-
对半插入排序的记录移动次数与直接插入排序相同，依赖于对象的初始排列
-
顺序存储 vs 链式存储
- 如果文件 ⟨ R 1 , R 2 , … , R n ⟩ \langle R_1, \; R_2, \; \dots, \; R_n \rangle ⟨R1,R2,…,Rn⟩ 采用顺序存储（比如数组），则对半插入排序算法可以减少关键词的比较次数，但是记录的移动次数仍不能减少
- 如果文件 ⟨ R 1 , R 2 , … , R n ⟩ \langle R_1, \; R_2, \; \dots, \; R_n \rangle ⟨R1,R2,…,Rn⟩ 采用链接存储，虽然确定了插入位置后，可以不必移动记录，但对于链表而言，不能使用对半的方法寻找插入位置
-
对半插入排序是一个稳定的排序方法
希尔排序
- 希尔排序（渐减增量排序法）思想：
- 1959 年 Donald L. Shell 提出 Shell 排序法，是对直接插入算法的一种改进
- 把记录按下标的一定增量分组，对每组使用直接插入排序法，随着增量逐渐减少，所分成的组包含的关键词越来越多，到增量值减至 1 时，整个文件恰好被分成一个组，算法便告终止
- 希尔排序增量的取法：例如 n = 10
d 1 = ⌊ n / 2 ⌋ = ⌊ 10 / 2 ⌋ = 5 d 2 = ⌊ d 1 / 2 ⌋ = ⌊ 5 / 2 ⌋ = 2 d 3 = ⌊ d 1 / 2 ⌋ = ⌊ 2 / 2 ⌋ = 1 d_1 = \lfloor n / 2 \rfloor = \lfloor 10 / 2 \rfloor = 5 \\ d_2 = \lfloor d_1 / 2 \rfloor = \lfloor 5 / 2 \rfloor = 2 \\ d_3 = \lfloor d_1 / 2 \rfloor = \lfloor 2 / 2 \rfloor = 1 d1=⌊n/2⌋=⌊10/2⌋=5d2=⌊d1/2⌋=⌊5/2⌋=2d3=⌊d1/2⌋=⌊2/2⌋=1
- 渐减增量排序的原理
- 开始时增量值较大，子序列中的记录较少，排序速度较快；随着排序进展，增量值逐渐变小，子序列中记录个数逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快
伪代码
ShekkSort(R,n)
{
// 渐减增量序列为 n/2, n/4, n/8,..., 1的希尔排序算法
d = n/2 ;
while d>0
{
for j = d to n
{
i = j - d;
K = Ki;
R = Rj;
while i > 0 and Ki > k
{
Ri+d = Ri;
i = i-d;
Ri+d = R;
d = d/2;
}
}
}
}
-
增量的取法
- 渐减增量可选如下的任意正整数序列：
- n > h t > h t − 1 > ⋯ > h 2 > h 1 = 1 n > h_t > h_{t-1} > \dots > h_2 > h_1 = 1 n>ht>ht−1>⋯>h2>h1=1
- 最初 Shell 提出 d 1 = ⌊ n / 2 ⌋ , d 2 = ⌊ d 1 / 2 ⌋ , … d_1 = \lfloor n / 2 \rfloor, \; d_2 = \lfloor d_1 / 2 \rfloor, \; \dots d1=⌊n/2⌋,d2=⌊d1/2⌋,…，直到 d t = 1 d_t = 1 dt=1
- 后来 Knuth 提出取 d j + 1 = ⌊ d j / 3 ⌋ + 1 d_{j+1} = \lfloor d_j / 3 \rfloor + 1 dj+1=⌊dj/3⌋+1
- 取奇数
- 各增量互质
-
希尔排序性能的分析： Shell 算法的性能与所选取的分组长度序列有很大关系
- 只对特定的待排序记录序列，可以准确地估算关键词的比较次数和对象移动次数
- 想要弄清关键词比较次数和记录移动次数与增量选择之间的依赖关系，并给出完整的数学分析，至今仍然是数学难题
-
希尔排序时不稳定的排序算法
交换排序
冒泡排序
冒泡排序思想
自下而上（或从左到右）比较相邻记录的关键词，交换存在逆序的记录（若 K i > K j + 1 K_i > K_{j+1} Ki>Kj+1，则互换 R j R_j Rj 和 R j + 1 R_{j+1} Rj+1）；使关键词较大的记录如气泡一般逐渐往上“漂移”直至“水面”
伪代码
Bsort
{
for i = n to 2
{
for j = 1 to i -1
{
if kj > k(j+1) Rj,R(j+1) = R(j+1),Rj;
}
}
}
- 经过一趟冒泡，可以把具有最大关键词的记录移至最后（第 n n n 个位置）
- 第 i i i 趟冒泡，将第 i i i 大记录放在第 n − i + 1 n-i+1 n−i+1 个位置上
- 做 n − 1 n-1 n−1 趟冒泡，就可以对所有记录排序
- 发生一次记录交换，逆序对个数减少一个
算法改进
- 在扫描过程中，可能最后几趟已无任何交换发生，算法应能做到，一旦发现某趟扫描中无任何交换时就会终止
- 在每一趟比较中，当比较结束后，如果发现从某个位置开始，不再进行记录交换，即说明从 R t + 1 , … , R n R_{t+1}, \dots, R_n Rt+1,…,Rn 已经排序，从而下一趟比较只要进行到位置 t t t 即可。这样可以减少算法的关键词比较次数
- 据此可以给出一种改进的冒泡排序算法
伪代码
Bubble(R,n)
{
BOUND = n;
while BOUND != 0
{
t = 0;
for j = 1 to BOUND-1
{
if Kj > K(j+1)
{
Rj,R(j+1) = R(j+1),Rj;
t = j;
BOUND = t;
}
}
}
}
- 记录的初始排列是按关键词从小到大排好序时，此算法只执行一趟冒泡，做 n − 1 n-1 n−1 次关键词比较，不发生记录交换；这是最好的情形
- 最坏的情形是算法执行了 n − 1 n-1 n−1 趟冒泡，第 i i i 趟（ 1 ≤ i < n 1 \leq i < n 1≤i<n）做了 n − i n-i n−i 次关键词比较，执行了 n − i n-i n−i 次记录交换。这样在最坏情形下总的关键词比较次数和记录交换次数均为： ( n − 1 ) n / 2 (n-1)n/2 (n−1)n/2
冒泡排序算法
- 时间复杂度}： O ( n 2 ) O(n^2) O(n2)（包括最坏和平均）
- 稳定性：冒泡排序是\textbf{稳定的}排序方法
- 最好情况：当被排序文件初态为正序时，算法的时间复杂度为 O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)
- 为提高效率，可以采用气泡上浮和下沉交替的方法排序
分划交换排序
-
为了加快排序的速度，1962 年霍尔 (Hoare) 提出了分划交换排序方法，又称为快速排序 (Quick Sort)
-
特点：一趟分划将一个记录放在最终位置上
-
原理：交换反序对，非相邻的（与冒泡排序相比）记录交换使得文件中的反序对数目减少得更多
-
该方法可以看作插入排序的改进，其与插入排序的不同之处在于：Hoare 的快速排序方法把控制分划过程的关键词 K i K_i Ki 直接放在它排序的最终位置上，而不是放在排序的子文件 ( R 1 , R 2 , … , R i − 1 ) (R_1, R_2, \dots, R_{i-1}) (R1,R2,…,Ri−1) 中的某一位置。这样，如果 K i K_i Ki 放的最终位置为 S ( j ) S(j) S(j)，则对 i < S ( j ) i < S(j) i<S(j) 有 K i ≤ K S ( j ) K_i \leq K_{S(j)} Ki≤KS(j)；对 i > S ( j ) i > S(j) i>S(j)，有 K i ≥ K S ( j ) K_i \geq K_{S(j)} Ki≥KS(j)。
算法思想
- 每次将当前分块第一个数当作基准，指针i指向当前分块首，指针j指向当前分块尾部+1
- i指针右移一位，如果i指针当前数小于基准，重复2步骤
- j指针左移一位，如果j指针当前数大于基准，重复3步骤
- 如果i<j，则将i指针所指数Ri与j指针所指数Rj调换，否则，将将基准Rm与Rj调换
- 对基准左边部分重复1，2，3，4
- 对基准右边部分重复1，2，3，4
伪代码
QSort(R, m, n) // m,n表示左边界，右边界，R表示原序列
{
if m< n
{
i = m; j = n+1; K = Km; // K表示基准元素
while( i < j )
{
i = i+1;
while (Ki < k) i ++;
j = j-1;
while (Kj > K) j++;
if ( i < j ) Ri,Rj = Rj,Ri;
}
Rm,Rj = Rj,Rm;
}
QSort(R , m , j-1);
QSort(R, j+1, n);
}
- 算法Qsort是一个递归的算法，其递归树如图所示
- 每一个结点表示一次递归调用，结点的值表示本次调用的分划元素
- 左子树表示左文件（由小于等于分划元素的记录构成）
- 右子树表示右文件（由大于等于分划元素的记录构成）
算法分析
- 从快速排序算法的递归树可知，分划嵌套的层数取决于递归树的高度
- 如每次分划对一个记录定位置，该记录的左侧子序列与右侧子序列的长度基本相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情形
时间复杂度
在 n n n 个记录的序列中，快速排序对一个记录分划定位置所需时间为 O ( n ) O(n) O(n)。若设 T ( n ) T(n) T(n) 是对 n n n 个记录的序列进行排序所需的时间，而且每次对一个记录正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：
T ( n ) = 划分时间 + 排序时间 = f ( n ) + T ( n / 2 ) × 2 , n > 1 / / 划分时间即为关键词找到位置的时间， f ( n ) 表示分划算法的时间 T(n) = 划分时间 + 排序时间 = f(n) + T(n/2) \times 2, \quad n > 1 \\ // 划分时间即为关键词找到位置的时间，f(n) 表示分划算法的时间 T(n)=划分时间+排序时间=f(n)+T(n/2)×2,n>1//划分时间即为关键词找到位置的时间，f(n)表示分划算法的时间
f ( n ) = O ( n ) f(n) = O(n) f(n)=O(n)，所以 f ( n ) ≤ c n f(n) \leq cn f(n)≤cn
// c c c 是一个常数
T ( n ) ≤ c n + 2 T ( n / 2 ) T(n) \leq cn + 2T(n/2) T(n)≤cn+2T(n/2)
T ( n ) ≤ c n + 2 T ( n / 2 ) / / c 是一个常数 ≤ c n + 2 ( c n 2 + 2 T ( n / 4 ) ) = 2 c n + 4 T ( n / 4 ) ≤ 2 c n + 4 ( c n 4 + 2 T ( n / 8 ) ) = 3 c n + 8 T ( n / 8 ) ⋮ ≤ c n log 2 n + n T ( 1 ) = O ( n log 2 n ) \begin{align*} T(n) &\leq cn + 2T(n/2) \quad // \; c \; 是一个常数 \\ &\leq cn + 2 \left( \frac{cn}{2} + 2T(n/4) \right) = 2cn + 4T(n/4) \\ &\leq 2cn + 4 \left( \frac{cn}{4} + 2T(n/8) \right) = 3cn + 8T(n/8) \\ &\vdots \\ &\leq cn \log_2 n + nT(1) = O(n \log_2 n) \end{align*} T(n)≤cn+2T(n/2)//c是一个常数≤cn+2(2cn+2T(n/4))=2cn+4T(n/4)≤2cn+4(4cn+2T(n/8))=3cn+8T(n/8)⋮≤cnlog2n+nT(1)=O(nlog2n)
可以证明，函数Qsort的平均计算时间也是 O ( n log 2 n ) O(n \log_2 n) O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个
- 对随机序列而言时间复杂度为 O ( n log 2 n ) O(n \log_2 n) O(nlog2n)
- 在最坏的情况下时间复杂度为 O ( n 2 ) O(n^2) O(n2)
- 待排序记录序列已经按其关键词从小到大排好序的情况下，其递归树成为单支树，每次分划只得到一个比上一次少一个记录的子序列。此时快速排序的速度退化到简单排序的水平
- 合理地选择基准记录，使得每次分划所得的两个子文件中的记录个数尽可能接近，可以加速排序速度
改进算法
- 改进办法：取每个待排序记录序列的第一个记录、最后一个记录和位置接近正中的 3 个记录，取其关键词大小居中者作为基准记录
伪代码
Part(R,m,n,j)
{
R((m+n)/2),R(m+1) = R(m+1),R((m+n)/2);
if (K(m+1) > Kn) Rm, Rn = Rn, Rm;
if (K(m+1)>Km) R(m+1), Rm = Rm, R(m+1)
i = m;j = n+1; K = Km;
while i < j
{
i = i+1;
while (Ki< K) = i+1;
j = j-1;
while (Kj > Kj) = j-1;
if (i < j) Ri, Rj = Rj, Ri;
}
Rm, Rj = Rj, Rm
}
总结
- 快速排序算法
- 时间复杂度： O ( n 2 ) O(n^2) O(n2) \quad // 最坏
- 时间复杂度： O ( n log 2 n ) O(n \log_2 n) O(nlog2n) \quad // 最好和平均
- 空间复杂度： O ( log 2 n ) O(\log_2 n) O(log2n)
- 稳定性：快速排序是\textbf{不稳定的}排序方法
- 快速排序方法是目前内部排序中最好、最快的排序方法。