前言

排序是数据结构与算法的基石。无论是应对面试、刷题，还是实际工程开发，掌握常见排序算法的原理与实现都是C语言学习者的必修课。

本文将从最基础的冒泡排序讲起，逐步过渡到选择排序、插入排序，最后深入讲解面试高频考点快速排序。每种算法都配有详细的思路图解、纯C语言实现代码以及优化技巧，文末还附有综合对比表格，建议收藏反复阅读！

一、冒泡排序（Bubble Sort）

1. 核心思想

重复遍历数组，依次比较相邻元素，如果顺序错误就交换。每一轮遍历都会将当前未排序部分的最大值”冒泡”到末尾。

2. C语言实现（含优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0; // 优化：标记本轮是否发生交换
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 若本轮无交换，说明已有序，提前退出
    }
}

3. 关键点

  • 时间复杂度：最优 O(n)（已有序时），最差/平均 O(n²)
  • 空间复杂度：O(1)
  • 稳定性：✅ 稳定
  • 优化点：加入 swapped 标志位，避免对已有序数组做无效遍历

二、选择排序（Selection Sort）

1. 核心思想

每轮从未排序区间中找到最小值，将其与未排序区间的第一个元素交换位置。

2. C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

3. 关键点

  • 时间复杂度：始终为 O(n²)（即使已有序也无法提前终止）
  • 空间复杂度：O(1)
  • 稳定性：❌ 不稳定（例如 [5, 5, 3] 第一轮交换后两个5的相对顺序被破坏）
  • 特点：交换次数最少（最多 n-1 次），适合交换代价高的场景

三、插入排序（Insertion Sort）

1. 核心思想

类似打扑克牌整理手牌：将未排序元素逐个插入到已排序序列的正确位置。

2. C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 将比key大的元素逐个后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

3. 关键点

  • 时间复杂度：最优 O(n)，最差/平均 O(n²)
  • 空间复杂度：O(1)
  • 稳定性：✅ 稳定
  • 实战价值：在小规模数据（n < 50）或近乎有序的数据上表现优异，常作为高级排序算法的子过程使用

四、快速排序（Quick Sort）⭐重点

1. 核心思想

分治法：选一个基准值（pivot），将数组分为”小于pivot”和”大于pivot”两部分，然后递归处理两个子数组。

2. C语言实现（Lomuto分区方案）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选最后一个元素为基准
    int i = low - 1;       // i指向小于区域的右边界

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将pivot放到正确位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

// 快速排序主函数
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);

3. 关键优化策略

优化手段 说明
三数取中法 取首、中、尾三个数的中位数作为pivot，避免最坏情况
小数组切换插入排序 当子数组长度 < 10 时改用插入排序，减少递归开销
尾递归优化 先递归较小的分区，较大的分区用循环代替，降低栈深度

4. 复杂度分析

  • 平均时间复杂度：O(n log n)
  • 最差时间复杂度：O(n²)（每次pivot恰好是最大/最小值）
  • 空间复杂度：O(log n)（递归栈）
  • 稳定性：❌ 不稳定

五、四大排序算法综合对比

算法 平均时间 最优时间 最差时间 空间 稳定性 适用场景
冒泡排序 O(n²) O(n) O(n²) O(1) ✅ 教学、极小数据量
选择排序 O(n²) O(n²) O(n²) O(1) ❌ 交换代价高的场景
插入排序 O(n²) O(n) O(n²) O(1) ✅ 小数据、近乎有序
快速排序 O(n log n) O(n log n) O(n²) O(log n) ❌ 通用大规模数据

💡 实践建议：实际工程中优先使用 qsort()（C标准库）或手写快排+插入排序混合版本；面试中务必能手写快排并解释分区逻辑。

六、测试验证代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序结果: ");
    printArray(arr, n);

    return 0;
}

输出：

1
2
原始数组: 64 34 25 12 22 11 90
排序结果: 11 12 22 25 34 64 90

总结

  • 入门三件套（冒泡、选择、插入）重在理解排序的基本思想和稳定性概念
  • 快速排序是分治思想的经典应用，也是面试和实战中最重要的一种排序算法
  • 没有”最好”的排序算法，只有”最适合”的场景——理解每种算法的优劣才能做出正确选型

📝 动手练习建议：尝试实现归并排序和堆排序，并用随机生成的万级数据实测各算法耗时，体感差异会让你记忆更深刻！