是什么
-
定义：408算法大题与选择题中最核心、要求熟练默写或调用的核心排序与划分算法。
-
大白话：考试大题最常考的硬核代码，考场上能直接照搬拿满分的必备模板。
核心内容
1. 快速排序（Quick Sort）
-
核心逻辑：基于分治思想，选枢轴进行
Partition划分，左边全放小于等于枢轴的数，右边全放大于等于枢轴的数，递归处理左右子表。 -
复杂度：平均时间复杂度 ，最坏时间复杂度 ，平均空间复杂度 （递归栈）。
C
// 核心划分函数 Partition（双指针挖坑法，考场必背）
int Partition(int A[], int low, int high) {
int pivot = A[low]; // 选第一个元素作为枢轴(pivot支点，枢轴)
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);//对枢右边的数进行排序
}
}
-
外层
while (low < high)：控制大循环。意思是：只要两个指针没相遇，我就要继续进行“左找右找、互相填坑”的过程。 -
内层
while (low < high && ...)：控制单向移动。-
比如右指针
high在往左退（--high）的过程中，可能会一直退退退。如果没有low < high这个限制，high就会冲过头，跑到low的左边去，导致下标越界或逻辑混乱！ -
举个极端的例子：假设数组是
[1, 2, 3, 4, 5]，pivot = 1。 右指针high要找比 1 小的数。由于后面的数都比 1 大，high会不停--high。 如果没有内层的low < high判断，high会一直减到负数去（下标越界，程序崩溃）； 有了内层的low < high，当high退到和low重合时，内层循环立刻停止，防止了越界！
-
一句话总结：外层决定“要不要进行下一轮填坑”，内层决定“移动指针时不能穿过对方”。
2. 直接插入排序（Direct Insertion Sort）
-
核心逻辑：将待排序记录按大小逐个插入到前面已排好序的子序列中。
-
复杂度：平均时间复杂度 ，空间复杂度 ，算法稳定。
C
void InsertSort(int A[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
if (A[i] < A[i - 1]) {
temp = A[i];
for (j = i - 1; j >= 0 && A[j] > temp; j--) {
A[j + 1] = A[j]; // 元素后移
}
A[j + 1] = temp; // 插入到正确位置
}
}
}
3. 简单选择排序（Simple Selection Sort）
-
核心逻辑：每一趟在未排序序列中选择最小的元素，与未排序序列的第一个元素交换。
-
复杂度：平均时间复杂度 ，空间复杂度 ，算法不稳定。
C
void SelectSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (A[j] < A[min]) {
min = j;
}
}
if (min != i) {
int temp = A[i];
A[i] = A[min];
A[min] = temp;
}
}
}
例题
-
题目：已知由 个正整数构成的集合 ，将其划分为两个不相交子集 和 ，元素个数分别为 和 ，元素之和为 和 。设计算法满足 最小且 最大，并说明复杂度（2016统考真题）。
-
分析：要使 最小，两子集需平分元素个数；要使 最大，需将较小的一半元素划分为 ，剩余较大元素划分为 。无需完全排序，利用快速排序的
Partition划分找到第 小的元素位置即可。 -
答案：
采用快速选择算法（QuickSelect），基于
Partition函数进行单侧搜索。算法平均时间复杂度为 ，空间复杂度为 。
⚠️ 易错点
Warning
Partition边界等号：while (low < high && A[high] >= pivot)中的>=和<=必须带上等号，否则数组内存在重复元素时会导致无限死循环。下标 offset 陷阱：在 0-indexed 数组中，第 小的元素对应的下标是 ，终止条件应判断
pivotpos == k - 1。复杂度混淆：完全快速排序平均时间复杂度为 ；而单侧划分的快速选择算法平均时间复杂度为 。
声明/定义函数时写类型（
int A[]），实际调用/使用函数时只写名字（A）。
使用 sizeof(A) / sizeof(A[0]) 计算数组元素个数是 C/C++ 中最经典的手法，但在考研手写代码和实际开发中有一个非常致命的陷阱。
以下是该方法的两大核心注意点：
1. 数组传参退化为指针（最核心易错点 ⚠️）
现象：当数组作为参数传递给函数时，C 语言会自动将数组名“退化”为指向其首元素的指针。此时在函数内部使用 sizeof，求出的不再是数组的总字节数，而是指针变量本身占用的内存大小。
错误示例：
C
void test(int A[]) {
// ❌ 严重错误！此时 A 已经退化为 int* 指针
// 在 64 位系统下，sizeof(A) 恒等于 8 字节；sizeof(A[0]) 为 4 字节
// 算出来的 len 永远是 8 / 4 = 2！
int len = sizeof(A) / sizeof(A[0]);
}
正确做法：
-
必须在定义数组的原始作用域（如
main函数）中计算出数组长度n。 -
显式地将长度
n作为形参传递给目标函数。
2. 无法用于动态分配的内存（堆内存）
现象：使用 malloc 或 new 在堆上动态申请的内存，变量本身只是一个普通的指针，sizeof 无法获取其申请的动态内存总大小。
错误示例：
C
// ❌ 错误！A 是一个指针，sizeof(A) 只代表指针大小，无法拿到动态申请的 40 字节
int *A = (int *)malloc(10 * sizeof(int));
int len = sizeof(A) / sizeof(A[0]);
正确做法：
-
动态分配内存时，需要自己用变量额外保存并记录分配的元素个数。
标准正确用法示例
C
#include <stdio.h>
// 正确示范：函数接受数组首地址 A 和 数组长度 n 作为两个独立参数
void printArray(int A[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", A[i]);
}
printf("\n");
}
int main() {
// 1. 在定义数组的作用域内计算元素个数（此时 A 尚未退化为指针）
int A[] = {10, 20, 30, 40, 50, 60};
// ✅ 正确：sizeof(A) 获取数组总字节数 (24)，sizeof(A[0]) 获取单个元素字节数 (4)
int n = sizeof(A) / sizeof(A[0]);
printf("数组元素个数 n = %d\n", n); // 输出：6
// 2. 将计算好的长度 n 显式传递给函数使用
printf("数组元素内容：");
printArray(A, n);
return 0;
}
核心记忆守则
-
计算位置：
sizeof(A) / sizeof(A[0])必须且只能写在定义数组的同一个函数/作用域内（通常是main函数或局部栈数组定义处）。 -
函数传参：编写调用的子函数时（如
QuickSort、Partition），一定要单独留一个形参int n（或int low, int high）来接收长度，绝不能在子函数内部去算长度。
💡 考场与答题速记
总结：
sizeof(A) / sizeof(A[0])只对本地栈上定义的静态/固定长度数组生效。一旦跨过函数调用的门槛，数组名就会退化为指针，此公式立刻失效！