个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺大家好我是代码不加冰C语言还有三天考试但我现在还是零基础今天下午开始学习先把一些基础的经典算法过一遍。从冒泡到堆排序从 O(n²) 到 O(n log n)动态步骤拆解 完整 C 源码 考场注意事项一篇通吃期末、二级和面试。算法平均复杂度最坏空间稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n¹·³)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定计数排序O(nk)O(nk)O(k)稳定01冒泡排序核心思想— 相邻元素两两比较大的往右沉一轮下来最大值到达末尾。加入 flag 标记可在数组已有序时提前终止最优情况 O(n)。O(n²)稳定原地排序有 flag 优化void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { int flag 0; // 优化无交换则提前退出 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; flag 1; } } if (flag 0) break; } }外层循环控制轮数内层每轮把当前最大值沉到末尾flag 优化是考试加分项写上它能说明理解了最优情况稳定性来源相等时不交换arr[j] arr[j1]不含等号保证相同元素相对顺序不变02选择排序核心思想— 每轮在未排序区间里找最小值的下标找完后再交换到最前面。交换次数是所有排序中最少的最多 n-1 次。O(n²)不稳定最少交换次数void selectionSort(int arr[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) minIdx j; // 记下最小值下标 } if (minIdx ! i) { // 不必要则不交换 int tmp arr[i]; arr[i] arr[minIdx]; arr[minIdx] tmp; } } }为什么不稳定交换可能跳过相同元素破坏原有顺序如 5 5 1 → 1 5 5 但两个 5 的位置可能对调比较次数固定 n(n-1)/2 次不受初始顺序影响没有 flag 优化空间03直接插入排序核心思想— 像打扑克牌摸牌手里的牌始终有序每摸一张就从右往左找到合适位置插进去。对于基本有序的数组效率接近 O(n)。O(n²)稳定近有序时最优void insertionSort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; // 待插入的牌 int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; // 元素后移腾出位置 j--; } arr[j 1] key; // 找到位置插入 } }注意是移动而不是交换——每次插入只需一次写入比冒泡少很多操作从 i1 开始默认把 arr[0] 视为已排好的有序序列04希尔排序核心思想— 插入排序的预处理加速版。先用大步长把数组粗略排好步长逐渐缩小最后步长为 1 时数组已经基本有序插入排序一次收尾即可。O(n¹·³)不稳定O(n²) 升级版void shellSort(int arr[], int n) { for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int tmp arr[i]; int j; for (j i; j gap arr[j - gap] tmp; j - gap) arr[j] arr[j - gap]; arr[j] tmp; } } }步长序列影响性能n/2 折半是最简单的方案Knuth 序列1,4,13...效果更好代码结构就是把插入排序的 j-1 换成 j-gap理解了插入排序就能秒懂05归并排序核心思想— 分治法把数组从中间劈开分别排好序再合并两个有序数组为一个。递归到底是单个元素天然有序从下往上合并。时间复杂度稳定在 O(n log n)是唯一最坏情况也是 O(n log n)的比较排序之一。O(n log n)稳定需要 O(n) 额外空间void merge(int arr[], int l, int m, int r) { int n1 m - l 1, n2 r - m; int L[n1], R[n2]; for (int i 0; i n1; i) L[i] arr[l i]; for (int j 0; j n2; j) R[j] arr[m 1 j]; int i 0, j 0, k l; while (i n1 j n2) arr[k] (L[i] R[j]) ? L[i] : R[j]; while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; } void mergeSort(int arr[], int l, int r) { if (l r) { int m l (r - l) / 2; // 防止 (lr)/2 溢出 mergeSort(arr, l, m); mergeSort(arr, m 1, r); merge(arr, l, m, r); } }中点写成l (r-l)/2而非(lr)/2防止大数组时整数溢出合并时用L[i] R[j]确保稳定性若写则可能打乱相等元素顺序外排序首选归并排序是磁盘文件排序的经典算法因为它对数据的访问是顺序的06快速排序核心思想— 同样是分治法但不需要额外空间。选一个基准数pivot把比它小的全挪左边比它大的全挪右边pivot 落到它的最终位置。然后对左右两段递归重复。平均情况极快但最坏情况已有序的数组选最后元素作 pivot退化到 O(n²)。O(n log n)不稳定实践中最快最坏 O(n²)int partition(int arr[], int low, int high) { int pivot arr[high]; // 选末尾元素为基准 int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } } int tmp arr[i1]; arr[i1] arr[high]; arr[high] tmp; return i 1; // pivot 的最终位置 } void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } }调用方式quickSort(arr, 0, n-1)注意第三个参数是末尾下标不是长度进阶优化随机选 pivot避免有序数组退化、三路划分处理大量重复元素面试高频考点手写快排是大厂算法面试的保留节目理解 partition 的双指针逻辑最关键07堆排序核心思想— 利用二叉堆结构建大顶堆后堆顶始终是最大值把它和末尾交换缩小堆范围再重新调整堆顶heapify反复操作直到全部有序。不需要额外空间且性能稳定在 O(n log n)。O(n log n)不稳定O(1) 空间复制// 以 i 为根调整为大顶堆堆大小为 n void heapify(int arr[], int n, int i) { int largest i; int l 2 * i 1, r 2 * i 2; if (l n arr[l] arr[largest]) largest l; if (r n arr[r] arr[largest]) largest r; if (largest ! i) { int tmp arr[i]; arr[i] arr[largest]; arr[largest] tmp; heapify(arr, n, largest); // 递归向下调整 } } void heapSort(int arr[], int n) { // 第一步建大顶堆从最后一个非叶子节点开始 for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i); // 第二步逐个把堆顶最大值移到末尾 for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; heapify(arr, i, 0); } }数组下标与树节点的关系父节点 i左孩子 2i1右孩子 2i2建堆从 n/2-1 开始最后一个非叶子节点向前遍历比从头建堆更高效最佳场景内存极紧张又要 O(n log n)堆排序是唯一既省空间又保证性能的选择08计数排序核心思想— 突破比较的限制直接统计每个值出现了多少次。开辟一个 count 数组count[v] 记录值 v 的出现次数再按顺序倒回来。适合数据范围 k 较小的整数排序否则浪费大量内存。O(nk)稳定非比较排序仅适合小范围整数void countingSort(int arr[], int n, int maxVal) { int count[maxVal 1]; int output[n]; for (int i 0; i maxVal; i) count[i] 0; for (int i 0; i n; i) count[arr[i]]; // 统计频次 for (int i 1; i maxVal; i) count[i] count[i-1]; // 前缀和 for (int i n - 1; i 0; i--) { // 反向填充保证稳定性 output[count[arr[i]] - 1] arr[i]; count[arr[i]]--; } for (int i 0; i n; i) arr[i] output[i]; }前缀和步骤是计数排序稳定性的来源不能省略反向填充从 n-1 到 0配合前缀和保证相同值的元素相对顺序不变典型应用学生成绩排名0-100 分、统计年龄分布k 远小于 n 时碾压一切比较排序
