CC++ & Algorithm

排序算法比较与应用——选对方法事半功倍

中等5
语言版本：C++
概述：对比冒泡、选择、插入、计数四种排序的特点，告诉你在不同场景下该选哪一种。

选对排序，事半功倍——四种常用排序算法大比拼

同学们，我们在写程序时经常要给一堆数据排好顺序，比如按成绩从高到低、按零食价格从低到高、按打游戏得分排个名次。排序的方法有很多种，不同方法就像不同的工具——用对了，程序跑得飞快；用错了，可能半天没结果。今天我们就拿四种最常用的排序（冒泡、选择、插入、计数）来对比，让你知道什么情况下该选哪一种。

一、冒泡排序——像泡泡一样浮上来

原理：从前往后两两比较相邻的元素，如果顺序不对就交换。每一轮会把当前最大的（或最小的）元素“浮”到数组末尾。就像汽水里的小气泡，大的气泡先浮到水面。

生活例子：老师让全班同学按身高排队，你从排头开始，让每两个相邻的同学比较身高，矮的站前面，高的站后面。走完一遍后，最高的同学就会自动到队尾。然后对剩下的人重复，直到全部排好。

#include <iostream>
using namespace std;

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};  // 待排序数组
    int n = 7;  // 数组长度

    // 冒泡排序
    for (int i = 0; i < n - 1; i++) {          // 一共需要n-1轮
        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;
            }
        }
    }

    // 输出排序结果
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

特点：

  • 非常简单，是入门排序的第一课
  • 速度慢：数据有n个，比较次数大约是 n×(n-1)/2 次，写成O(n²)
  • 交换次数多：最坏情况每比较一次就交换一次

适合场景：学习排序原理、数据量极小（比如不超过20个）

二、选择排序——每次挑个最合适的

原理：每一轮从剩下的未排序元素中找出最小的（或最大的），把它放到已排序部分的末尾。就像你从一堆零食里选最贵的，放到左手边，然后从剩下的里再选最贵的，以此类推。

生活例子：你有几张考试卷子想按分数从低到高放好。你每次都从没排好的卷子里找出分数最低的那张，放到最右边（或最左边）。重复直到全部排好。

#include <iostream>
using namespace std;

int main() {
    int arr[] = {64, 25, 12, 22, 11};  // 待排序数组
    int n = 5;

    // 选择排序
    for (int i = 0; i < n - 1; i++) {       // i表示当前要放的位置
        int min_idx = i;                     // 假设当前位置的元素是最小的
        for (int j = i + 1; j < n; j++) {   // 在剩下的元素中找更小的
            if (arr[j] < arr[min_idx]) {
                min_idx = j;                 // 记录最小元素的下标
            }
        }
        // 把最小的元素和当前位置交换
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }

    // 输出
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

特点：

  • 交换次数少：每一轮只交换一次，总交换次数为 n-1 次
  • 速度依然是 O(n²)，因为比较次数和冒泡一样多
  • 不稳定：相同值的元素，排序后相对顺序可能改变。比如两个都是80分的同学，本来A在前，B在后，选择排序可能把B换到前面去了。

适合场景：对交换成本很在意（比如交换两个元素很耗时），但对稳定性没要求时。

三、插入排序——像打扑克牌一样理牌

原理：把数组看成两部分：左边是已经排好序的（初始只有第一个元素），右边是未排序的。每次从右边拿一个元素，插入到左边正确的位置。就像你打牌时，每摸一张牌，就插到手里已经排好序的牌里。

生活例子：你有一堆零花钱硬币，面额有1角、5角、1元。你先把第一个硬币放在桌上，然后拿起第二个硬币，跟第一个比，插到合适的位置。第三个硬币插到前两个合适的位置……每次只移动少量硬币，直到全部排好。

#include <iostream>
using namespace std;

int main() {
    int arr[] = {12, 11, 13, 5, 6};  // 待排序数组
    int n = 5;

    // 插入排序
    for (int i = 1; i < n; i++) {        // 从第二个元素开始（i=1）
        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;                // 把key放到正确位置
    }

    // 输出
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

特点：

  • 速度也是 O(n²)，但是！
  • 如果数据基本有序，它的速度会快到接近 O(n)——因为几乎不需要移动元素。
  • 稳定：相同值的元素不会交换相对顺序。
  • 节省内存：不需要额外的大数组。

适合场景：数据量小、或数据已经大致有序（比如老师只把一两个同学的位置弄错了），此时插入排序是最佳选择。

四、计数排序——用“格子”来数数字

原理：如果知道所有数字的范围（比如0~100分），可以准备一排“格子”（数组），每个格子统计一个数字出现的次数。然后从左到右把数字按次数倒出来，就得到了排好序的序列。

生活例子：你们班有50个同学，考试分数都在0~100之间。老师想快速知道每个分数有多少人，然后按分数从低到高列出所有分数。他先准备101个格子（0分到100分），每个格子放一个计数器。批完卷子，在对应分数格子里放一颗糖果（计数+1）。最后从0分格子开始，把糖果一颗颗拿回来，就得到了排序后的分数列表。

#include <iostream>
using namespace std;

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};  // 待排序数组，数字范围0~9
    int n = 7;
    int max_val = 9;                     // 已知最大值

    // 1. 创建计数数组，初始全为0
    int count[max_val + 1] = {0};

    // 2. 统计每个数字出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;                 // 比如arr[i]=3，则count[3]加1
    }

    // 3. 根据计数结果，把数字放回原数组
    int idx = 0;                         // 当前要放的位置
    for (int val = 0; val <= max_val; val++) {  // 遍历每个可能的数字
        while (count[val] > 0) {         // 这个数字出现了几次就放几次
            arr[idx] = val;
            idx++;
            count[val]--;
        }
    }

    // 输出
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

特点：

  • 速度极快：时间复杂度 O(n + k)，其中 k 是数字范围。n很大时，只要k不大，就比任何O(n²)的算法快很多。
  • 稳定：实现得当可以保持相同元素的相对顺序。
  • 局限性：只能对整数排序，而且需要提前知道数字的范围。如果数字范围太大（比如0~10亿），计数数组会占用太多内存，就不合适了。

适合场景：考试分数（0100）、年龄（0150）、彩票号码（4位数）等数字范围小且为整数的场景。

五、一表对比，一目了然

排序算法速度（时间复杂度）优点缺点
冒泡排序较慢 (O(n²))简单易懂交换次数多，慢
选择排序较慢 (O(n²))交换次数少不稳定（相同值的顺序可能变）
插入排序较慢 (O(n²))，但数据基本有序时很快稳定，节省内存数据乱序时慢
计数排序极快 (O(n+k))，k是数字范围线性时间，稳定只适用于整数且范围小

六、什么时候用哪种？

  • 如果数据量很小（比如少于100个），用任何一个都可以，但插入排序通常表现最好，因为它利用了局部有序性，而且代码也简单。
  • 如果数据基本已经有序（只是个别元素乱序），插入排序是王者，几乎不需移动。
  • 如果数字范围很小（比如考试分数0~100），计数排序是最佳选择，快到飞起。
  • 如果只是为了学习排序原理，冒泡和选择最简单，适合入门。
  • 如果数据量很大（数千以上）且数字范围也不小，就需要学习更高级的算法（比如快速排序、归并排序），这将在后续学习。

七、新手常犯的错误

  1. 冒泡排序的循环边界写错：内层循环 j < n-i-1 容易写成 j < n-i，导致数组越界访问。记住每轮已经浮上去的元素就不需要再比较了。
  2. 选择排序忘记更新最小下标：写代码时容易忘记在找到更小值时更新 min_idx，导致选错元素。
  3. 插入排序的 while 条件：容易写成 arr[j] > key 但忘记 j>=0 的判断，导致数组越界。也可以先判断 j>=0，再判断 arr[j] > key。
  4. 计数排序的数组大小：如果最大值是 max_val，计数数组长度应为 max_val+1（因为下标从0到max_val），新手容易写成 max_val，导致越界。
  5. 忽略稳定性需求：在需要保持相同元素原始顺序的场景（比如按成绩排序，同分的人按学号先后），选择冒泡、插入、计数（稳定实现）而不要用选择排序。

八、完整可运行示例：按考试成绩排序

下面这个程序从键盘输入若干考试分数（0~100），用计数排序帮老师快速排好成绩。

#include <iostream>
using namespace std;

int main() {
    int scores[100];          // 最多存100个分数
    int n = 0;                // 实际人数
    int max_score = 100;      // 最高分已知为100

    // 输入分数，直到输入-1结束
    cout << "请输入考试成绩（0~100），输入-1结束：" << endl;
    while (true) {
        int s;
        cin >> s;
        if (s == -1) break;
        if (s < 0 || s > 100) {
            cout << "分数必须在0~100之间，重新输入：";
            continue;
        }
        scores[n] = s;
        n++;
    }

    // 计数排序
    int count[101] = {0};       // 101个格子：0分到100分
    for (int i = 0; i < n; i++) {
        count[scores[i]]++;     // 统计每个分数出现次数
    }

    // 输出排序结果
    cout << "排序后的成绩（从低到高）：" << endl;
    for (int score = 0; score <= max_score; score++) {
        while (count[score] > 0) {
            cout << score << " ";
            count[score]--;
        }
    }
    cout << endl;
    return 0;
}

运行示例：

请输入考试成绩（0~100），输入-1结束：
88 72 93 65 88 100 55 72 -1
排序后的成绩（从低到高）：
55 65 72 72 88 88 93 100

九、接下来学什么？

当你面对成千上万个数据，数字范围又很大时，O(n²)的算法就太慢了。这时候需要更高级的排序方法：

  • 快速排序：平均速度 O(n log n)，非常快，最常用。
  • 归并排序：稳定，O(n log n)，适合大数据。
  • 堆排序：利用堆结构，O(n log n)。

这些算法将在后续的CSP-J学习中见到。记住：没有最好的排序，只有最适合当前数据的排序。理解每种算法的特点，你就能在写程序时选出最合适的方法，让程序跑得更快！

例题精讲

1单选题

以下哪种排序算法最适合对已知数值范围且范围较小的整数数组进行排序？

A冒泡排序
B选择排序
C插入排序
D计数排序
2单选题

关于冒泡排序和选择排序的稳定性，下列说法正确的是？

A冒泡排序是稳定的，选择排序是不稳定的
B两者都是稳定的
C两者都是不稳定的
D冒泡排序是不稳定的，选择排序是稳定的
3判断题

插入排序在最好情况下的时间复杂度为O(n)。

4填空题
以下插入排序代码中，while循环的条件处应填写什么？

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (___) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
5填空题
以下计数排序代码中，统计频率的语句应填写什么？

void countingSort(int arr[], int n, int range) {
    int count[range + 1] = {0};
    for (int i = 0; i < n; i++) {
        ___ ;
    }
    for (int i = 1; i <= range; i++) {
        count[i] += count[i - 1];
    }
    int output[n];
    for (int i = n - 1; i >= 0; i--) {
        output[--count[arr[i]]] = arr[i];
    }
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}