【408考研知识点全面讲解计算机学科专业基础综合（408）】——数据结构之排序

一、排序的基本概念

在数据结构中，排序是将一组无序的数据按照某个关键字（可以是数据本身，也可以是数据的某个属性）重新排列成有序序列的过程。有序序列可以是升序（从小到大），也可以是降序（从大到小），在默认情况下，我们通常以升序为例进行讲解。

排序在实际生活和计算机应用中有着广泛的应用。比如在学校里，成绩单需要按照成绩排序；在电商平台上，商品需要按照价格、销量等排序供用户选择。在考研 408 的考试中，排序是数据结构的重要知识点，几乎每年都会涉及相关考题，所以掌握好排序算法是非常必要的。

二、插入排序

（一）直接插入排序

基本思想
直接插入排序就像我们平时整理手里的扑克牌。比如你手里已经有几张排好序的牌，现在又摸到一张新牌，你会把它和手里的牌从后往前一张张比较，找到合适的位置插进去，让手里的牌一直保持有序。

具体步骤

初始时，将第一个元素视为一个有序序列。从第二个元素开始，依次将每个元素插入到前面已经排好序的序列中合适的位置。

对于要插入的元素，与有序序列中的元素从后往前比较，如果有序序列中的元素大于要插入的元素，则将该元素后移一位；直到找到一个元素小于或等于要插入的元素，将其插入到该元素的后面。

实现代码（C 语言）
void InsertSort(int A[], int n) {int i, j, temp;for (i = 1; i < n; i++) {  // 从第二个元素开始temp = A[i];  // 保存要插入的元素for (j = i - 1; j >= 0 && A[j] > temp; j--) {  // 从后往前比较A[j + 1] = A[j];  // 元素后移}A[j + 1] = temp;  // 插入元素}
}

时间复杂度
最好情况：当待排序序列已经有序时，每插入一个元素只需要比较一次，不需要移动元素。此时时间复杂度为 O (n)。
最坏情况：当待排序序列逆序时，每个元素都需要与前面所有元素比较并移动。此时时间复杂度为 O (n²)。
平均情况：时间复杂度为 O (n²)。

空间复杂度
只需要一个临时变量来保存要插入的元素，所以空间复杂度为 O (1)。
算法特点
稳定性：稳定，因为当遇到相等元素时，会将待插入元素插入到相等元素的后面，不会改变它们的相对顺序。
适用性：适用于数据量较小的情况，因为当数据量较大时，时间复杂度较高。

（二）折半插入排序

基本思想

折半插入排序是对直接插入排序的改进。在直接插入排序中，寻找插入位置时是通过顺序比较的方式，而折半插入排序则是利用折半查找的方法来寻找插入位置，这样可以减少比较的次数。

具体步骤
初始时，将第一个元素视为一个有序序列。
从第二个元素开始，对于每个要插入的元素，在前面的有序序列中使用折半查找找到合适的插入位置。
将插入位置之后的元素依次后移，然后将该元素插入到找到的位置。

实现代码（C 语言）
void BinaryInsertSort(int A[], int n) {int i, j, low, high, mid, temp;for (i = 1; i < n; i++) {temp = A[i];low = 0;high = i - 1;// 折半查找插入位置while (low <= high) {mid = (low + high) / 2;if (A[mid] > temp) {high = mid - 1;} else {low = mid + 1;}}// 元素后移for (j = i - 1; j >= high + 1; j--) {A[j + 1] = A[j];}A[high + 1] = temp;  // 插入元素}
}

时间复杂度
折半查找的时间复杂度为 O (log n)，但元素的移动次数并没有减少，仍然和直接插入排序相同。

最好情况：O (n log n)（待排序序列有序时，移动次数少）。
最坏情况和平均情况：O (n²)。

空间复杂度
同样只需要一个临时变量，空间复杂度为 O (1)。
算法特点
稳定性：稳定，原因和直接插入排序相同。
与直接插入排序比较：减少了比较次数，但移动次数不变，所以在数据量较大时，效率比直接插入排序略高，但仍然适用于数据量较小的情况。

（三）希尔排序

基本思想
希尔排序又称缩小增量排序，它是基于直接插入排序的一种改进。其基本思想是将待排序序列按照一定的增量分割成若干个子序列，对每个子序列进行直接插入排序，然后逐渐减小增量，重复上述过程，直到增量为 1，此时对整个序列进行一次直接插入排序，排序完成。

具体步骤

选择一个增量序列，通常取 d1 = n/2，d2 = d1/2，…，dk = 1（n 为序列长度）。

对于每个增量 di，将序列分割成 di 个子序列，每个子序列由下标相差 di 的元素组成。
对每个子序列进行直接插入排序。
当增量减为 1 时，整个序列成为一个子序列，对其进行直接插入排序，完成排序。

实现代码（C 语言）
void ShellSort(int A[], int n) {int i, j, d, temp;for (d = n / 2; d >= 1; d = d / 2) {  // 增量变化for (i = d; i < n; i++) {temp = A[i];for (j = i - d; j >= 0 && A[j] > temp; j -= d) {A[j + d] = A[j];  // 元素后移}A[j + d] = temp;  // 插入元素}}
}

时间复杂度
希尔排序的时间复杂度与增量序列的选择有关，目前还没有一个精确的数学表达式。在最坏情况下，时间复杂度为 O (n²)，但在平均情况下，性能优于直接插入排序，通常认为其时间复杂度为 O (n^1.3)。
空间复杂度
空间复杂度为 O (1)，只需要一个临时变量。

算法特点
稳定性：不稳定，因为在分割子序列时，可能会将相等元素分到不同的子序列中，从而改变它们的相对顺序。
适用性：适用于数据量较大的情况，比直接插入排序效率高。

三、交换排序

（一）冒泡排序

基本思想
冒泡排序的基本思想是重复地走访待排序序列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。走访序列的工作会重复地进行直到没有相邻元素需要交换，也就是说该序列已经排序完成。

具体步骤
从序列的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。
经过一轮比较后，最大的元素会 “浮” 到序列的末尾。

排除已经 “浮” 到末尾的元素，对剩下的元素重复上述过程，直到所有元素都排序完成。

实现代码（C 语言）
void BubbleSort(int A[], int n) {int i, j, temp, flag;for (i = 0; i < n - 1; i++) {flag = 0;  // 标记是否发生交换for (j = 0; j < n - 1 - i; j++) {if (A[j] > A[j + 1]) {temp = A[j];A[j] = A[j + 1];A[j + 1] = temp;flag = 1;  // 发生交换，标记为1}}if (flag == 0) {  // 没有发生交换，说明序列已经有序，提前退出break;}}
}

时间复杂度
最好情况：当待排序序列已经有序时，只需要进行一轮比较，没有元素交换，时间复杂度为 O (n)。
最坏情况：当待排序序列逆序时，需要进行 n-1 轮比较，每轮比较 n-i-1 次（i 为轮次），时间复杂度为 O (n²)。
平均情况：时间复杂度为 O (n²)。

空间复杂度
空间复杂度为 O (1)，只需要一个临时变量用于交换元素。
算法特点
稳定性：稳定，因为当两个相邻元素相等时，不会进行交换，它们的相对顺序保持不变。
适用性：适用于数据量较小的情况，实现简单，但效率不高。

（二）快速排序

基本思想
快速排序是一种分治法的排序算法。其基本思想是选择一个元素作为基准（通常选择第一个元素或最后一个元素），通过一趟排序将待排序序列分割成两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大，然后分别对这两部分重复上述过程，直到整个序列有序。

具体步骤
选择序列中的一个元素作为基准（pivot）。

分区（partition）：将序列中比基准小的元素移到基准前面，比基准大的元素移到基准后面，基准元素放在中间位置。
递归地对基准前面的子序列和基准后面的子序列进行快速排序。

实现代码（C 语言）
// 分区函数
int Partition(int A[], int low, int high) {int 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;  // 返回基准元素的位置
}// 快速排序函数
void QuickSort(int A[], int low, int high) {if (low < high) {int pivotpos = Partition(A, low, high);  // 分区QuickSort(A, low, pivotpos - 1);  // 递归排序左子序列QuickSort(A, pivotpos + 1, high);  // 递归排序右子序列}
}

时间复杂度
最好情况：每次分区都将序列分成大小大致相等的两部分，此时时间复杂度为 O (n log n)。
最坏情况：当待排序序列已经有序或逆序时，每次分区只能得到一个比上一次少一个元素的子序列，此时时间复杂度为 O (n²)。
平均情况：时间复杂度为 O (n log n)。

空间复杂度
快速排序的空间复杂度主要取决于递归调用的栈空间。在最好情况下，递归深度为 log n，空间复杂度为 O (log n)；在最坏情况下，递归深度为 n，空间复杂度为 O (n)；平均情况下，空间复杂度为 O (log n)。

算法特点
稳定性：不稳定，因为在分区过程中，可能会交换相等元素的相对位置。
适用性：适用于数据量较大的情况，是实际应用中效率较高的排序算法之一。

四、选择排序

（一）直接选择排序

基本思想
直接选择排序的基本思想是在待排序序列中，每次选择最小（或最大）的元素，将其与序列的第一个（或最后一个）元素交换位置，然后在剩下的元素中重复上述过程，直到整个序列有序。

具体步骤
初始时，整个序列为待排序序列，有序序列为空。
在待排序序列中找到最小的元素，将其与待排序序列的第一个元素交换位置，此时该元素进入有序序列。
待排序序列减少一个元素，重复上述步骤，直到待排序序列为空。

实现代码（C 语言）
void SelectSort(int A[], int n) {int i, j, min, temp;for (i = 0; i < n - 1; i++) {min = i;  // 记录最小元素的下标for (j = i + 1; j < n; j++) {if (A[j] < A[min]) {min = j;  // 更新最小元素的下标}}// 交换最小元素和待排序序列的第一个元素temp = A[i];A[i] = A[min];A[min] = temp;}
}

时间复杂度
无论待排序序列的初始状态如何，在每一趟排序中都需要遍历待排序序列以找到最小元素，所以时间复杂度始终为 O (n²)，包括最好情况、最坏情况和平均情况。

空间复杂度
空间复杂度为 O (1)，只需要一个临时变量用于交换元素和一个变量用于记录最小元素的下标。

算法特点
稳定性：不稳定，例如序列 [2, 2, 1]，第一次选择最小元素 1，与第一个 2 交换位置，得到 [1, 2, 2]，两个 2 的相对顺序发生了改变。
适用性：适用于数据量较小的情况，实现简单，但效率不高。

（二）堆排序

基本思想
堆排序是利用堆这种数据结构进行排序的算法。堆是一种完全二叉树，分为大根堆和小根堆。大根堆是指每个节点的值都大于或等于其左右孩子节点的值；小根堆是指每个节点的值都小于或等于其左右孩子节点的值。堆排序的基本思想是将待排序序列构造成一个大根堆，此时堆顶元素为最大元素，将其与序列的最后一个元素交换位置，然后将剩下的元素重新构造成一个大根堆，重复上述过程，直到整个序列有序。

具体步骤
构建大根堆：将待排序序列构造成一个大根堆。
交换堆顶元素和堆尾元素：将堆顶的最大元素与堆尾元素交换，此时最大元素被放置在序列的末尾。

调整堆：将除了最后一个元素之外的元素重新构造成一个大根堆。

重复步骤 2 和步骤 3，直到所有元素都排序完成。

实现代码（C 语言）
// 堆调整函数
void HeapAdjust(int A[], int k, int len) {A[0] = A[k];  // 暂存根节点for (int i = 2 * k; i <= len; i *= 2) {  // 沿关键字较大的孩子节点向下筛选if (i < len && A[i] < A[i + 1]) {i++;  // 取关键字较大的孩子节点的下标}if (A[0] >= A[i]) {break;  // 根节点大于等于最大孩子节点，调整结束} else {A[k] = A[i];  // 将最大孩子节点的值赋给当前节点k = i;  // 修改k值，继续向下筛选}}A[k] = A[0];  // 将暂存的根节点值放到最终位置
}// 堆排序函数
void HeapSort(int A[], int n) {// 构建大根堆for (int i = n / 2; i >= 1; i--) {HeapAdjust(A, i, n);}// 排序for (int i = n; i > 1; i--) {int temp = A[1];  // 交换堆顶元素和堆尾元素A[1] = A[i];A[i] = temp;HeapAdjust(A, 1, i - 1);  // 调整剩余元素为大根堆}
}

时间复杂度
构建大根堆的时间复杂度为 O (n)。
每一次堆调整的时间复杂度为 O (log n)，共需要进行 n-1 次堆调整，所以堆调整的总时间复杂度为 O (n log n)。
因此，堆排序的总时间复杂度为 O (n log n)，且不受序列初始状态的影响，最好情况、最坏情况和平均情况的时间复杂度均为 O (n log n)。
空间复杂度
空间复杂度为 O (1)，只需要一个临时变量用于交换元素和一个暂存根节点的变量。
算法特点
稳定性：不稳定，因为在交换堆顶元素和堆尾元素以及调整堆的过程中，可能会改变相等元素的相对顺序。
适用性：适用于数据量较大的情况，是一种高效的排序算法。

五、归并排序

（一）基本思想

归并排序是一种分治法的排序算法。其基本思想是将待排序序列分成两个长度大致相等的子序列，分别对这两个子序列进行归并排序，然后将排好序的子序列合并成一个有序的序列。

（二）具体步骤

分解：将待排序序列分解成两个长度为 n/2 的子序列。
递归求解：如果子序列的长度大于 1，则对每个子序列重复分解和递归求解的过程；如果子序列的长度为 1，则该子序列已经有序。
合并：将两个排好序的子序列合并成一个有序的序列。

（三）实现代码（C 语言）

// 合并函数
void Merge(int A[], int low, int mid, int high) {int i, j, k;int *B = (int *)malloc((high - low + 1) * sizeof(int));  // 辅助数组for (k = low; k <= high; k++) {B[k - low] = A[k];  // 将A中的元素复制到B中}for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {if (B[i - low] <= B[j - low]) {A[k] = B[i - low];  // 将较小的元素放入A中i++;} else {A[k] = B[j - low];j++;}}while (i <= mid) {A[k++] = B[i - low];  // 复制剩余的元素i++;}while (j <= high) {A[k++] = B[j - low];j++;}free(B);  // 释放辅助数组
}// 归并排序函数
void MergeSort(int A[], int low, int high) {if (low < high) {int mid = (low + high) / 2;  // 中间位置MergeSort(A, low, mid);  // 递归排序左子序列MergeSort(A, mid + 1, high);  // 递归排序右子序列Merge(A, low, mid, high);  // 合并}
}

（四）时间复杂度

归并排序的时间复杂度不受序列初始状态的影响，在最好情况、最坏情况和平均情况下，时间复杂度均为 O (n log n)。

（五）空间复杂度

归并排序需要一个辅助数组来存储合并过程中的元素，所以空间复杂度为 O (n)。

（六）算法特点

稳定性：稳定，因为在合并过程中，当两个子序列中的元素相等时，会将左子序列中的元素先放入结果序列中，保持它们的相对顺序。
适用性：适用于数据量较大的情况，尤其是外部排序（数据不能全部放入内存的排序）。

六、基数排序

（一）基本思想

基数排序是一种非比较型排序算法，它是根据元素的关键字的各位值来进行排序的。其基本思想是将待排序元素按照关键字的不同位进行排序，通常从最低位开始，依次对每一位进行排序，直到最高位排序完成，整个序列有序。

（二）具体步骤

确定排序的位数：找出待排序序列中最大元素的位数，作为排序的总位数。
初始化 10 个队列：分别对应 0-9 这 10 个数字。
按位排序：从最低位开始，对于每一位，将元素按照该位的数字放入对应的队列中，然后按照队列的顺序将元素取出，组成新的序列。
重复步骤 3，直到最高位排序完成。

（三）实现代码（C 语言）

// 获取数字的第d位数字
int GetDigit(int x, int d) {int div = 1;for (int i = 1; i < d; i++) {div *= 10;}return (x / div) % 10;
}// 基数排序函数
void RadixSort(int A[], int n, int maxd) {int i, j, d, digit;int *count = (int *)malloc(10 * sizeof(int));  // 计数数组int *temp = (int *)malloc(n * sizeof(int));  // 临时数组for (d = 1; d <= maxd; d++) {  // 从低位到高位依次排序for (i = 0; i < 10; i++) {count[i] = 0;  // 计数数组初始化}// 统计每个数字出现的次数for (i = 0; i < n; i++) {digit = GetDigit(A[i], d);count[digit]++;}// 计算每个数字在temp中的位置for (i = 1; i < 10; i++) {count[i] += count[i - 1];}// 将元素放入temp中for (i = n - 1; i >= 0; i--) {digit = GetDigit(A[i], d);temp[count[digit] - 1] = A[i];count[digit]--;}// 将temp中的元素复制回A中for (i = 0; i < n; i++) {A[i] = temp[i];}}free(count);free(temp);
}

（四）时间复杂度

设待排序序列有 n 个元素，关键字的最大位数为 d，每一位的基数为 r（这里 r=10）。则基数排序的时间复杂度为 O (d (n + r))。在实际应用中，d 通常是一个较小的常数，所以时间复杂度可以近似为 O (n)。

（五）空间复杂度

基数排序需要两个辅助数组：计数数组和临时数组，所以空间复杂度为 O (n + r)，其中 r 为基数。

（六）算法特点

稳定性：稳定，因为在按位排序时，对于相同位数字的元素，会按照它们原来的相对顺序放入队列中。
适用性：适用于关键字可以分解成若干位，且每位的取值范围较小的情况，如整数、字符串等。

八、排序算法的应用场景

当数据量较小时，可选择直接插入排序、冒泡排序、直接选择排序等简单排序算法，它们实现简单，在数据量小时效率差异不大。

当数据量较大时，应选择快速排序、堆排序、归并排序等高效排序算法。其中，快速排序在平均情况下效率最高，但在最坏情况下性能较
差；堆排序在最坏情况下性能稳定；归并排序是稳定的排序算法，适用于外部排序。

当需要稳定的排序算法时，可选择直接插入排序、冒泡排序、归并排序、基数排序等。

当关键字可以分解成若干位，且每位的取值范围较小时，可选择基数排序。