中 · 排序

冒泡排序

第一个「不只是看数据,而是改数据」的算法。你早就会比较两个数了 —— 排序就是把每一对都按正确的顺序比一遍。

一句话答案反复比较相邻的一对，顺序不对就交换，直到整趟都没有交换为止 —— O(n²)，但 n ≤ 1000 完全够用；输出用单个空格分隔。

题目

输入: 第一行一个整数 n(1 ≤ n ≤ 1000)。第二行 n 个用空格隔开的整数。

输出: 把同样的数按从小到大输出,单个空格隔开。

样例:

输入输出
5
5 3 8 1 9		1 3 5 8 9
1
42		42
4
7 7 2 2		2 2 7 7

原地排序指的是在原数组上重排,不是复制到新数组。所以交换需要临时变量 —— 下面那个错误示例会让你看清为什么。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 一趟就能把最大的数送到末尾

走一遍数组,每个元素和它的下一个比较。如果左边更大就交换。走完一趟,最大的值就「冒」到了最后 —— 因为它在参与的每次比较里都赢。做 n−1 趟,全部有序。

提示 2 — 内层循环每轮都变短

跑了 i 趟之后,最后 i 个元素已经到位了。所以内层只需要 j < n - 1 - i。去掉 - i 结果仍然正确,只是白干活 —— 你会一遍遍重复比较已经排好的尾部。

提示 3 — 交换是三条赋值

int t = a[j]; a[j] = a[j+1]; a[j+1] = t; —— 顺序很重要。第一行存在的唯一目的,就是把你马上要覆盖掉的那个值先存起来。少了它,那个值就永久消失了:你会得到一个重复的数和一个消失的数。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1005];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

冒泡排序是 O(n²),生产环境没人用它 —— 但它是「比较」和「交换」这两个所有排序算法共有的概念最清楚的展示。手写过一次之后,库函数排序就不再是魔法了。一个值得做的练习:加一个 bool swapped 标志,每次交换置真,如果某一整趟没有任何交换就跳出外层 —— 已经有序的数组于是只需一趟。接下来别再排序了,开始利用有序性:二分查找。

深度解析

为什么这样做对

比较相邻两个,逆序就交换。走一趟,最大的必然冒到末尾 —— 因为它在参与的每一次比较里都赢。重复 n−1 趟,全部有序。

代价

O(n²)。一千个数约五十万次比较,而快排只要一万次左右。它的价值在教学,不在生产。

常见错法

  • 交换时忘了临时变量,写成 a[j] = a[j+1]; a[j+1] = a[j]; —— 两个位置都变成较小值,大的那个永久消失。
  • 内层边界很要命:j < n 会越界读 a[n];而 j < n - 1 只是慢(重复比较已排好的尾部),不会错。

下一步

排好序是为了用它:二分查找 每一步扔掉一半。

记住这两句

  • 一趟冒泡 = 最大的那个就位。
  • 交换是三条赋值,第一条存在的唯一目的是别把值弄丢。
🐞 这段是错的 —— 点开,亲手让它挂一次

交换时忘了临时变量 —— 两个位置都变成较小值,大的那个丢了

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1005];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                a[j] = a[j + 1];
                a[j + 1] = a[j];
            }
        }
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}