一、冒泡排序

基本思想

冒泡排序的核心思路是：

相邻元素两两比较，把较大的数往后“冒”，每一轮都会将未排序部分中的最大值放到最后。

就像水里的气泡一样，每次“冒”出一个最大值到顶部。

---

排序过程示意

假设数组为：

[5, 3, 4, 1]

1️、第 1 轮：

[3, 4, 1, 5] → 最大值 5 被放到最后

2️、第 2 轮：

[3, 1, 4, 5] → 次大值 4 到倒数第二个

3️、 第 3 轮：

[1, 3, 4, 5] → 全部有序

---

C语言实现

#include <stdio.h>

void bubble_sort(int a[], int len) {
    int i, j;
    for (j = len - 1; j > 0; j--) {  // 外层控制趟数
        for (i = 0; i < j; i++) {    // 内层控制相邻比较
            if (a[i] > a[i + 1]) {   // 前大后小则交换
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
            }
        }
    }
}

int main() {
    int a[] = {5, 2, 9, 1, 7};
    int len = sizeof(a) / sizeof(a[0]);
    bubble_sort(a, len);
    for (int i = 0; i < len; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

---

特点总结

特性	冒泡排序
时间复杂度	O(n²)
空间复杂度	O(1)
稳定性	稳定
适用场景	数据量较小，逻辑入门

---

二、选择排序

基本思想

选择排序每一轮从 未排序部分中找到最小值，放到当前起始位置。
即：

每轮“选择”一个最小的，放到前面。

---

排序过程示意

[5, 3, 4, 1]

1️、 找最小值 1 → 放到第 0 位
→ [1, 3, 4, 5]

2️、继续在 [3, 4, 5] 中找最小值 3
→ [1, 3, 4, 5]（已经排好）

---

C语言实现

void select_sort(int a[], int len) {
    int i, j;
    for (j = 0; j < len - 1; j++) {
        for (i = j + 1; i < len; i++) {
            if (a[j] > a[i]) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }
}

---

特点总结

特性	选择排序
时间复杂度	O(n²)
空间复杂度	O(1)
稳定性	不稳定（相同元素可能交换）
适用场景	小规模数组、要求交换次数较少的情况

---

三、插入排序

基本思想

插入排序的思路就像打扑克牌：

把一个“新牌”插入到已经排好序的手牌中，保持顺序不变。

每次取出一个元素，插入到前面有序区间的正确位置。

---

排序过程示意

初始： [5, 3, 4, 1]
第1轮： [3, 5, 4, 1]
第2轮： [3, 4, 5, 1]
第3轮： [1, 3, 4, 5]

---

C语言实现

void insert_sort(int a[], int len) {
    for (int i = 0; i < len - 1; i++) {
        int j = i + 1;
        int k = a[j]; // 待插入元素
        while (j > 0 && a[j - 1] > k) { // 从后往前比较
            a[j] = a[j - 1]; // 整体后移
            j--;
        }
        a[j] = k; // 插入到正确位置
    }
}

---

特点总结

特性	插入排序
时间复杂度	O(n²)，但在部分有序数据中更快
空间复杂度	O(1)
稳定性	稳定
适用场景	数据量小、部分有序的数据集

---

四、三种排序的对比

排序算法	时间复杂度	空间复杂度	稳定性	特点
冒泡排序	O(n²)	O(1)	稳定	实现简单、效率低
选择排序	O(n²)	O(1)	不稳定	交换次数最少
插入排序	O(n²)	O(1)	稳定	局部有序时性能好

---

五、总结

排序类型	思想简述	推荐使用场景
冒泡排序	两两交换，最大“冒”上来	基础教学、逻辑入门
选择排序	找最小放前面	数据量小，交换代价高的场合
插入排序	插入到有序区间	数据部分有序时更高效