内部排序（插入、交换、选择）
一、排序的部分基本概念
1. 算法的稳定性
若待排序表中有两个元素 Ri 和 Rj ，其对应的关键字相同即 keyi = keyj，且在排序前 Ri 在 Rj 的前面，若使用某一排序算法排序后，Ri 仍然在 Rj 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣 ，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。
2. 排序的分类
在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：
1）内部排序
是指在排序期间元素全部存放在内存中的排序。
2）外部排序
是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。
3. 一些结论
对于任意序列进行基于比较的排序，求至少的比较次数应考虑最坏情况。对任意 n 个关键字排序的比较次数至少为 ⌈log2(n!)⌉ 。
上述公式证明如下：在基于比较的排序方法中，每次比较两个关键字后，仅出现两种可能的转移。假设整个排序过程至少需要做 t 次比较，则显然会有 2t 种情况。由于 n 个记录共有 n! 种不同的排列，因而必须有 n! 种不同的比较路径，于是有 2t >= n!，即 t >= log2(n!) 。考虑到 t 为整数，故为 ⌈log2(n!)⌉ 。
二、插入排序
插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序和希尔排序。
【注】默认排序结果为非递减有序序列。
1. 直接插入排序
1）算法思想与实现步骤
① 直接插入排序的基本思想是：
将待排序的数组分为已排序和未排序两部分。每次从未排序部分中取出一个元素，找到其在已排序部分中的合适位置并插入。
② 直接插入排序的实现步骤是：
a）从第二个元素开始，依次取出待排序部分的第一个元素(当前元素)。
b）与已排序部分的元素进行比较，找到当前元素合适的插入位置。
（即找到元素 L(i) 在有序序列 L[1…i - 1] 中的插入位置 k ）
c）将已排序部分中大于当前元素的元素向后移动一位，为当前元素腾出位置。
（即将 L[ k…i - 1] 中的所有元素依次后移一个位置）
d）将当前元素插入到找到的位置
（即将 L(i) 复制到 L(k) ）
e）重复步骤 a-d 直到所有元素均被插入。
为了实现对 L[1…n] 的排序，可以将 L(2) ~ L(n) 依次插入前面已排好序的子序列，初始 L[1] 可以视为是一个已排好序的子序列。插入排序在实现上通常采用 就地排序（空间复杂度为 O(1) ），因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。
2）算法的C++代码
void InsertSort(ElemType A[],int n) {int i, j;for(i=2; i<=n; i++) { // 依次将A[2]~A[n]插入前面已排好序的序列中if(A[i]<A[i-1]) { // 若A[i]关键字小于其前驱，将A[i]插入有序表A[0] = A[i]; // 复制为哨兵，A[O]不存放元素for(j=i-1; A[0]<A[j]; --j){ // 从后往前查找待插入位置A[j+1] = A[j]; // 向后挪位} A[j+1] = A[O] ; // 复制到插入位置}}
}
3）示例
假定初始序列为 49, 38, 65, 97, 76, 13, 27, 49’，初始时 49 可以视为一个已排好序的子序列，按照上述算法进行直接插入排序的过程如下图所示，括号内是已排好序的子序列。
4）算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O(1) 。
II、时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了 n - 1 趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。
- 在最好情况下：表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为 O(n) 。
- 在最坏情况下：表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大，总的移动次数也达到最大，总的时间复杂度为 O(n2) 。
- 平均情况下：考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为 n2 / 4 。
因此，直接插入排序算法的时间复杂度为 O(n2) 。
② 稳定性
由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
③ 适用性
直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
2. 折半插入排序
从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作： ① 从前面的有序子表中查找出待插入元素应该被插入的位置；② 给插入位置腾出空间，将待插入元素复制到表中的插入位置。
当排序表为顺序表时，可以对直接插入排序算法做如下改进： 由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。
1）算法思想与实现步骤
① 折半插入排序的基本思想是：
折半插入排序是对直接插入排序的优化，通过折半查找的方法来提高插入的位置寻找效率。它减少了比较次数，但在后面的插入步骤中仍需移动元素。
② 折半插入排序的实现步骤是：
a）从第二个元素开始，依次取出待排序部分的第一个元素(当前元素)。
b）在已排序部分使用折半查找找到当前元素的插入位置。
c）移动已排序部分中大于当前元素的元素，为当前元素腾出位置。
d）将当前元素插入到找到的位置。
e）重复步骤 a-e 直到所有元素均被插入。
2）算法的C++代码
void InsertSort(ElemType A[], int n) {int i, j, low, high, mid;for(i=2; i<=n; i++) { // 依次将A[2]~A[n]插入前面的已排序序列A[O] = A[i]; // 将A[i]暂存到A[O]low = 1; high = i-1; // 设置折半查找的范围while(low <= high) { // 折半查找（默认递增有序）mid = (low+high)/2; // 取中间点if(A[mid]>A[O]){high = mid-1;} // 查找左半子表else{low = mid+1;} // 查找右半子表}for(j=i-1; j>=high+1; --j){ // 此时的high+1=lowA[j+1] = A[j]; // 统一后移元素，空出插入位置}A[high+1] = A[O]; // 插入操作}
}
3）算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O(1) 。
II、从上述算法中，不难看出折半插入排序仅减少了比较元素的次数，约为 O(nlog2n)，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数 n ；而元素的移动次数并未改变，它依赖于待排序表的初始状态。
因此，折半插入排序的时间复杂度仍为 O(n2) ，但对于数据量不很大的排序表， 折半插入排序往往能表现出很好的性能。
② 稳定性
折半插入排序是一种稳定的排序方法。
③ 适用性
折半插入排序算法仅适用于顺序存储的线性表。
3. 希尔排序
直接插入排序算法的时间复杂度为 O(n2)，但若待排序列为“正序”时，其时间效率可提高至 O(n)，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。
1）算法思想与实现步骤
① 希尔排序的基本思想是：
希尔排序是插入排序的一种改进版本，通过选取增量序列来将数组分成多个子序列，分别进行局部排序，最后再进行整体插入排序。这种方法可以减少元素的移动次数，提升排序效率。
② 希尔排序的实现步骤是：
a）选择一个增量序列。
（例如，初始增量为 d（小于 n ，通常 d = n / 2），随后不断缩小增量，直到增量为 1 ）
b）对于每个增量，按增量将整个数组分为若干个子序列。
（即将待排序表分割成若干形如 L[ i, i + d, i + 2d, … , i + kd ] 的“特殊"子序列）
c）对每个子序列进行直接插入排序。
d）重复步骤 b-c，直到增量为 1 。
e）最后对整个数组进行一次插入排序，确保整体有序。
2）算法的C++代码
void ShellSort(ElemType A[] , int n) {
// A[O]只是暂存单元，不是哨兵，当j<=O时，插入位置已到int d, i, j;for(d=n/2; d>=1; d=d/2){ // 增量变化（无统一规定）for(i=d+1; i<=n; ++i){if(A[i]<A[i-d]){ // 需将A[i]插入有序增量子表A[O] = A[i]; // 暂存在A[O]for(j=i-d; j>O && A[0]<A[j]; j-=d){A[j+d] = A[j]; // 记录后移，查找插入的位置}A[j+d] = A[0]; // 插入}}}
}
3）示例
（先追求表中元素部分有序，再逐渐逼近全局有序。）
4）算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率： 仅使用了常数个辅助单元，因而空间复杂度为 O(1) 。
II、时间效率： 由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。
- 当 n 在某个特定范围时，希尔排序的时间复杂度约为 O(n1.3) 【优于直接插入排序】。
- 在最坏情况下希尔排序的时间复杂度为 O(n2) 。
希尔排序最好的情况是序列原本就有序，比较好的情况是序列基本有序。
② 稳定性
当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
③ 适用性
希尔排序算法仅适用于线性表为顺序存储的情况。
4. 例题
① 折半插入排序算法的时间复杂度为（ C ）。
A. O(n)
B. O(nlog2n)
C. O(n2)
D. O(n3)
② 【2012 统考真题】对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ D ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
③ 【2014 统考真题】用希尔排序方法对一个数据序列进行排序时，若第一趟排序结果为 9, 1, 4, 13, 7, 8, 20, 23, 15 , 则该趟排序采用的增量（间隔）可能是（ B ）。
A. 2
B. 3
C. 4
D. 5
④ 【2015 统考真题】希尔排序的组内排序采用的是（ A ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
⑤ 【2018 统考真题】对初始数据序列 (8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6) 进行希尔排序。若第一趟排序结果为 (1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8) ，第二趟排序结果为 (1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9) ，则两趟排序采用的增量（间隔）依次是（ D ）。
A. 3, 1
B. 3, 2
C. 5, 2
D. 5, 3
三、交换排序
所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多，下面主要介绍冒泡排序和快速排序。
1. 冒泡排序
1）算法思想与实现步骤
① 冒泡排序的基本思想是：
冒泡排序通过从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 A[i - 1] > A[ i ] ），则交换它们，将最小的元素逐步“冒泡”到序列的开头（或将最大的元素逐步“冒泡”到序列的末尾）。这个过程重复进行，前一趟确定的最小（或最大）的元素不再参与比较，每趟冒泡都会将未确定序列中下一个最小（或最大）的元素放到正确的位置。这样最多做 n - 1 趟冒泡就能把所有元素排好序。
② 冒泡排序的实现步骤是：
a）从尾到头（或从头到尾）遍历序列，比较相邻的两个元素。
b）如果前一个元素大于后一个元素，则交换这两个元素。
c）每遍历一轮，最小的元素会传到序列的开头（或最大的元素会传到序列的末尾）。
d）重复步骤 a-c，直到没有交换发生为止。
注意：冒泡排序中所产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中的所有元素的关键字一定小于（或大于）无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。
2）算法的C++代码
void BubbleSort(ElemType A[],int n){for(int i=O; i<n-1; i++){bool flag = false; // 表示本趟冒泡是否发生交换的标志for(int j=n-1; j>i; j--){ // 一趟冒泡过程if(A[j-1] > A[j]){ // 若为逆序swap (A[j-1], A[j]); // 交换flag = true;}}if(flag==false){return;} // 本趟遍历后没有发生交换，说明表已经有序}
}
3）示例
4）算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O(1) 。
II、时间效率：
- 当初始序列有序时，显然第一趟冒泡后 flag 依然为 false（本趟没有元素交换），从而直接跳出循环，比较次数为 n - 1，移动次数为 0，从而最好情况下的时间复杂度为 O(n)；
- 当初始序列为逆序时，需要进行 n - 1 趟排序，第 i 趟排序要进行 n - i 次关键字的比较，而且每次比较后都必须移动元素 3 次来交换元素位置。
从而，最坏情况下的时间复杂度为O(n2)，平均时间复杂度为O(n2) 。
② 稳定性
由于 i > j 且 A [i] = A [j] 时，不会发生交换，因此冒泡排序是一种稳定的排序方法。
③ 适用性
冒泡排序算法适用于顺序存储和链式存储的线性表。
2. 快速排序
1）算法思想与实现步骤
① 快速排序的基本思想是：
快速排序采用分治法，在待排序表 L[1…n] 中任取一个元素 pivot 作为枢轴（或称基准，通常取首元素），通过一趟排序将待排序表划分为独立的两个子表 L[1…k - 1] 和 L[k + 1…n]，使得 L[1…k - 1] 中的所有元素小于 pivot，L[k + 1…n] 中的所有元素大于或等于 pivot，则 pivot 放在了其最终位置 L(k) 上，这个过程称为一次划分。然后分别递归地对左右两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。
② 快速排序的实现步骤是：
a）从待排序表中选择一个基准元素（通常选第一个、最后一个或中间的元素）。
b）将待排序表重排，使得基准的左侧是所有小于基准的元素，右侧是所有大于基准的元素。
c）递归地对基准左侧和右侧的子表进行快速排序。
d）直到子表的规模为 1 或 0（即已经是有序的）。
注意：在快速排序算法中，并不产生有序子序列，但每趟排序后会将上一趟划分的各个无序子表的枢轴（基准）元素放到其最终的位置上。
2）算法的C++代码
void QuickSort (ElemType A[],int low,int high){if(low < high) { // 递归跳出的条件int pivotpos = Partition(A, low, high); // 划分// Partition()就是划分操作，将表A[low…high]划分为满足上述条件的两个子表QuickSort(A, low, pivotpos-1); // 依次对两个子表进行递归排序QuickSort(A, pivotpos+l, high);}
}
int Partition(ElemType A[], int low, int high) { // 一趟划分ElemType pivot = A[low]; // 将当前表中第一个元素设为枢轴，对表进行划分while(low < high) { // 循环跳出条件while(low < high && A[high] >= pivot) {--high;}A[low] = A[high]; // 将比枢轴小的元素移动到左端while(low < high && A[low] <= pivot) {++low;}A[high] = A[low]; // 将比枢轴大的元素移动到右端}A[low] = pivot; // 枢轴元素存放到最终位置return low; // 返回存放枢轴的最终位置
}
3）示例
用二叉树的形式描述这个举例的递归调用过程，如下图所示：
4）算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大深度一致。
- 最好情况下为 O(log2n）；
- 最坏情况下，因为要进行 n - 1 次递归调用，所以栈的深度为 O(n) ；
- 平均情况下，栈的深度为 O(log2n) 。
II、时间效率：快速排序的运行时间与划分是否对称有关。快速排序的最坏情况发生在两个区域分别包含 n - 1 个元素和 0 个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 O(n2) 。
有很多方法可以提高算法的效率： 一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。
在最理想的状态下，即 Partition() 可能做到最平衡的划分，得到的两个子问题的大小都不可能大于n / 2，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为O(nlog2n) 。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。
② 稳定性
在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。
③ 适用性
快速排序算法仅适用于顺序存储的线性表。
3. 例题
① 快速排序算法在（ D ）情况下最不利于发挥其长处。
A. 要排序的数据量太大
B. 要排序的数据中含有多个相同值
C. 要排序的数据个数为奇数
D. 要排序的数据已基本有序
② 就平均性能而言，目前最好的内部排序方法是（ D ）。
A. 冒泡排序
B. 直接插入排序
C . 希尔排序
D. 快速排序
③ 【2010 统考真题】采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ D ）。
A. 递归次数与初始数据的排列次序元关
B. 每次划分后，先处理较长的分区可以减少递归次数
C. 每次划分后，先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关
④ 【2011 统考真题】为实现快速排序算法，待排序序列宜采用的存储方式是（ A ）。
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
⑤ 【2014 统考真题】下列选项中，不可能是快速排序第 2 趟排序结果的是（ C ）。
A. 2, 3, 5, 4, 6, 7, 9
B. 2, 7, 5, 6, 4, 3, 9
C. 3, 2, 5, 4, 7, 6, 9
D. 4, 2, 3, 5, 7, 6, 9
⑥ 【2019 统考真题】排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（ D ）。
A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60
⑦ 【2023 统考真题】使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的枢轴是（ D ）。
A. 11
B. 70
C. 80
D. 81
⑧ 对 8 个元素的序列进行快速排序，在最好情况下的关键字比较次数是（ D ）。
A. 7
B. 8
C. 12
D. 13
【快速排序的最好情况是每次划分将待排序序列划分为等长的两部分。】
⑨ 双向冒泡排序是指对一个序列在正反两个方向交替进行扫描，第一趟把最大值放在序列的最右端，第二趟把最小值放在序列的最左端，之后在缩小的范围内进行同样的扫描，放在次右端、次左端，直到序列有序。对数组 {4, 7, 8, 3, 5, 6, 10, 9, 1, 2} 进行双向冒泡排序，则排序趟数是（ B ）。（第一趟从左往右开始，从左往右或从右往左都称为一趟。）
A. 7
B. 6
C. 8
D. 9
【序列已有序后，仍需再进行一趟无交换的排序才能确定序列已有序。】
四、选择排序
选择排序的基本思想是： 每一趟（如第 i 趟）在后面 n - i + 1（ i = 1, 2, … , n - 1 ）个待排序元素中选取关键字最小的元素，作为有序子序列的第 i 个元素，直到第 n - 1 趟做完，待排序元素只剩下 1 个，就不用再选了。
1. 简单选择排序
1）算法思想与实现步骤
① 简单选择排序的基本思想是：
简单选择排序通过不断选择未排序部分中的最小的元素，将其放到已排序部分的末尾，逐步构建出一个非递减有序的序列。
② 简单选择排序的实现步骤是：
a）从排序表的未排序部分 L[i…n] 找到最小元素。
b）将找到的最小元素交换到已排序部分的末尾，即 L( i ) 处，每一趟排序可以确定一个元素的最终位置。
c）标记已排序部分的边界，继续对未排序部分重复步骤 a-b 。
d）直到整个数组变为有序。
2）算法的C++代码
void SelectSort(ElemType A[], int n) {for(int i=O; i<n-1; i++){ // 一共进行n-1趟int min = i; // 记录最小元素位置for(int j=i+1; j<n; j++){ // 在A[i…n-1]中选择最小的元素if(A[j] < A[min]) {min = j;} // 更新最小元素位置}if(min != i) {swap(A[i], A[min]);} // 封装的swap()函数共移动元素 3 次}
}
3）示例
4）算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率：仅使用常数个辅助单元，故空间效率为 O(1) 。
II、时间效率：在简单选择排序过程中，元素移动的操作次数很少，不会超过 3(n - 1) 次，最好的情况是移动 0 次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是 n(n - 1) / 2 次，因此时间复杂度始终是 O(n2) 。
【简单选择排序算法的比较次数为 O(n2)，移动次数为 O(n) 。】
② 稳定性
在第 i 趟找到最小元素后，和第 i 个元素交换，可能会导致第 i 个元素与其含有相同关键字元素的相对位置发生改变。例如：L = {2, 2’, 1} 经过一趟排序后 L = {1, 2’, 2}。因此，简单选择排序是一种不稳定的排序方法。
③ 适用性
简单选择排序算法适用于顺序存储和链式存储的线性表，以及关键字较少的情况。
2. 堆排序
1）了解堆的定义
① 定义1：一棵大根树（小根树） 是这样一棵树，其中每个结点的值都大于（小于）或等于其子结点（如果有子结点的话）的值。在大根树或小根树中，结点的子结点个数可以任意。
② 定义2：一个大根堆（小根堆）既是大根树（小根树）也是完全二叉树。
因为堆是完全二叉树，具有 n 个元素的堆的高度为 ⌈log2(n + 1)⌉ 。因此，如果能够在 O(height) 时间内完成插人和删除操作，那么这些操作的复杂性为 O(log2n) 。
堆的定义如下，n 个关键字序列 L [1…n] 称为堆，当且仅当该序列满足：
a）L(i) >= L(2i) 且 L(i) >= L(2i + 1) 或
b）L(i) <= L(2i) 且 L(i) <= L(2i + 1) （1 <= i <= ⌊n / 2⌋)
可以将堆视为一棵完全二叉树。
- 满足条件 a 的堆称为大根堆（大顶堆），大根堆的最大元素存放在根结点，且其任意一个非根结点的值小于或等于其双亲结点值。
- 满足条件 b 的堆称为小根堆（小顶堆），小根堆的定义刚好相反，根结点是最小元素。
2）大根堆的“上浮”和“下沉”
在大根堆中，上浮操作（Upward Sift 或 Bubble Up）和下沉操作（Downward Sift 或 Bubble Down）是确保堆性质（每个父结点的值大于或等于子结点的值）得以维持的重要操作。
① “上浮”操作：上浮操作用于在插入新元素后，调整堆的结构，确保大根堆的性质得以满足。
步骤：（自下而上）
a）将新插入的元素放在数组的末尾（即堆的最后一个位置）。
b）从该新元素的位置开始，检查其值是否大于其父结点的值。
c）如果大于，则与父结点交换位置。
d）重复以上步骤，直到达到根结点或堆的性质得以满足。
② “下沉”操作：下沉操作用于在删除堆顶元素（或在将堆的最后一个元素移到根结点后），调整堆的结构，确保大根堆的性质得以满足。
步骤：（自上而下）
a）将堆顶元素（通常是最大值）与最后一个元素交换位置。
b）移除最后一个元素（即原堆顶元素）。
c）从新根结点开始，检查其值与左右子结点的值。
d）若根结点小于任一子结点，则与较大的子结点交换位置。
e）重复以上步骤，直到达到叶结点或堆的性质得以满足。
3）大根堆的插入、初始化和删除操作
① 大根堆的插入：
a）添加元素：将新元素添加到数组末尾（堆的最后一个位置）。
b）上浮操作（自下而上）：检查新插入元素是否满足大根堆的性质。
从新元素的位置开始，若其值大于其父结点的值，则交换两者，继续向上比较，直到满足大根堆的性质或到达根结点。
示例如下图所示：在已经建好的大根堆中加入新元素 63 。
实现这种插入策略的时间复杂性为 O(height) = O(log2n) 。
② 大根堆的删除：（通常删除堆顶元素）
a）替换根节点：将堆顶（最大值）与最后一个元素交换。
b）移除最后元素：从堆中移除最后一个元素（原堆顶）。
c）下沉操作（自上而下）：从新根结点开始，进行下沉调整。
比较新根结点与其子结点，若其值小于任一子结点的值，则与较大的子结点交换，直到满足大根堆的性质。
示例如下图所示：在已经建好的大根堆中删除堆顶元素 87 。
实现这种删除策略的时间复杂性为 O(height) = O(log2n) 。
③ 大根堆的初始化：
a）创建数组：使用数组来存储堆中的元素。
b）构建堆：将无序数组转换成大根堆，通常采用“自下而上”的方法，遍历所有的非叶结点，从最后一个非叶结点开始（索引为 ⌊(n / 2)⌋ ，n 为结点总数，索引从 1 开始），依次向上调整每个结点，使其满足大根堆的性质。
c）调整结点：对每个结点调用“下沉”操作，确保其大于或等于其子结点。
数组构建堆的过程可以分为两种：
I、把数组元素逐个插入到一个空堆中，这时需要用“上浮”操作来维护大根堆的性质【为了构建这个初始的非空堆，我们需要在空堆中执行 n 次插入操作，插入操作所需的总时间为 O(nlog2n) 】；
II、更高效的做法是直接将一个无序数组转化为大根堆，再依次调整结点，这种方法称为“堆化”（Heapify），这时只需通过“下沉”操作便可完成初始化【用这种方法初始化堆的时间复杂度为 O(n) 】。
目前我们讨论的就是“堆化”的过程。
示例如下图所示：初始数组序列为 {49, 38, 65, 97, 76, 13, 27, 49’}
在大根堆的初始化过程和删除操作中，主要依赖“下沉”操作，而大根堆的插入操作中可能会使用到“上浮”操作。
4）算法思想与实现步骤
① 堆排序的基本思想是：
堆排序利用堆这种数据结构的性质，首先构建一个最大堆或最小堆，然后反复将堆顶元素（最大或最小）取出并放入有序部分。
② 堆排序的实现步骤是：
a）将待排序数组 L[1…n] 中的 n 个元素构建成一个最大堆(或最小堆)。
b）将堆顶元素与最后一个元素交换，并从堆中移除堆顶元素。
c）对剩余的元素调整为堆结构。
d）重复步骤 b 和 c，直到所有元素都有序（直到堆中仅剩一个元素为止）。
5）算法的C++代码
void BuildMaxHeap(ElemType A[],int len){for(int i=len/2; i>O; i--){ // 从i=[n/2]~1，反复调整堆HeadAdjust(A, i, len);}
}
void HeadAdjust(ElemType A [], int k, int len) {
// 函数HeadAdjust将元素k为根的子树进行调整A[O] = A[k]; // A[O]暂存子树的根结点for(int i=2*k; i<=len; i*=2){ // 沿key较大的子结点向下筛选if(i<len && A[i]<A[i+l]) {i++;} // 取key较大的子结点的下标if (A[0]>=A[i]) {break;} // 筛选结束else{A[k] = A[i]; // 将A[i]调整到双亲结点上k = i; // 修改k值，以便继续向下筛选}}A[k] = A[O]; // 被筛选结点的值放入最终位置
}
void HeapSort(ElemType A[], int len) {BuildMaxHeap(A, len); // 初始建堆for(int i=len; i>l; i--) { // n-1趟的交换和建堆过程Swap(A[i], A[1]); // 输出堆顶元素（和堆底元素交换）HeadAdjust(A, 1, i-1); // 调整，把剩余的i-1个元素整理成堆}
}
调整的时间与树高有关，为 O(h) 。在建含 n 个元素的堆时，关键字的比较总次数不超过 4n，时间复杂度为 O(n) ，这说明可以在线性时间内将一个无序数组建成一个堆。
6）算法的性能分析
堆排序适合关键字较多的情况。例如，在 1 亿个数中选出前 100 个最大值。首先使用一个大小为 100 的数组，读入前 100 个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中 100 个数即为所求。
① 时间复杂度与空间复杂度
I、空间效率：仅使用了常数个辅助单元，所以空间复杂度为 O(1) 。
II、时间效率：建堆时间为 O(n) ，之后有 n - 1 次向下调整操作， 每次调整的时间复杂度为 O(h)，故在最好、最坏和平均情况下，堆排序的时间复杂度为 O(nlog2n) 。
② 稳定性
进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。
③ 适用性
堆排序仅适用于顺序存储的线性表。
3. 例题
① 【2009 统考真题】已知关键字序列 5, 8, 12, 19, 28, 20, 15, 22 是小根堆，插入关键字 3，调整好后得到的小根堆是（ A ）。
A. 3, 5, 12, 8, 28, 20, 15, 22, 19
B. 3, 5, 12, 19, 20, 15, 22, 8, 28
C. 3, 8, 12, 5, 20, 15, 22, 28, 19
D. 3, 12, 5, 8, 28, 20, 15, 22, 19
② 【2011 统考真题】已知序列 25, 13, 10, 12, 9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（ B ）。
A. 1
B. 2
C. 4
D. 5
③ 【2015 统考真题】已知小根堆为 8, 15, 10, 21, 34, 16, 12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（ C ）。
A. 1
B. 2
C. 3
D. 4
④【2018 统考真题】在将序列 (6, 1, 5, 9, 8, 4, 7) 建成大根堆时，正确的序列变化过程是（ A ）。
A. 6, 1, 7, 9, 8, 4, 5 --> 6, 9, 7, 1, 8, 4, 5 --> 9, 6, 7, 1, 8, 4, 5 --> 9, 8, 7, 1, 6, 4, 5
B. 6, 9, 5, 1, 8, 4, 7 --> 6, 9, 7, 1, 8, 4, 5 --> 9, 6, 7, 1, 8, 4, 5 --> 9, 8, 7, 1, 6, 4, 5
C. 6, 9, 5, 1, 8, 4, 7 --> 9, 6, 5, 1, 8, 4, 7 --> 9, 6 , 7, 1, 8, 4, 5 --> 9, 8, 7, 1, 6, 4, 5
D. 6, 1, 7, 9, 8, 4, 5 --> 7, 1, 6, 9, 8, 4, 5 --> 7, 9, 6, 1, 8, 4, 5 --> 9, 7, 6, 1, 8, 4, 5 --> 9, 8, 6, 1, 7, 4, 5
⑤ 【2020 统考真题】下列关于大根堆（至少含 2 个元素）的叙述中，正确的是（ C ）。
I. 可以将堆视为一棵完全二叉树
II. 可以采用顺序存储方式保存堆
III. 可以将堆视为一棵二叉排序树
IV. 堆中的次大值一定在根的下一层
A. 仅 I 、II
B. 仅 II 、III
C. 仅 I 、II 和 IV
D. I 、III 和 IV
⑥ 【2021 统考真题】将关键字 6, 9, 1, 5, 8, 4, 7 依次插入到初始为空的大根堆 H 中，得到的 H 是（ B ）。
A. 9, 8, 7, 6, 5, 4, 1
B. 9, 8, 7, 5, 6, 1, 4
C. 9, 8, 7, 5, 6, 4, 1
D. 9, 6, 7, 5, 8, 4, 1