00:00:00
排序 原创
假设含n个记录的文件内容为 ,相应的关键字为 。经过排序确定 一种排列 ,使得它们的关键字满足以下递增(或递减)关系: （或）
一、稳定性与分类
1.1 稳定性
若在待排序的一个序列中, 和 的关键字相同,即 ,且在排序前 ,领先于R,那 么在排序后,如果 ;和 的相对次序保持不变, 仍领先于 ,则称此类排序方法为。若在排序后的序列中有可能出现 领先于 的情形,则称此类排序为的。
说明
若数组 在从小到大排序后仍然保持 在 之前则说明当前排序算法是稳定的，反之则为不稳定。
1.2分类
- 内部排序。内部排序指待排序记录全部存放在排序的过程。
- 外部排序。外部排序指待排序记录的数量很大,以至于内存不能容纳全部记录,在排序过程中尚的排序过程。
在排序过程中需要进行下列两种基本操作:
- 比大小：比较两个关键字的大小;
- 挪位置：将记录从一个位置移动到另一个位置。
前一种操作（比大小）对序方法来说都是,后一种操作。
二、常见的排序算法
常见的排序算法有：直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序、归并排序、基数排序。
2.1 直接插入排序
直接插入排序是一种简单的排序方法,具体做法是:在插入第 个记录时, 已经 排好序，这时将 的关键字 依次与关键字 等进行比较，从而找到应该插入的位置并将 插入,插 入位置及其后的记录依次向后移动。
- 排序过程演示
- 代码示例
C
// 直接插入排序函数实现
void insertSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
// 选择一个元素作为要插入的元素
key = arr[i];
j = i - 1;
// 将大于key的元素向后移动一位
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// 插入到正确的位置
arr[j + 1] = key;
}
}- 稳定性：稳定
- 比较次数
- 最好情况下（元素已经有序）：每趟排序只需作 次比较且不需要移动元素,因此 个元素排序时的总比较次数为 次,总移动次数为
0次。 - 最坏的情况下（元素已经逆序排列）：进行第 趟排序时,待插入的记录需要同前面的 个记录都 进行 次比较，因此，总比较次数为 ，排序过程中,第 趟排序时移动记录的次数为 (包括移进、移出 ),总移动次数为
- 最好情况下（元素已经有序）：每趟排序只需作 次比较且不需要移动元素,因此 个元素排序时的总比较次数为 次,总移动次数为
- 时间复杂度：
- 最好： 数组已经是有序的
- 平均/最坏： 数组逆序的
- 空间复杂度：只需要一个辅助变量，则
2.2 冒泡排序
2.2.1 核心思想 (重点)
冒泡排序是一种简单的。它的基本思想是：
- 相邻比较：从序列开头开始，两个元素。
- 逆序交换：如果它们的顺序错误（即前一个比后一个大，这是针对升序排序而言），就交换它们的位置。
- 最大值沉底：这样一轮（一趟）比较下来，最大的元素就会像石头一样“沉”到序列的最后一个位置。
- 重复过程：对剩下的
n-1个元素重复上述过程，直到整个序列有序。
形象比喻：就像水底的气泡一样，较大的数值会一步步"冒"到序列的顶端（末尾）。
2.2.2 算法特性 (考点)
- 时间复杂度：
- 最好情况（序列已有序）：。只需进行 次比较，，即可提前结束。
- 平均和最坏情况（序列逆序）：。需要进行 趟，每趟比较次数递减，总比较次数为 。
- 空间复杂度：。只用了常数个额外变量（用于交换的临时变量、循环标志等），是原地排序。
- 稳定性：。因为只有当相邻元素逆序时才交换，不会改变相同关键字的相对位置。
2.2.3 重难点与常考形式
- 重点：算法过程、代码实现、时间复杂度分析、稳定性。
- 难点：优化（提前结束机制）、每趟排序后序列状态的分析。
- 考点：
- 给定一个序列，写出第
k趟排序结束后的结果。 - 计算总的比较次数或交换次数。
- 判断算法的稳定性和空间复杂度。
- 与其它 排序算法（如直接插入、简单选择）的对比。
- 给定一个序列，写出第
2.2.4 排序示意图
排序过程示意图
代码示例
c//冒泡函数 BubbleSort() 的定义 //返回类型是 void //有两个参数，参数 1 是 int arr[] ( 一维整型数组 ) //参数 2 是 int n (整型变量 n) void BubbleSort(int arr[],int n) { // 定义一个整型循环控制变量 i， // 并且初始化为 0 int i = 0; //外层 for 循环 //用于循环 第几趟 //进入循环的条件是 循环控制变量 i < (数组的长度 - 1) for (i = 0; i < (n -1) ; i++) { // 定义一个整型循环控制变量 j， // 并且初始化为 0 int j = 0; //内层 for 循环 //用于循环 第几次比较 //进入循环的条件是 循环控制变量 j < ( 数组的长度 n - 1 - i ( i 是循环的趟数) ) for (j = 0; j < (n -1 - i); j++) { // 定义一个整型变量 tmp， // 并且初始化为 0 int tmp = 0; // 如果 数组的后者的大小 ( < )小于 数组的前者的大小 -- 升序数组实现 if (arr[j + 1] < arr[j]) { // 数组的后者 arr[j + 1] 赋值给 tmp tmp = arr[j + 1]; //数组的前者 arr[j] 赋值给 数组的后者 arr[j + 1] arr[j + 1] = arr[j]; // tmp (起始数组的后者 arr[j + 1]) 赋值给 数组的前者 arr[j] arr[j] = tmp; } } } return 0; }
2.2.5 典型考试例题与解析
【例题1】注1:
对关键字序列 {25, 12, 30, 15, 8} 进行冒泡排序（升序），请写出第三趟排序结束后的结果。
【分析与解答】
- 初始序列： [25, 12, 30, 15, 8]
- 第一趟：目标是将最大值冒泡到最后。
- 25 vs 12 -> 交换 -> [12, 25, 30, 15, 8]
- 25 vs 30 -> 不交换 -> [12, 25, 30, 15, 8]
- 30 vs 15 -> 交换 -> [12, 25, 15, 30, 8]
- 30 vs 8 -> 交换 -> [12, 25, 15, 8, 30]
- 第一趟结果：
[12, 25, 15, 8, 30]
- 第二趟：对前4个元素
[12, 25, 15, 8]进行冒泡。- 12 vs 25 -> 不交换 -> [12, 25, 15, 8]
- 25 vs 15 -> 交换 -> [12, 15, 25, 8]
- 25 vs 8 -> 交换 -> [12, 15, 8, 25]
- 第二趟结果：
[12, 15, 8, 25, 30]
- 第三趟：对前3个元素
[12, 15, 8]进行冒泡。- 12 vs 15 -> 不交换 -> [12, 15, 8]
- 15 vs 8 -> 交换 -> [12, 8, 15]
- 第三趟结果：
[12, 8, 15, 25, 30]
【答案】 第三趟排序结束后的序列为：12, 8, 15, 25, 30
【例题2】注2
对 n 个记录的表进行冒泡排序，在最坏情况下，需要进行 ______ 次比较。
【分析与解答】
- 最坏情况是序列完全逆序。
- 第一趟需要比较
n-1次。 - 第二趟需要比较
n-2次。 - ...
- 最后一趟（第
n-1趟）需要比较1次。 - 总比较次数为：
(n-1) + (n-2) + ... + 1 = n(n-1)/2
【答案】 n(n-1)/2
解释
注1：过程与结果分析例题 注2：比较次数计算2.3 简单选择排序
2.3.1 核心思想 (重点)
简单选择排序的核心思想是，可以概括为：
- 从，每次选择一个的元素。
- 将其（即与未排序序列的第一个元素交换位置）。
- 如此重复，直到所有元素排序完毕。
形象比喻：就像打扑克时，你把所有牌摊开，一张一张选出最小的牌，依次排好。
2.3.2 算法特性 (考点)
时间复杂度：
- 。需要进行 ，。。
- 因此，最好、最坏、平均情况下的。
空间复杂度：O(1)。只用了常数个额外变量（如存储最小值的下标、交换用的临时变量），是原地排序。
稳定性：。这是它的一个重要考点。因为选择最小元素后，需要与未排序区的第一个元素进行交换，这个交换操作可能会破坏稳定性。
不稳定性举例：序列
[5, 5, 2]。 第一趟：找到最小值2，与第一个5交换。得到序列[2, 5, 5]。 此时，原本在前面的5被交换到了后面，与另一个5的相对顺序发生了变化。所以是不稳定的。
2.3.3 重难点与常考形式
- 重点：算法过程、时间复杂度分析、不稳定性的原因。
- 难点：与冒泡排序的区分（交换次数更少）、不稳定性的理解。
- 考点：
- 给定一个序列，写出第
k趟排序结束后的结果。 - 计算总的比较次数。
- 判断算法的稳定性，并解释原因。
- 与其它 排序算法（如直接插入、冒泡）的对比。
- 给定一个序列，写出第
2.3.4 排序示意图
示意图
代码
cvoid select_sort(int arr[]){ int temp; //中间变量 for (int i = 0; i < N-1; i++) { //外层循环 for (int j = i+1; j < N; j++) { //内层循环 if (arr[i] > arr[j]){ //外循环里的元素和内循环里的每一个元素比较 //交换位置 temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } print_arr(arr); } printf("\n"); }
2.3.5 典型考试例题与解析
【例题1】注1 采用简单选择排序对序列 {50, 10, 90, 30, 70} 进行升序排序，请写出第二趟排序结束后的结果。
【分析与解答】 我们一步步模拟过程：
- 初始序列： [50, 10, 90, 30, 70]
- 第一趟 (i=0)：
- 在 [50, 10, 90, 30, 70] 中找最小值，是
10（下标为1）。 - 交换
arr[0]和arr[1]-> [10, 50, 90, 30, 70] - 第一趟结果：
[10, 50, 90, 30, 70]
- 在 [50, 10, 90, 30, 70] 中找最小值，是
- 第二趟 (i=1)：
- 在子序列 [50, 90, 30, 70] 中找最小值，是
30（下标为3）。 - 交换
arr[1]和arr[3]-> [10, 30, 90, 50, 70] - 第二趟结果：
[10, 30, 90, 50, 70]
- 在子序列 [50, 90, 30, 70] 中找最小值，是
【答案】 第二趟排序结束后的序列为：10, 30, 90, 50, 70
【例题2】注2 下列关于简单选择排序的叙述中，错误的是 ______。
A. 它的时间复杂度为 O(n²)
B. 它是一种不稳定的排序方法
C. 在排序过程中，元素移动的次数最多为 n-1 次
D. 序列越接近有序，它的时间效率就越高
【分析与解答】
- A 正确：简单选择排序的时间复杂度恒为 O(n²)。
- B 正确：由于存在交换操作，可能会破坏稳定性。
- C 正确：每趟排序最多只进行一次交换（移动3次元素），共
n-1趟，所以元素移动（交换）次数最多为n-1次。这与冒泡排序（最坏需要 O(n²) 次移动）相比是一个优势。 - D 错误：这是直接插入排序的特点。简单选择排序的比较次数与序列初始状态无关，无论序列是否有序，它都需要进行
n(n-1)/2次比较。因此它的时间效率并不因序列有序而提高。
【答案】 D
解释
注1：过程与结果分析例题 注2：概念辨析（稳定性与复杂度）2.4 希尔排序
2.4.1 核心思想 (重点)
希尔排序的核心思想是，也称为。
- 基本思想：将整个待排序序列，对这些。
- 如何分组：不是简单地逐段分割，而是。，
gap为多少就将当前数组分为多少组。 - 逐步缩小增量：随着增量
gap逐渐减小，子序列中的记录越来越多且越来越有序。当，被当作一个子序列进行，此时序列已基本有序，插入排序效率很高。
为什么有效？ 直接插入排序在元素基本有序时效率很高（接近 ），并且元素较少时效率也不错。希尔排序通过前期的大增量分组，使元素能够，快速远离其最终位置，从而。
2.4.2 算法特性 (考点)
- 时间复杂度：
- 时间复杂度依赖于所选取的，分析非常复杂。
- 使用希尔建议的增量（
n/2, n/4, ..., 1）时，最坏情况时间复杂度为 一般认为时间复杂度为 。 - 考试中通常只需记住其。
- 空间复杂度：O(1)。只用了常数个额外变量，是原地排序。
- 稳定性：。因为相同的关键字可能会被划分到不同的子序列中，并在各自的子序列中移动，从而可能改变它们的相对次序。
2.4.3 重难点与常考形式
- 重点：算法过程（分组、组内插入排序）、它是。
- 难点：、。
- 考点：
- 给定一个序列和一个增量序列，要求写出某一趟排序（某个特定gap下）后的结果。这是最高频的考法！
- 判断算法的。
- 询问其与直接插入排序的关系（它是其改进版）。
2.4.4 排序示意图
图片示例：
代码示例：
c#include <stdio.h> #define N 8 //设定待排序序列中的元素个数 //list[N] 为存储待排序序列的数组 void shell_sort(int list[N]) { int temp, i, j; //初始化间隔数为 1 int interval = 1; //计算最大间隔 while (interval < N / 3) { interval = interval * 3 + 1; } //根据间隔数，不断划分序列，并对各子序列排序 while (interval > 0) { //对各个子序列做直接插入排序 for (i = interval; i < N; i++) { temp = list[i]; j = i; while (j > interval - 1 && list[j - interval] >= temp) { list[j] = list[j - interval]; j -= interval; } if(j != i){ list[j] = temp; } } //计算新的间隔数，继续划分序列 interval = (interval - 1) / 3; } }
2.4.5 典型考试例题与解析
例题1：过程与结果（最常考！）
【例题】 设待排序序列为 {50, 26, 38, 80, 70, 90, 8, 30, 40, 20}，取增量序列 gap = {5, 3, 1}，请写出第一趟（gap=5）排序后的结果。
【分析与解答】第一步：分组 增量 gap=5，意味着将序列中相距为5的元素分为一组。
- 组1：下标为0, 5 -> (50, 90)
- 组2：下标为1, 6 -> (26, 8)
- 组3：下标为2, 7 -> (38, 30)
- 组4：下标为3, 8 -> (80, 40)
- 组5：下标为4, 9 -> (70, 20)
第二步：组内插入排序 分别对以上5个子序列进行直接插入排序：
- 组1 (50, 90)：已有序 -> (50, 90)
- 组2 (26, 8)：逆序，交换 -> (8, 26)
- 组3 (38, 30)：逆序，交换 -> (30, 38)
- 组4 (80, 40)：逆序，交换 -> (40, 80)
- 组5 (70, 20)：逆序，交换 -> (20, 70)
第三步：重组序列 将排序后的各组元素，按原来的分组顺序放回原序列。
- 位置0和5来自组1：50, 90
- 位置1和6来自组2：8, 26
- 位置2和7来自组3：30, 38
- 位置3和8来自组4：40, 80
- 位置4和9来自组5：20, 70
【答案】 第一趟（gap=5）排序后的结果为： 50, 8, 30, 40, 20, 90, 26, 38, 80, 70
关键提示
最终序列是各组排序后的结果，并。90仍然在位置5，26仍然在位置6，这是初学者最容易出错的地方。
例题2：概念辨析
【例题】 下列关于希尔排序的叙述中，正确的是 ______。
A. 希尔排序是稳定的排序算法
B. 希尔排序的空间复杂度为O(n)
C. 希尔排序是直接插入排序的一种高效改进版本
D. 希尔排序的时间复杂度为O(nlog₂n)
【分析与解答】
- A 错误：希尔排序是不稳定的。
- B 错误：希尔排序的空间复杂度是O(1)。
- C 正确：这正是希尔排序的设计初衷和本质。
- D 错误：希尔排序的时间复杂度依赖于增量序列，通常认为在O(nlog₂n)和O(n²)之间，不等于O(nlog₂n)。
【答案】 C
2.5 快速排序
2.5.1 核心思想 (重点)
快速排序采用了的思想，其核心流程可以概括为以下三步：
分解（Partition）：
- 从序列中，也称为枢轴。
- 通过一趟排序，将所有的元素放到它的，所有的元素放到它的。
- 操作结束后，该基准元素就位于了序列的最终正确位置上。
递归（Recurse）：
- 递归地（Recursively）对基准左边的子序列和右边的子序列进行。
合并（Combine）：
- 因为每一步都将基准放到了最终位置，所以递归完成后，整个序列自然就是有序的。这个步骤不需要任何操作。
精髓：每一趟排序都让一个元素（基准）。
2.5.2 算法特性 (高频考点)
- 时间复杂度：
- 最好情况: ：每次划分都能将序列几乎等分成两部分。递归树的深度为 ，每层需要 时间处理。
- 平均情况：：数学期望值，证明过程复杂，考试只需记住结论。
- 最坏情况：：每次划分产生的两个子序列一个为空，另一个为 个元素。当，如果选择，就会导致最坏情况。
- 空间复杂度：
- 最好：：递归树的深度，即递归。
- 最坏：：需要进行 次递归调用，栈深度为 。
- 稳定性：：。在分区过程中，元素的交换是跳跃式的，会破坏稳定性。例如：序列
[5, 3, 5, 2]，以第一个5为基准，后面的5会被交换到前面去。
2.5.3 重难点与常考形式
- 重点：、Partition过程、时间复杂度分析、稳定性。
- 难点：、递归过程的理解、时间复杂度的分析。
- 考点：
- 给定一个序列，写出以某个特定元素为基准进行第一趟排序后的结果。
- 分析快速排序的最好/最坏情况及其发生条件。
- 判断算法的稳定性和空间复杂度。
- 与其他 排序算法（如归并、堆排）的对比。
2.5.4 算法示例
Hoare 算法示例
挖坑填数法示例
Hoare 算法代码示例
cppvoid Swap(int* a, int* b)//交换函数 { int tmp = *a; *a = *b; *b = tmp; } // 快速排序hoare版本 void Quicksort1(int* a, int left, int right) { if (left >= right)//只有一个元素或不存在，停止递归 return ; int keyi = left; int begin = left, end = right; while (begin < end)//begin与end未相遇时，继续循环 { while (begin < end && a[end] >= a[keyi])//end先移动，找到小于keyi位置的值停止 end--; while (begin < end && a[begin] <= a[keyi])//begin再移动，找到大于keyi位置的值停止 begin++; Swap(&a[begin], &a[end]); } Swap(&a[keyi], &a[begin]);//出循环后，begin与end相遇，交换此位置与keyi位置的值 keyi = begin;//更新keyi的位置 //[left][keyi-1]keyi[keyi+1][right] 左右区间划分 Quicksort1(a, left, keyi - 1);//左区间递归 Quicksort1(a, keyi + 1, right);//右区间递归 }挖坑填数法代码示例
cpp// 单趟快排（挖坑法） int Partition(int* array, int begin, int end) { int key = array[begin]; // 基准值 while (begin < end) { // 从右向左找小于基准值的元素 while (begin < end && array[end] >= key) { end--; } array[begin] = array[end]; // 填入左侧坑位 // 从左向右找大于基准值的元素 while (begin < end && array[begin] <= key) { begin++; } array[end] = array[begin]; // 填入右侧坑位 } array[begin] = key; // 将基准值放入最终位置 return begin; // 返回基准值的位置 } // 快速排序递归函数 void QuickSort(int* array, int begin, int end) { if (begin >= end) { return; // 递归终止条件 } int pivot = Partition(array, begin, end); // 单趟快排 QuickSort(array, begin, pivot - 1); // 递归左子数组 QuickSort(array, pivot + 1, end); // 递归右子数组 }
典型考试例题与解析
例题1：过程与结果（必考题）
【例题】 对关键字序列 (25, 84, 21, 47, 15, 27, 68, 35, 20) 进行快速排序，以第一个元素25为基准，请写出第一趟排序结束后的结果。
【分析与解答】 按照上述Partition过程进行模拟：
- 初始：
[25, 84, 21, 47, 15, 27, 68, 35, 20],pivot=25,i=0,j=8。 - 从右向左找 <25的数：
j=8,20<25，将20填入arr[0]，i++。 序列：[20, 84, 21, 47, 15, 27, 68, 35, 坑] - 从左向右找 >25的数：
i=1,84>25，将84填入arr[8]的坑，j--。 序列：[20, 坑, 21, 47, 15, 27, 68, 35, 84] - 从右向左找 <25的数：
j=7,35>25；j=6,68>25；j=5,27>25；j=4,15<25，将15填入arr[1]的坑，i++。 序列：[20, 15, 21, 47, 坑, 27, 68, 35, 84] - 从左向右找 >25的数：
i=2,21<25；i=3,47>25，将47填入arr[4]的坑，j--。 序列：[20, 15, 21, 坑, 47, 27, 68, 35, 84] - 从右向左找 <25的数：
j=3，此时i=3,j=3，循环结束。 - 将
pivot=25填入arr[3]。
【答案】 第一趟排序结束后的结果为： [20, 15, 21, 25, 47, 27, 68, 35, 84]
例题2：时间复杂度分析（概念题）
【例题】 在快速排序中，最坏情况下的时间复杂度发生在（ ）时。
A. 元素完全有序
B. 元素完全无序
C. 左子序列元素个数和右子序列相等
D. 基准元素是最大元素或最小元素
【分析与解答】
- 最坏情况是每次划分都极不均匀，即一个子序列为空，另一个包含 n-1 个元素。
- 这发生在每次选取的基准都是当前序列中的最大值或最小值时。
- 如果序列本身已经有序（升序或降序），并且我们选择第一个或最后一个元素作为基准，那么每次选取的基准恰好就是最小值或最大值，这就导致了最坏情况。
- 选项A和D描述的是同一现象的两种表述方式，但A是D的典型例子。而B和C都是较好或平均的情况。
【答案】 A (同时，D也是正确的描述，但单选题中最标准的答案是A，因为它是最常见的实例)
2.6 堆排序
2.6.1 核心思想 (重点)
堆排序是一种，它的核心是利用这种数据结构来进行高效的选择。
- 什么是堆？
- 堆是一种。
- 它满足以下性质之一：
- 大顶堆 (Max Heap)：每个结点的值都其左右孩子结点的值。
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] - 小顶堆 (Min Heap)：每个结点的值都其左右孩子结点的值。
arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] - 核心思想：将待排序序列构造成一个大顶堆。此时，整个序列的 就是堆顶的。将其与堆数组的，此时末尾就是最大值。然后将剩余的
n-1个序列重新调整成大顶堆，如此反复执行，便能得到一个有序序列。
- 大顶堆 (Max Heap)：每个结点的值都其左右孩子结点的值。
精髓：堆排序分为两个核心步骤：1. 和 2. 。
2.6.2 算法特性 (高频考点)
- 时间复杂度：
- 建堆过程：时间复杂度为 。这是一个非常重要的结论，虽然看起来需要调整很多次，但通过数学推导可以证明是线性的。
- 调整过程：每次从堆顶取出最大值后调整堆需要 的时间，总共需要
n-1次调整。 - 总复杂度：。最好、最坏、平均情况下。
- 空间复杂度：。只用了常数个额外变量（用于交换），是。
- 稳定性：。因为在调整堆的过程中，父子节点之间的交换是跳跃式的。例如：序列
[5, 5, 4]，构建大顶堆后交换堆顶和末尾，相对顺序会被打乱。
2.6.3 重难点与常考形式
- 重点：堆的定义、建堆过程、调整过程、时间复杂度、不稳定性。
- 难点：将线性序列在脑中映射成完全二叉树、理解调整堆的递归（或循环）过程、理解建堆复杂度为 。
- 考点：
- （最高频） 给定一个序列，写出其初始大顶堆（或小顶堆）。
- 写出第一趟或第 趟堆排序后的序列状态（即交换并调整k次后）。
- 计算堆排序的时间复杂度和空间复杂度。
- 判断算法的稳定性。
2.6.4 算法示例
- 示例图
- 示例代码c
#include <stdio.h> #include <stdlib.h> void swap(int* a, int* b) { int temp = *b; *b = *a; *a = temp; } void max_heapify(int arr[], int start, int end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son <= end) { //若子节点指标在范围内才做比较 if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的 son++; if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数 return; else { //否则交换父子内容再继续子节点和孙节点比较 swap(&arr[dad], &arr[son]); dad = son; son = dad * 2 + 1; } } } void heap_sort(int arr[], int len) { int i; //初始化，i从最后一个父节点开始调整 for (i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); //先将第一个元素和已排好元素前一位做交换，再从新调整，直到排序完毕 for (i = len - 1; i > 0; i--) { swap(&arr[0], &arr[i]); max_heapify(arr, 0, i - 1); } }
2.6.5典型考试例题与解析
例题1：构建初始堆（最常考！）
【例题】 对于关键字序列 {15, 20, 8, 10, 16, 7, 12, 13, 5}，将其构建成一个大顶堆，则初始大顶堆是 ______。
【分析与解答】第一步：将序列看成完全二叉树
15
/ \
20 8
/ \ / \
10 16 7 12
/ \
13 5第二步：找到最后一个非叶子节点 序列长度 n=9，最后一个非叶子节点下标 = n/2 - 1 = 4 - 1 = 3 (即值为10的节点)。
第三步：从后往前依次调整
- 调整节点3 (10)：比较
10和其孩子13, 5，13最大，交换10和13。 序列变为：[15, 20, 8, 13, 16, 7, 12, 10, 5] - 调整节点2 (8)：比较
8和其孩子7, 12，12最大，交换8和12。 序列变为：[15, 20, 12, 13, 16, 7, 8, 10, 5] - 调整节点1 (20)：比较
20和其孩子13, 16，20最大，无需调整。 - 调整节点0 (15)：比较
15和其孩子20, 12，20最大，交换15和20。 序列变为：[20, 15, 12, 13, 16, 7, 8, 10, 5]- 由于
15被交换下去，需要继续调整以15为根的子树。 - 比较
15和其新孩子13, 16，16最大，交换15和16。 序列变为：[20, 16, 12, 13, 15, 7, 8, 10, 5] 15被交换到叶子节点，调整结束。
- 由于
【答案】 初始大顶堆为：20, 16, 12, 13, 15, 7, 8, 10, 5
例题2：概念辨析
【例题】 下列关于堆排序的叙述中，错误的是 ______。
A. 堆排序的时间复杂度为
B. 堆排序是稳定的排序算法
C. 堆排序的空间复杂度为
D. 构建初始堆的过程的时间复杂度为
【分析与解答】
- A 正确：堆排序的最好、最坏、平均时间复杂度都是 。
- B 错误：堆排序在调整堆时，父节点和子节点的交换是跳跃性的，会破坏稳定性，是排序。
- C 正确：堆排序是原地排序。
- D 正确：构建初始堆的复杂度是线性的 。
【答案】 B
2.7 归并排序
2.7.1 核心思想 (重点)
归并排序的核心思想是，其过程可以概括为以下三步：
分解（Divide）：
- 将当前待排序的序列递归地的子序列，直到（此时自然有序）。
解决（Conquer）：
- 递归地对。（实际上，分解到只有一个元素时，“解决”步骤就已经自动完成了）
合并（Combine）：
- 这是归并排序的核心操作。将两个已经。
- 进行，直到最终合并成一个完整的有序序列。
精髓：关键在于如何高效地将两个有序子序列合并为一个有序序列。
2.7.2 算法特性 (高频考点)
- 时间复杂度：
- 。无论序列的初始状态如何，归并排序都需要进行 层分解，每层都需要 的时间进行合并操作。
- 空间复杂度：。这是归并排序的主要缺点。合并两个有序子序列时需要一個大小為 的来存储中间结果。
- 稳定性：。这是它的重要优点。在合并过程中，当两个有序子序列遇到相等元素时，我们可以规定优先将前一个子序列的元素放入临时数组，这样就可以保证它们的相对顺序不变。
2.7.3 重难点与常考形式
- 重点：、合并过程、时间复杂度分析、稳定性、空间复杂度。
- 难点：理解递归过程、手动模拟每一趟归并后的结果。
- 考点：
- （最高频） 给定一个序列，写出其2路归并排序过程中某一趟排序（或全部趟数）后的结果。
- 分析归并排序的时间复杂度和空间复杂度。
- 判断算法的稳定性，并解释原因。
- 与其它 排序算法（如快速排序、堆排序）的对比。
2.7.4 归并排序示例
- 静态图示
- 动态图示
- 代码示例c
void merge_sort(int arr[], int len) { int *a = arr; int *b = (int *) malloc(len * sizeof(int)); int seg, start; for (seg = 1; seg < len; seg += seg) { for (start = 0; start < len; start += seg * 2) { int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high; while (start1 < end1 && start2 < end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) b[k++] = a[start1++]; while (start2 < end2) b[k++] = a[start2++]; } int *temp = a; a = b; b = temp; } if (a != arr) { int i; for (i = 0; i < len; i++) b[i] = a[i]; b = a; } free(b); }
2.7.5 典型考试例题与解析
例题1：过程与结果（最常考！）
【例题】 采用2路归并排序对序列 {25, 84, 21, 47, 15, 27, 68, 35, 20} 进行排序，请写出第一趟归并结束后的结果。
【分析与解答】 “第一趟归并”通常指的是将序列中相邻的、长度为1的子序列两两归并，得到若干个长度为2的有序子序列。
- 初始序列：
[25], [84], [21], [47], [15], [27], [68], [35], [20] - 第一趟归并（相邻两个一组）：
- 归并
[25]和[84]->[25, 84] - 归并
[21]和[47]->[21, 47] - 归并
[15]和[27]->[15, 27] - 归并
[68]和[35]->[35, 68](注意：35<68，所以合并后是[35,68]) [20]单个元素，本轮轮空，直接放入结果。
- 归并
- 重组：将上述归并结果按顺序组合起来。
【答案】 第一趟归并结束后的结果为： [25, 84, 21, 47, 15, 27, 35, 68, 20]
关键提示💡
考试时要看清题目问的是还是。
第二趟归并会将长度为2的子序列两两归并成长度为4的子序列（[25,84]和[21,47]合并，[15,27]和[35,68]合并，[20]轮空），以此类推。
例题2：概念辨析
【例题】 下列关于归并排序的叙述中，正确的是 ______。
A. 归并排序不需要额外的存储空间
B. 归并排序的时间复杂度在最坏情况下是
C. 归并排序是一种稳定的排序算法
D. 2路归并排序的核心操作是交换
【分析与解答】
- A 错误：归并排序需要 的额外空间用于合并操作，这是它的主要缺点。
- B 错误：归并排序的最好、最坏、平均时间复杂度都是 。
- C 正确：在合并两个有序子序列时，如果遇到相等元素，可以优先取前一子序列的元素，从而保证稳定性。
- D 错误：其核心操作是，而非交换。
【答案】 C
2.8 基数排序 (Radix Sort)
2.8.1 核心思想 (重点 & 难点)
基数排序的核心思想是： 和 。
- 不基于比较：。
- 基于关键字位：它将整个关键字 拆分成多个（例如：个位、十位、百位），并按照的顺序，进行排序。
- 稳定排序：每一趟的排序算法都必须是的，因为每一趟排序的结果都依赖于上一趟排序的结果。
两种方法：
- 最低位优先 (LSD - Least Significant Digit First)：从关键字的（如个位），再到次低位（十位），直至最高位。这是最常用的方法。
- 最高位优先 (MSD - Most Significant Digit First)：从关键字的。这是一个分治递归的过程，比较复杂，考试中极少涉及。
精髓：LSD基数排序的过程可以看作是先按排序，再按排序，再按排序的多次过程。
2.8.2 算法特性 (高频考点)
- 时间复杂度：O(d(n + r))
d：关键字的位数（例如：最大数为100，则d=3）。n：待排序元素的个数。r：关键字位的基数（Radix）。对于十进制数，r=10（即0-9共10个桶）。- 总共进行
d趟分配和收集，每趟分配需要O(n)时间，收集需要O(r)时间。
- 空间复杂度：。需要额外的空间来存放 个队列（桶），以及存放中间结果。 是基数的大小。
- 稳定性：。这是实现基数排序的前提，因为每一趟的排序都必须是稳定的，才能保证之前排序的有效性。
2.8.3 重难点与常考形式
- 重点：LSD过程、分配与收集、时间复杂度表示、稳定性、适用场景。
- 难点：理解 "基于位" 和 "稳定排序" 的重要性、空间复杂度的分析。
- 考点：
- （最高频） 给定一个序列，写出其基于LSD的基数排序全过程或某一趟后的结果。
- 计算基数排序的时间复杂度和空间复杂度。
- 判断算法的稳定性。
- 询问其适用场景（例如：适合基数排序的关键字类型）。
2.8.4 基数示例
- 排序图示
- 代码示例c
#include <stdio.h> #include <stdlib.h> // 获取数组中的最大值 int getMax(int arr[], int n) { int max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } // 计数排序，作为基数排序的一个子过程 void countSort(int arr[], int n, int exp) { int output[n]; int i, count[10] = {0}; // 存储计数 for (i = 0; i < n; i++) { count[(arr[i] / exp) % 10]++; } // 更改count[i]，现在包含实际位置信息 for (i = 1; i < 10; i++) { count[i] += count[i - 1]; } // 构建输出数组 for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // 将输出数组的内容复制到arr[] for (i = 0; i < n; i++) { arr[i] = output[i]; } } // 主排序函数 void radixsort(int arr[], int n) { int m = getMax(arr, n); // 从最低位开始，对每一位进行排序 for (int exp = 1; m / exp > 0; exp *= 10) { countSort(arr, n, exp); } } // 测试基数排序 int main() { int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; int n = sizeof(arr) / sizeof(arr[0]); radixsort(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
解释💡
- 在上述代码中，
getMax函数用于找到数组中的最大值，这是为了确定排序过程中需要的最大位数。 countSort函数是基数排序中的一个子过程，它按照当前位（个位、十位、百位等）对数组进行排序。radixsort函数通过从最低位开始，逐步对每一位进行排序，最终得到一个有序数组
2.8.5 典型考试例题与解析
例题1：过程与结果（必考题！）
【例题】 对一组关键字 {209, 386, 766, 185, 247, 606, 230, 830, 539} 进行基数排序，请写出按最低位优先(LSD)排序的第一趟和第二趟结束后的关键字序列。
【分析与解答】
第一趟（按个位分配和收集）：
- 分配：
- 个位为9：209, 539
- 个位为6：386, 766, 606
- 个位为5：185
- 个位为7：247
- 个位为0：230, 830
- 收集（按桶号0->9顺序取出）：
- 230, 830, (0号桶)
- (空1,2,3,4号桶)
- 185, (5号桶)
- 386, 766, 606, (6号桶)
- 247, (7号桶)
- (空8号桶)
- 209, 539 (9号桶)
- 第一趟结果：
230, 830, 185, 386, 766, 606, 247, 209, 539
- 分配：
第二趟（按十位分配和收集）：
- 基于第一趟结果
[230, 830, 185, 386, 766, 606, 247, 209, 539]进行。 - 分配（看十位）：
- 十位为3：230, 830
- 十位为8：185, 386, 766
- 十位为0：606, 209
- 十位为4：247
- 十位为3：539
- 收集（按桶号0->9顺序取出）：
- 606, 209, (0号桶)
- (空1,2号桶)
- 230, 830, 539, (3号桶)
- 247, (4号桶)
- (空5,6,7号桶)
- 185, 386, 766, (8号桶)
- (空9号桶)
- 第二趟结果：
606, 209, 230, 830, 539, 247, 185, 386, 766
- 基于第一趟结果
【答案】
- 第一趟结束后：230, 834, 185, 386, 768, 606, 247, 209, 539
- 第二趟结束后：606, 209, 230, 834, 539, 247, 185, 386, 768
例题2：概念辨析
【例题】 基数排序是一种稳定的排序算法，它适用于（ ）。
A. 元素个数很多，但关键字位数较少的情况
B. 元素个数很少，但关键字位数较多的情况
C. 元素个数和关键字位数都很多的情况
D. 任何情况
【分析与解答】
- 基数排序的时间复杂度是 。
- 如果关键字位数 很大（例如：对很长的字符串排序），而元素个数 较小，那么 将成为主导因素，效率可能不如 的算法。
- 反之，如果关键字位数 较小（例如：给10万人的年龄排序，d=2或3），即使元素个数 很大，其时间复杂度也接近 ，效率会非常高。
- 因此，基数排序最适合。
【答案】 A
2.9 小结
| 排序算法 | 核心思想 (重点) | 时间复杂度 (重点&难点) | 空间复杂度 (重点) | 稳定性 (重点&考点) | 常考要点 (考点) |
|---|---|---|---|---|---|
| 直接插入排序 | 将待排记录逐个插入到已排好序的有序序列中 | 最好: 平均/最坏: | 稳定 | 过程理解、比较次数、移动次数 | |
| 冒泡排序 | 两两比较，逆序则交换 | 最好: 平均/最坏: | 稳定 | 过程理解、趟数、比较次数 | |
| 简单选择排序 | 每趟从无序区选一个最小/大的放到有序区末尾 | 不稳定 | 过程理解、比较次数 | ||
| 希尔排序 | 分组插入排序，增量由大到小 | 依赖于增量序列，约 | 不稳定 | 概念、是不稳定的插入排序 | |
| 快速排序 | 分治法 。选取枢轴，将序列分成两部分 | 最好/平均: 最坏: | 平均: 最坏: | 不稳定 | 递归过程、枢轴选择、时间复杂度分析、趟排序后的结果 |
| 堆排序 | 将序列构建成大顶堆（升序）或小顶堆，交换堆顶和末尾元素，调整剩余为堆 | 不稳定 | 建堆过程、调整过程、输出序列 | ||
| 归并排序 | 分治法 。将序列递归地分成子序列，然后合并有序子序列 | 稳定 | 合并过程、空间复杂度 | ||
| 基数排序 | 按 关键字位 分配收集（个位->十位->百位） | (d:位数，r:基数) | 稳定 | 过程理解、适用场景（关键字可拆分） |
效率从高到低（增长率从慢到快）的完整关系链： 。
选取规则：在选取排序方法时需要考虑的因素有待排序的记录个数 、记录本身的大小、关键字的分布情况、对排序稳定性的要求、语言工具的条件和辅助空间的大小。
- 依据这些因素,可以得到以下几点结论。
- 若待排序的记录,可采用。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当时 ,用。
- 若待排序记录按关键字,宜。
- 当 很大且关键字的时,采用较好。
- 若 较大,则应,例如快速排序、堆排序或归并排序