【C语言期末速成篇】一篇全拿下，八大排序算法保姆级图解完整源码

🔥个人主页：代码不加冰（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：LeetCode刷题日记 ， 苍穹外卖日记，SSM框架深入，JavaWeb，
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

大家好，我是代码不加冰，C语言还有三天考试，但我现在还是零基础，今天下午开始学习，先把一些基础的经典算法过一遍。

从冒泡到堆排序，从 O(n²) 到 O(n log n)，动态步骤拆解 + 完整 C 源码 + 考场注意事项，一篇通吃期末、二级和面试。

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[j+1]不含等号），保证相同元素相对顺序不变

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; // 找到位置，插入 } }

注意是"移动"而不是"交换"——每次插入只需一次写入，比冒泡少很多操作

从 i=1 开始，默认把 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; // 防止 (l+r)/2 溢出 mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } }

中点写成l + (r-l)/2而非(l+r)/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[i+1]; arr[i+1] = 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，左孩子 2i+1，右孩子 2i+2

建堆从 n/2-1 开始（最后一个非叶子节点），向前遍历，比从头建堆更高效

最佳场景：内存极紧张又要 O(n log n)，堆排序是唯一既省空间又保证性能的选择

08计数排序

💡核心思想— 突破比较的限制，直接统计每个值出现了多少次。开辟一个 count 数组，count[v] 记录值 v 的出现次数，再按顺序"倒"回来。适合数据范围 k 较小的整数排序，否则浪费大量内存。

O(n+k)稳定非比较排序仅适合小范围整数

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 时碾压一切比较排序