青橙 Studio

Appearance

📊 02. 排序算法 ​

排序算法 的核心作用是将一组数据按特定顺序排列（通常是升序或降序）。排序是计算机科学中最基础、最常用的操作之一。

为什么排序这么重要？

  • 数据检索：排序后可以用二分查找快速定位数据。
  • 数据展示：排行榜、成绩单都需要按顺序排列。
  • 任务调度：按优先级排序后依次执行。
  • 数据分析：排序是许多高级算法（如去重、归并）的前置步骤。

NOTE

排序算法有很多种，但 L2 阶段我们只学三种最基础的：冒泡排序、选择排序、插入排序。它们的共同点是实现简单、容易理解，适合初学者建立算法思维。

一、冒泡排序（Bubble Sort）🫧 ​

1. 基本思想 ​

冒泡排序通过相邻元素之间的比较和交换，逐步将"最大"元素"冒泡"到数组末尾。

就像水中气泡上升一样，越大的气泡升得越快，最终浮到水面。

2. 工作原理 ​

  1. 从数组开头开始，依次比较相邻的两个元素。
  2. 如果前一个大于后一个，就交换它们。
  3. 经过第一轮，最大的元素"冒泡"到了最后一位。
  4. 重复以上过程，但每轮少比较最后一个（已排好序的）元素。
  5. 直到所有元素排好序。

3. 图解过程 ​

以数组 [5, 3, 4, 1, 2] 为例：

第一轮：         第二轮：         第三轮：
[5, 3, 4, 1, 2]  [3, 4, 1, 2, 5]  [3, 1, 2, 4, 5]
 ↓↔                ↓↔                ↓↔
[3, 5, 4, 1, 2]  [3, 1, 4, 2, 5]  [1, 3, 2, 4, 5]
    ↓↔                ↓↔                ↓↔
[3, 4, 5, 1, 2]  [3, 1, 2, 4, 5]  [1, 2, 3, 4, 5] ✅
       ↓↔                ↓
[3, 4, 1, 5, 2]  [3, 1, 2, 4, 5]
          ↓↔
[3, 4, 1, 2, 5]  ← 5 到位了

4. 代码实现 ​

cpp
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    // 外层循环：控制比较的轮数
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;  // 标记本轮是否发生交换

        // 内层循环：相邻元素比较
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }

        // 如果某一轮没有发生交换，说明已经有序，提前结束
        if (!swapped) {
            break;
        }
    }
}

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

    cout << "排序前：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    bubbleSort(arr, n);

    cout << "排序后：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出：

排序前：64 34 25 12 22 11 90
排序后：11 12 22 25 34 64 90

5. 复杂度分析 ​

指标值
最坏时间复杂度O(n²) —— 数组完全逆序
最好时间复杂度O(n) —— 已排好序（加 swapped 优化后）
平均时间复杂度O(n²)
空间复杂度O(1) —— 原地排序，只用了一个 temp 变量

TIP

冒泡排序的优化技巧：用一个 bool 变量 swapped 检查每轮是否有交换。如果某一轮一次交换都没有，说明数组已经有序，可以提前结束。

二、选择排序（Selection Sort）🎯 ​

1. 基本思想 ​

选择排序通过不断从未排序部分中选出最小元素，放到已排序部分的末尾。

就像打牌时，你从桌上剩下的牌里每次都挑最小的那张放到手里。

2. 工作原理 ​

  1. 将数组分为已排序区（左侧）和未排序区（右侧）。
  2. 在未排序区中找到最小的元素。
  3. 将最小元素与未排序区的第一个元素交换位置。
  4. 未排序区缩小一个元素，已排序区扩大一个。
  5. 重复直到全部有序。

3. 代码实现 ​

cpp
#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;  // 假设当前位置就是最小值

        // 在未排序区寻找真正的最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 将最小值交换到当前位置
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

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

    cout << "排序前：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    selectionSort(arr, n);

    cout << "排序后：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

4. 复杂度分析 ​

指标值
最坏时间复杂度O(n²)
最好时间复杂度O(n²) —— 就算已经有序，也要扫描找最小值
平均时间复杂度O(n²)
空间复杂度O(1)

TIP

选择排序的优点是交换次数少（每轮最多交换 1 次），适合"交换成本高"的场景。 缺点是不稳定（相等的元素可能会改变相对顺序），且无论数据有序与否都要执行 O(n²) 次比较。

三、插入排序（Insertion Sort）🃏 ​

1. 基本思想 ​

插入排序将当前元素插入到前面已经排好序的序列中，就像整理扑克牌一样。

打牌时，你每拿到一张新牌，就会把它插入到手中已有牌的正确位置。

2. 工作原理 ​

  1. 将第一个元素视为已经排好序。
  2. 从第二个元素开始，依次取出当前元素。
  3. 将当前元素与已排序部分的元素从后向前比较。
  4. 找到合适的位置后插入。
  5. 重复直到全部有序。

3. 图解过程 ​

以数组 [5, 3, 4, 1, 2] 为例：

初始： [5 | 3, 4, 1, 2]   ← 竖线左边是已排序区
第1步：[3, 5 | 4, 1, 2]   ← 将 3 插入到 [5] 的正确位置
第2步：[3, 4, 5 | 1, 2]   ← 将 4 插入到 [3,5] 的正确位置
第3步：[1, 3, 4, 5 | 2]   ← 将 1 插入到 [3,4,5] 的正确位置
第4步：[1, 2, 3, 4, 5]    ← 将 2 插入到 [1,3,4,5] 的正确位置 ✅

4. 代码实现 ​

cpp
#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int current = arr[i];  // 当前要插入的元素
        int j = i - 1;         // 已排序区的最后一个位置

        // 将比 current 大的元素向后移动
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 插入到正确位置
        arr[j + 1] = current;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    insertionSort(arr, n);

    cout << "排序后：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

5. 复杂度分析 ​

指标值
最坏时间复杂度O(n²) —— 完全逆序
最好时间复杂度O(n) —— 已经有序，只需比较 n 次
平均时间复杂度O(n²)
空间复杂度O(1)

TIP

插入排序在数据基本有序时效率非常高（接近 O(n)）。 很多高级排序算法（如快速排序）在数据规模较小时，也会改用插入排序来优化。

四、三种排序算法的对比 📊 ​

特性冒泡排序选择排序插入排序
核心操作相邻交换选最小交换插入到已排序区
最好情况O(n) ✅O(n²) ❌O(n) ✅
最坏情况O(n²)O(n²)O(n²)
交换次数多（依次冒泡）少（每轮最多1次）中（移动元素）
稳定性稳定不稳定稳定
适合场景几乎不用（太慢）交换成本高时数据基本有序时

NOTE

稳定性 是指排序后，相等元素的相对顺序是否保持不变。保持的叫"稳定排序"，否则叫"不稳定排序"。 比如按成绩排序，成绩相同的同学，如果希望保持原来的顺序，就需要用稳定排序。

五、小结 🎯 ​

  • 冒泡排序：两两比较交换，大的往后"冒泡"。实现简单，但效率最低。
  • 选择排序：每轮选最小的放前面。交换次数少，但比较次数固定为 O(n²)。
  • 插入排序：像整理扑克牌一样插入到已排序区。数据基本有序时效率高。
  • 三种排序的时间复杂度平均都是 O(n²)，适合小规模数据。

六、练习 📝 ​

  1. 模拟排序过程：用手动方式写出数组 [7, 2, 9, 1, 5] 经过冒泡排序每一轮的结果。

  2. 模拟选择排序：写出数组 [29, 10, 14, 37, 13] 经过选择排序的每一轮结果。

  3. 代码填空：补全以下冒泡排序代码：

    cpp
    void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < _______; j++) {
            if (arr[j] > arr[______]) {
                // 交换 arr[j] 和 arr[j+1]
            }
        }
    }
}

  4. 选择插入排序：编写一个程序，输入 10 个整数，使用插入排序将它们从小到大排序并输出。

  5. 反向排序：修改选择排序，实现从大到小（降序）排序。

  6. 思考题：为什么插入排序在数据"基本有序"时效率高，而选择排序不是？用大O分析说明。

💬 与我联系 QQ:774165314 | 微信:ArinRiver

Copyright © 2025-present Arin