- 8.1 排序的基本概念
- 8.2 插入排序
- 直接插入排序
- 折半插入排序
- 希尔排序（缩小增量排序）
- 8.3 交换排序
- 冒泡排序
- 快速排序
- 8.4 选择排序
- 简单选择排序
- 堆排序
- 8.5 归并排序和基数排序
- 归并排序
- 基数排序
- 8.6 算法小结
排序，就是重新排列表中的元素，使表中元素满足按关键字有序的过程。
算法的稳定性：若待排序表中有两个元素
R
i
R_i
Ri和
R
j
R_j
Rj，其对应的关键字相同即
k
e
y
i
=
k
e
y
j
key_i=key_j
keyi=keyj，且在排序前
R
i
R_i
Ri 在
R
j
R_j
Rj 的前面，若使用某一排序算法后，
R
i
R_i
Ri 仍然在
R
j
R_j
Rj 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
算法是否具有稳定性并不能衡量一个算法的优劣，主要是对算法性质的描述。对于不稳定的排序算法只需举出一组关键字的实例，说明它的不稳定性即可。
在排序过程中，根据数据结构是否完全在内存中，可将排序算法分为两类：
1）内部排序：是指在排序期间元素全部存放在内存中的排序。
2）外部排序：是指在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内、外存之间移动的排序。
一般来说，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。但并非所有内部排序算法都要基于比较操作，事实上，基数排序就不基于比较。
对于任意n个关键字排序，进行基于比较的排序算法，比较次数至少为 ┌ log 2 ( n ! ) ┐ ulcorner log_2(n!) urcorner ┌log2(n!)┐
通常可以将排序算法分为插入排序，交换排序、选择排序、归并排序和基数排序五大类。
8.2 插入排序基本思想：每次将一个待排序的记录按其关键字大小插入前面已排好的子序列，直到全部记录插入完成。插入排序的三个重要排序算法：直接插入排序、折半插入排序和希尔排序。
直接插入排序直接应用上面的插入排序思想。假设待排序表 L [ 1... n ] L[1...n] L[1...n] 在某次排序过程中的某一时刻状态如下：
要将元素
L
(
i
)
L(i)
L(i)插入已有序的子序列
L
[
1...
i
−
1
]
L[1...i-1]
L[1...i−1] ，需要执行以下操作：
1）查找出
L
(
i
)
L(i)
L(i) 在
L
[
1...
i
−
1
]
L[1...i-1]
L[1...i−1] 中的插入位置
k
k
k。
2）将
L
[
k
.
.
.
i
−
1
]
L[k...i-1]
L[k...i−1] 中的所有元素依次后移一个位置。
3）将
L
(
i
)
L(i)
L(i) 复制到
L
(
k
)
L(k)
L(k)
上述的操作，从
L
(
2
)
L
(
n
)
L(2)~L(n)
L(2) L(n) 依次插入前面已排好序的子序列就能得到一个有序的表。
直接插入排序算法有可能在最后一趟开始之前，所有元素都不在最终位置上。
假设初试序列为
49
,
38
,
65
,
97
,
76
,
13
,
27
,
49
49,38,65,97,76,13,27,49
49,38,65,97,76,13,27,49，排序过程如下图所示：
具体代码如下：
void InsertSort(ElemType s[],int n){
//注意A[0]我们不存放元素，充当“哨兵”的作用
int i,j;
for(i=2;i<=n;i++){//依次将s[2]~s[n]插入到前面已经排序的序列
if(s[i]
直接插入排序算法的性能分析
1）空间效率
仅使用了常数了辅助单元，因而空间复杂度为O(1)。
2）时间复杂度
直接插入排序算法的平均时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)
在排序过程中，向有序子表中逐个地插入元素的操作进行了
n
−
1
n-1
n−1 趟，每趟都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。
1）在最好的情况下，表中元素已经有序，此时没插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为
O
(
n
)
O(n)
O(n)，在序列基本有序的情况下，只有直接插入算法的效率最高。
2）在最坏的情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大，为
∑
i
=
2
n
i
sum_{i=2}^n{i}
∑i=2ni，总的移动次数也达到最大，为
∑
i
=
2
n
(
i
+
1
)
sum_{i=2}^n (i+1)
∑i=2n(i+1)
3）平均情况下，去上述最好与最坏的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均为
n
2
4
frac{n^2}{4}
4n2 。
3）稳定性
由于每次插入元素总是从后向前比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序算法。
4）适用性
直接插入排序算法适用于顺序存储和链式存储的线性表。
大部分排序算法都仅适用于顺序存储的线性表。
折半插入排序
折半插入排序主要是针对查找待插入元素应插入的位置做算法上的优化，从上面的学习中我们可以知道，直接插入排序在查找采用的是线性查找，所以根据上一章的内容，我们可以采用折半查找来降低关键字比较的平均次数。
void InsertSort(ElemType s[],int n){
//注意A[0]我们不存放元素，充当“哨兵”的作用
int i,j;
for(i=2;i<=n;i++){//依次将s[2]~s[n]插入到前面已经排序的序列
s[0]=s[i];//复制为哨兵
//折半查找插入位置
int low=1,high=i-1;//设置折半查找的范围
while(low<=high){
int mid=(low+high)/2;
if(s[mid]>s[0]){
high=mid-1;//查找左半子表
}
else{
low=mid+1;//查找右半子半表
}
}
for(j=i-1;j>=high+1;j--){
s[j+1]=s[j];//向后移位置，腾出插入位置
}
s[high+1]=s[0];//复制到插入的位置中
}
}
折半插入排序算法的性能分析
1）时间复杂度：折半插入排序的时间复杂度仍为
O
(
n
2
)
O(n^2)
O(n2)，但对于数据量不是很大的排序表，折半插入排序往往能表现出很好的性能。
折半插入排序仅减少了比较元素的次数，约为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n) ，但元素的移动次数并未改变，约为
O
(
n
2
)
O(n^2)
O(n2)，所以折半插入排序的时间复杂度仍为
O
(
n
2
)
O(n^2)
O(n2)
2）稳定性：折半插入排序是一种稳定的排序方法。
4）适用性：折半插入排序算法仅适用于线性表未顺序存储的情况。
希尔排序（缩小增量排序）
有前面的分析可知，直接插入排序算法在最好的情况下，表中元素已经有序，时间复杂度为
O
(
n
)
O(n)
O(n)。希尔排序就是基于这个特点，对直接插入排序进行改进而成。
基本思想：先将待排序表分割成若干个形如
L
[
i
,
i
+
d
,
i
+
2
d
,
.
.
.
,
i
+
k
d
]
L[i,i+d,i+2d,...,i+kd]
L[i,i+d,i+2d,...,i+kd]的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个元素中的元素已“基本有序”时，再对全体记录进行一次直接插入排序，而由于此时已经具有较好的局部有序性，所有能很快得到最终结果。
希尔排序过程如下：
1）取一个小于
n
n
n 的步长
d
1
d_1
d1，把表中的全部记录分成
d
1
d_1
d1 组，所有距离为
d
1
d_1
d1 的倍数的记录放在同一组，在各组内进行直接插入排序；
2）取第二步长
d
2
<
d
1
d_2
到目前为止，还没任何人能求得一个最好的增量序列，希尔提出的方法是
d
1
=
n
2
，
d
i
+
1
=
└
d
i
2
┘
d_1=frac{n}{2}，d_{i+1}=llcorner frac{d_i}{2} lrcorner
d1=2n，di+1=└2di┘，并且最后一个增量等于1。
假设初试序列为
49
,
38
,
65
,
97
,
76
,
13
,
27
,
49
49,38,65,97,76,13,27,49
49,38,65,97,76,13,27,49，希尔排序过程如下图所示：
第一趟取增量
d
1
=
5
d_1=5
d1=5，将该序列分为5个子序列，分别对各子序列进行直接插入排序，结果如图所示；
第二趟取增量
d
2
=
3
d_2=3
d2=3，分别对3个子序列进行插入排序；
第三趟取增量
d
3
=
1
d_3=1
d3=1，排序达到尾声，对整个序列进行一趟直接插入排序，得到最后结果。
代码如下所示：
void InsertSort(ElemType s[],int n){
//注意s[0]只是暂存单元，不是哨兵
int i,j;
for(int dk=n/2;dk>=1;dk=dk/2){//步长变化
for (i=dk+1; i<=n; ++i) {//遍历所有当前步长的子序列
//在子序列内进行直接插入排序，从子序列中的第二位开始比较插入，到子序列的最后一位
if(s[i]0&&s[0]
希尔排序算法的性能分析
1）空间效率：仅使用了常数个辅助单元，因此空间复杂度为
O
(
1
)
O(1)
O(1)。
2）时间效率：当
n
n
n 在某个特定范围时，希尔排序的时间复杂度为
O
(
n
1.3
)
O(n^{1.3})
O(n1.3)。在最坏情况下希尔排序的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难
3）不稳定性：当相同关键字的记录被划分到不同的子表，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序算法。
4）适用性：希尔排序算法仅适用于线性表未顺序存储的情况。
8.3 交换排序
交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。算法虽然很多，但主要考察冒泡排序和快速排序。
冒泡排序
基本思想：从后向前两两比较相邻元素的值，若为逆序
(
A
[
i
−
1
]
>
A
[
i
]
)
(A[i-1]>A[i])
(A[i−1]>A[i])，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序序列的最后一个位置），关键字最小的元素如同气泡一样逐渐往上“漂浮”（或关键字最大的元素如石头一样下沉到水底）。下一趟冒泡时，前一趟确定的最小元素不再参与比较。这样最多做n-1趟冒泡就能把所有元素排序好。
冒泡排序每趟排序都会将一个元素放在其最终的位置上，即所产生的有序子序列一定是全局有序的（不同于直接插入排序）
如下图所示，冒泡排序的过程：
冒泡排序代码如下：
void BubbleSort(ElemType A[],int n){
//注意A[0]也是暂存单元，用于交换操作
for (int i=1; ii; --j) {//一趟的冒泡排序
if (A[j-1]>A[j]) {
//交换
A[0]=A[j];
A[j]=A[j-1];
A[j-1]=A[0];
flag=true;
}
}
if (flag==false) {
return;//本趟遍历后没有发生交换，表示表已经有序
}
}
}
冒泡排序的性能分析
1）空间效率：仅使用了常数个辅助单元，因而空间复杂度为
O
(
1
)
O(1)
O(1)
2）时间效率：平均时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)
1）当初始序列有序时，显然第一趟冒泡后
f
l
a
g
flag
flag 依旧为
f
a
l
s
e
false
false ，从而跳出循环，比较次数为
n
−
1
n-1
n−1，移动次数为
0
0
0，从而最好情况下的时间复杂度为
O
(
n
)
O(n)
O(n)
2）当初始序列为逆序时，需要进行
n
−
1
n-1
n−1 趟排序，第
i
i
i 趟排序要进行
n
−
i
n-i
n−i 次关键字排序，而且每次比较都必须移动元素3次来交换位置。这种情况下，比较次数为
∑
i
=
1
n
−
1
(
n
−
i
)
=
n
(
n
−
1
)
2
sum_{i=1}^{n-1}{(n-i)}=frac{n(n-1)}{2}
∑i=1n−1(n−i)=2n(n−1)，总的移动次数也达到最大，为
∑
i
=
1
n
−
1
3
(
n
−
i
)
=
3
n
(
n
−
1
)
2
sum_{i=1}^{n-1}{3(n-i)}=frac{3n(n-1)}{2}
∑i=1n−13(n−i)=23n(n−1)，所以最坏情况下的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2) ，其平均时间复杂度也为
O
(
n
2
)
O(n^2)
O(n2)
3）稳定性：冒泡排序是一种稳定的排序方法。
快速排序
基本思想：基于分治法，在待排序表
L
[
1...
n
]
L[1...n]
L[1...n] 中任取一个元素
p
i
v
o
t
pivot
pivot 作为枢轴（或基准，通常取首元素）通常一趟排序将待排序表划分为独立的两部分
L
[
1...
k
−
1
]
L[1...k-1]
L[1...k−1] 和
L
[
k
+
1...
n
]
L[k+1...n]
L[k+1...n]，使得
L
[
1...
k
−
1
]
L[1...k-1]
L[1...k−1] 中的所有元素小于
p
i
v
o
t
pivot
pivot，
L
[
k
+
1...
n
]
L[k+1...n]
L[k+1...n]中的所有元素大于等于
p
i
v
o
t
pivot
pivot ，则
p
i
v
o
t
pivot
pivot 放在了其最终位置
L
[
k
]
L[k]
L[k] 上，这个过程称为一趟快速排序（或一次划分）。然后分别递归地对两个子表重复步骤
快速排序是所有内部排序算法中平均性能最优的排序算法
具体示例如下所示：
假设两个指针
i
i
i 和
j
j
j ，初值分别为
l
o
w
low
low 和
h
i
g
h
high
high，取第一个元素
49
49
49 为枢轴，赋值到变量
p
i
v
o
t
pivot
pivot 中
指针
j
j
j 从
h
i
g
h
high
high 往前搜索找到第一个小于枢轴的元素
27
27
27，将
27
27
27 交换到
i
i
i 所指的位置
指针
i
i
i 从
l
o
w
low
low 往后搜索找到第一个大于枢轴的元素
65
65
65，将
65
65
65 交换到
j
j
j 所指的位置
指针
j
j
j 继续往前搜索找到第一个小于枢轴的元素
13
13
13，将
13
13
13 交换到
i
i
i 所指的位置
指针
i
i
i 继续往后搜索找到第一个大于枢轴的元素
97
97
97，将
97
97
97 交换到
j
j
j 所指的位置
指针
j
j
j 继续往前搜索小于枢轴的元素，直到
i
=
=
j
i==j
i==j
第一趟划分结束，
i
=
=
j
i==j
i==j处的位置放入
p
i
v
o
t
=
49
pivot=49
pivot=49 ，即其最终位置得到确定。此时，指针
i
i
i 之后的元素均大于等于
49
49
49，
i
i
i 之前的元素均小于
49
49
49 ，将原序列分割成了前后两个子序列。
按照同样的方法对各上面的子序列再进行多次划分，直到待排序列中只含有一个元素，此时显然已有序。
具体代码如下所示：
int Partition(ElemType A[],int low,int high){//划分函数，函数将表中的元素被枢轴值一分为二
//表中比枢轴大的元素向右移，比枢轴小的元素向左移
int i=low,j=high;
ElemType pivot=A[low];//将当前表中的第一个元素设为枢轴
while(i=pivot) {//指针j往前搜索找到小于枢轴的元素为止
j--;
}
A[i]=A[j];//将j找到的比枢轴小的元素换到左边
while (i
快速排序算法的性能分析
1）空间效率
由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。
最好的情况下为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)；
最坏情况下，进行
n
−
1
n-1
n−1 次递归调用，栈深度为
O
(
n
)
O(n)
O(n)；
平均情况下，栈深度为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)。
2）时间效率：
快速排序的运行时间与划分是否对称有关；
快速排序的最坏情况发生在两个区域分别包含
n
−
1
n-1
n−1个元素和0个元素，这种最大限度的不对称性若发生在每层递归上，即对应初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
在理想情况下，划分函数能做到最平衡的划分，得到的两个子表长度不可能大于
n
2
frac{n}{2}
2n，在这种情况下，快速排序的运行速度将大大增加， 此时，时间复杂度为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)。
且快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，所以平均时间复杂度为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)。
有很多方法可以提高算法效率：一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取三个元素的中间值作为最终的枢轴元素；或者随机的从当前表中选取枢轴元素，这样可使得最坏情况在实际排序中几乎不会发生
3）不稳定性：快速排序是一种不稳定的排序方法。
8.4 选择排序
基本思想：每一趟（如第
i
i
i 趟）在后面
n
−
i
+
1
(
i
=
1
,
2
,
.
.
.
,
n
−
1
)
n-i+1(i=1,2,...,n-1)
n−i+1(i=1,2,...,n−1)个待排序元素中选取关键字最小的元素，作为有序子序列的第
i
i
i 个元素，直到第
n
−
1
n-1
n−1 趟做完，待排序元素只剩1个，就不用再选了。
简单选择排序
根据上面选择排序的思路，可以直接得到简单排序的算法：假设排序表为
L
[
1...
n
]
L[1...n]
L[1...n]，第
i
i
i 趟排序即从
L
[
i
.
.
.
n
]
L[i...n]
L[i...n] 中选择关键字最小的元素与
L
[
i
]
L[i]
L[i] 交换，每一趟排序可以确定一个元素的最终位置，这样经过
n
−
1
n-1
n−1 趟排序就可使得整个排序表有序。
具体代码如下：
void SelectSort(ElemType A[],int n){
//注意A[0]是暂存单元，用于交换操作
int i,j,min;
for(i=1;i
简单选择排序算法的性能分析
1）空间效率：空间效率为
O
(
1
)
O(1)
O(1)；
2）时间效率：时间复杂度始终是
O
(
n
2
)
O(n^2)
O(n2)；
在简单选择排序中，元素移动的操作次数很少，不会超过
3
(
n
−
1
)
3(n-1)
3(n−1) 次，最好的情况时移动0次，此时，对应的表已经有序；但元素减的比较次数与序列的初始状态无关，始终是
n
(
n
−
1
)
2
frac{n(n-1)}{2}
2n(n−1)次
3）不稳定性：简单选择排序是一种不稳定的排序方法。
堆排序
堆：n个关键字序列
L
[
1...
n
]
L[1...n]
L[1...n]称为堆，当前仅当该序列满足：
1）
L
(
i
)
⩾
L
(
2
i
)
L(i)geqslant L(2i)
L(i)⩾L(2i) 且
L
(
i
)
⩾
L
(
2
i
+
1
)
L(i)geqslant L(2i+1)
L(i)⩾L(2i+1) 或
2）
L
(
i
)
⩽
L
(
2
i
)
L(i)leqslant L(2i)
L(i)⩽L(2i) 且
L
(
i
)
⩽
L
(
2
i
+
1
)
（
1
⩽
i
⩽
└
n
2
┘
）
L(i)leqslant L(2i+1) （1leqslant i leqslant llcorner frac{n}{2} lrcorner ）
L(i)⩽L(2i+1)（1⩽i⩽└2n┘）
可以将该一堆数组视为一棵完全二叉树
满足条件1）的堆称为大根堆（大顶堆），大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。下图是一个大根堆的举例：
满足条件2）的堆称为小根堆（小顶堆），小根堆的定义刚好相反，根结点是最小元素。
堆排序的思路：
1）首先将存放在
L
[
1...
n
]
L[1...n]
L[1...n] 中的
n
n
n 个元素建成初始堆
2）由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值，输出堆顶元素
3）输出堆顶元素后，将剩余元素调整为新的堆，再输出堆顶元素，直到堆中仅剩一个元素。
1、如何将无序序列构造成初始堆？
n
n
n个结点的完全二叉树，最后一个结点是第
└
n
2
┘
llcorner frac{n}{2} lrcorner
└2n┘ 个结点的孩子。对第
└
n
2
┘
llcorner frac{n}{2} lrcorner
└2n┘ 个结点为根的子树筛选，使该子树成为堆（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换）。
之后依次向前依次对各结点(
└
n
2
┘
−
1
llcorner frac{n}{2} lrcorner-1
└2n┘−1 ~
1
1
1)为根的子树进行筛选，看该结点值时候大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换。
交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构造成对为止。
反复操作上述步骤建堆，直到根结点为止。
例如下图所示：{53,17,78,09,45,65,87,32} 建立初始堆 {87,45,78,32,17,65,53,09}
a）初始时找到
i
=
└
n
2
┘
=
4
i=llcorner frac{n}{2} lrcorner=4
i=└2n┘=4 为根的子树，
09
<
32
09<32
09<32，交换，交换后满足大根堆的定义；
b）继续向前调整
i
=
3
i=3
i=3 为根的子树，
78
<
左
右
孩
子
的
较
大
者
87
78<左右孩子的较大者87
78<左右孩子的较大者87，交换，交换后满足堆的定义；
c）继续向前调整
i
=
2
i=2
i=2 为根的子树，
17
<
左
右
孩
子
的
较
大
者
45
17<左右孩子的较大者45
17<左右孩子的较大者45，交换，交换后满足堆的定义；
d）继续向前调整
i
=
1
i=1
i=1 为根的子树，
53
<
左
右
孩
子
的
较
大
者
87
53<左右孩子的较大者87
53<左右孩子的较大者87，交换，交换后破坏了
i
=
3
i=3
i=3的子树，需要检查
i
=
3
i=3
i=3 的子树此时是否符合堆的定义；
e）检查
i
=
3
i=3
i=3 的子树，
53
<
左
右
孩
子
的
较
大
者
78
53<左右孩子的较大者78
53<左右孩子的较大者78，证明此时子树并不符合堆的定义，需要进行53和78的交换操作，交换后，符合堆的定义，并且没再破坏任何子树，退回
i
=
1
i=1
i=1，构造初始堆完成。
构建
n
n
n 个记录的初始堆，其时间复杂度为
O
(
n
)
O(n)
O(n)
2、输出栈顶元素后，如何将剩余元素调整为新的堆？
输出堆顶元素后，通常将堆低元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素，直到堆中仅剩一个元素。
例如下图所示：初始堆 {87,45,78,32,17,65,53,09}
输出栈顶元素87，将堆中的最后一个元素09换成栈顶，堆的性质被破坏，需要向下进行筛选处理；
1）从
i
=
1
i=1
i=1 为根的子树开始，
09
<
左
右
孩
子
的
较
大
者
78
09<左右孩子的较大者78
09<左右孩子的较大者78，交换，交换后破坏了
i
=
3
i=3
i=3的子树，需要检查
i
=
3
i=3
i=3 的子树此时是否符合堆的定义；
2）检查
i
=
3
i=3
i=3 的子树，
09
<
左
右
孩
子
的
较
大
者
65
09<左右孩子的较大者65
09<左右孩子的较大者65，证明此时子树并不符合堆的定义，需要进行09和65的交换操作
3）交换后，
i
=
3
i=3
i=3的子树符合堆的定义，并且没再破坏任何子树，退回
i
=
1
i=1
i=1，用剩余元素构造新堆的任务完成。
在具有
n
n
n个结点的队中，删除一个元素的时间复杂度为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)
3、如何对堆进行插入操作？
堆也支持插入操作。先将新结点放在堆的末端，再对这个新结点向上执行调整操作。如下图所示：
向具有
n
n
n 个结点的队中插入一个新元素的时间复杂度
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)
下面是具体实现代码：
void HeadAdjust(ElemType A[],int k,int n){
//函数HeadAdjust将元素k为根的子树进行筛选
A[0]=A[k];//A[0]暂存子树的根结点
for(int i=2*k;i=A[i]){
break;//符合堆的定义，不用进行筛选
}
else{
//如果不符合堆的定义，则进行交换
A[k]=A[i];
//交换后可能会导致，以交换后的子结点为根的子树堆性质被破坏
k=i;//检查子树的性质
}
}
A[k]=A[0];
}
void BuildMaxHeap(ElemType A[],int n){
//建立大根堆
for(int i=n/2;i>0;i--){
//从i=[n/2]~1，依次调整堆
HeadAdjust(A, i, n);
}
}
void HeapSort(ElemType A[],int n){
//建立初始堆
BuildMaxHeap(A, n);
for(int i=n;i>1;i--){
//把原来堆低元素与堆顶元素交换
A[0]=A[1];
A[1]=A[i];
A[i]=A[0];
//调整堆，把剩余的i-1个元素重新整理成堆
HeadAdjust(A,1,i-1);
}
}
堆排序算法的性能分析如下：
1）空间效率：空间复杂度为
O
(
1
)
O(1)
O(1)；
2）时间效率：建堆时间为
O
(
n
)
O(n)
O(n)，之后有
n
−
1
n-1
n−1次向下调整操作，每次调整的时间复杂度为
O
(
h
)
O(h)
O(h)，故在最好、最坏和平均情况下，堆排序的时间复杂度都为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)；
3）不稳定性：堆排序算法是一种不稳定的排序算法。
堆排序适合关键字较多的情况。
例如，如何在1亿个数中选出前100个最大值？
首先使用一个大小为100的数组，读入前100个数，建立小顶堆；
而后依次读下余下的树，若小于堆顶则舍弃，否则用该树取代堆顶并重新调整堆；
待数据读取完毕，堆中100个数即为所求。
8.5 归并排序和基数排序
归并排序
归并的含义是将两个或两个以上的有序表组合成一个新的有序表。
假定待排序表含有
n
n
n 个记录，则可将其视为
n
n
n 个有序的子表，每个子表的长度为1，然后两两归并，得到
┌
n
2
┐
ulcorner frac{n}{2} urcorner
┌2n┐ 个长度为2或1的有序表；继续两两归并…如此重复，直到合并成一个长度为
n
n
n。这种排序方法称为2路归并排序。
下图为2路归并排序的一个例子：
合并的做法具体如下：设两段有序表
A
[
l
o
w
.
.
.
m
i
d
]
A[low...mid]
A[low...mid]、
A
[
m
i
d
+
1...
h
i
g
h
]
A[mid+1...high]
A[mid+1...high]存放在同一顺序表中相邻的位置，先将他们复制到辅助数组B中，每次从对应B中的两个段取出一个记录进行关键字比较，较小者放入A中，当数组B中有一段的下标超出其对应的表长时（即该段的所有元素都已经复制到A中），将另一段中的剩余部分直接复制到A中。
一趟归并的操作是：调用
┌
n
2
h
┐
ulcorner frac{n}{2h} urcorner
┌2hn┐次合并算法，将
L
[
1...
n
]
L[1...n]
L[1...n] 中前后相邻且长度为
h
h
h 的有序段进行两两归并，得到前后相邻，长度为
2
h
2h
2h 的有序段，整个归并排序需要进行
┌
l
o
g
2
n
┐
ulcorner log_2n urcorner
┌log2n┐ 趟
一般而言，对于
N
N
N 个元素进行
k
k
k 路归并排序时，排序的趟数
m
m
m 满足
k
m
=
N
k^m=N
km=N，即
m
=
┌
l
o
g
k
N
┐
m=ulcorner log_kN urcorner
m=┌logkN┐
具体代码如下：
void Merge(ElemType A[],int low,int mid,int high){
//表A的两段A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
int i,j,k;
ElemType *B=(ElemType *)malloc((high+1)*sizeof(ElemType));//辅助数组B
for (k=low; k<=high; k++) {
B[k]=A[k];//将A中所有元素复制到B中
}
for (i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
//比较B的左右两段中的元素，将较小值复制到A中
if(B[i]<=B[j]){
A[k]=B[i++];
}
else{
A[k]=B[j++];
}
}
//若第一个表未检测完，则复制
while (i<=mid) {
A[k++]=B[i++];
}
//若第二个表未检测完，则复制
while (j<=high) {
A[k++]=B[j++];
}
}
void MergeSort(ElemType A[],int low,int high){
if(low
2路归并排序算法的性能分析
1）空间效率
归并操作中，辅助空间为n个单元，所以空间复杂度为
O
(
n
)
O(n)
O(n)
2）时间效率
每趟归并的时间复杂度为
O
(
n
)
O(n)
O(n)，共需进行
┌
l
o
g
2
n
┐
ulcorner log_2n urcorner
┌log2n┐ 趟归并。所以时间复杂度为
O
(
n
l
o
g
2
n
)
O( nlog_2n)
O(nlog2n)
3）稳定性
2路归并排序是一种稳定的排序方法。
基数排序
基数排序是一种不基于比较和移动的排序方法，而是基于关键字各位的大小排序。
实现基数排序有两种方法：
第一种是最高位优先法（MSD），按关键字权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。
第二种是最低位优先法（LSD），按关键字权重递增依次进行排序，最后形成一个有序序列。
例如，下面是 以
r
=
10
r=10
r=10 为基数 的 最低位优先 链式 基数排序的过程，在排序过程中需要借助10个链队列。
第一趟分配，用3位关键字的最低位（个位）进行分配收集
收集：是指把各个队列的结点依次首尾相连，得到新的结点序列，从而组成新的线性表。
第二趟分配，在第一趟收集后的排序序列的基础上，在对次低位关键字（十位）进行分配收集
第三趟同理，在第二趟收集后的排序序列的基础上，在最高位关键字（百位）进行分配收集，自此，整个排序结束
基数排序算法的性能分析
1）空间效率
一趟排序需要的辅助空间为
r
r
r （
r
r
r个队列：
r
r
r个队头指针和
r
r
r个队尾指针），但在以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为
O
(
r
)
O(r)
O(r)。
2）时间效率
基数排序需要进行
d
d
d趟分配和收集，一趟分配需要
O
(
n
)
O(n)
O(n)，一趟收集需要
O
(
r
)
O(r)
O(r)，所以基数排序的时间复杂度为
O
(
d
(
n
+
r
)
)
O(d(n+r))
O(d(n+r))，且它与序列初始状态无关。
3）稳定性：基数排序是稳定算法。
8.6 算法小结
由于希尔排序的时间复杂度依赖于增量函数，所以无法准确的给出其时间复杂度。
小结：
1）若
n
n
n 较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需要的记录移动次数比简单选择排序的多，因此当记录本身信息量较大的时候，用简单选择排序较好。
2）若
n
n
n 较大，则应采用时间复杂度为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)的排序方法：快速排序、堆排序或归并排序。
快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。
堆排序所需的辅助空间少于开始排序，并且不会出现快速排序中可能出现的最坏情况，这两种排序都是不稳定的。
若要求排序稳定且时间复杂度为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)，则可选用归并排序。
3）若
n
n
n很大，但记录的关键字位数较少且可分解时，采用基数排序较好
4）若文件的初始状态已按关键字基本有序，则选用直接插入排序或冒泡排序。
5）当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。即可以采用直接插入排序或者基数排序。
6）在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能情况，所以可以用一棵二叉树来描述比较判定的过程，由此可知：当文件n个关键字随机分布时，任何借助“比较”的排序算法，都至少需要
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)的时间
