🛁 冒泡排序 (Bubble Sort)

归档: #Algorithm #Sorting #Elementary

核心心法: "推土机" —— 每一轮把最大的石头推到最右边。

🧠 核心思想

它通过重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

• 每一轮遍历就像一个推土机从左走到右。
• 每一轮结束，最大的那个元素就像气泡一样“冒”到了数组的最右端（有序区）。

🎨 图解演示

点击“开始排序”演示冒泡过程

20

50

10

90

30

70

40

80

60

5

💻 代码实现 (C++)

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    // 外层循环：要把 n 个气泡冒上去，需要 n-1 轮
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // 🚦 优化标记：如果这一轮没交换，说明已经排好了
        
        // 内层循环：推土机工作
        // 注意：后 i 个元素已经排好了，不需要再推了，所以是 n - 1 - i
        for (int j = 0; j < n - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                swapped = true;
            }
        }
        
        // 如果全程无交换，直接收工
        if (!swapped) break;
    }
}

📊 复杂度分析

维度	数值	说明
时间 (平均)		两层循环，效率低
时间 (最好)		数组本身就是有序的 (配合 swapped 优化)
空间		原地交换，不需要额外空间
稳定性	✅ 稳定	相等的元素不会交换位置

💡 适用场景

• 教学演示：理解“交换”和“循环”的最好例子。

• 检测有序：如果只需跑一轮就知道数组是否有序。