06 排序算法与查找

GESP 4-5 级CSP-J 高频

级别标注：GESP 4 级（选择/冒泡/插入排序）/ 5 级（归并·快排·二分）（考级要求）/ CSP-J 高频考点（竞赛进阶）。

一、为什么需要排序

排序是把数据按某种规则（升序/降序）重新排列。它是许多算法（二分、贪心、归并统计）的前置。

排序算法概览：

算法	平均时间复杂度	稳定性	是否原地	主要用途
冒泡排序	O(n²)	稳定	是	教学、小数据
选择排序	O(n²)	不稳定	是	教学
插入排序	O(n²)	稳定	是	近乎有序数据快
归并排序	O(n log n)	稳定	否（需额外空间）	稳定排序、逆序对
快速排序	O(n log n)	不稳定	是	通用场景首选
STL sort	O(n log n)	不稳定	是	竞赛日常首选

形象理解排序像整理书架：不整理时找一本书要一本本翻（顺序查找 O(n)），整理好后按字母定位就像查字典（二分查找 O(log n)）。很多算法（二分、贪心、合并统计）都要求数据“先排好队”。

考级视角GESP 4 级考排序稳定性：冒泡、插入、归并稳定（相等元素相对顺序不变）；选择、快排不稳定。笔试判断题高频，用“两个相同分数按姓名字典序排”的场景理解。

二、冒泡排序

每轮把"最大（小）"元素像气泡一样浮到末尾。

C++ 实例

#include <iostream>
using namespace std;

// 冒泡排序：像气泡一样把大的元素逐步"浮"到末尾
void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {          // 第 i 轮：确定倒数第 i+1 个位置
        bool swapped = false;                  // 记录本轮是否有交换
        for (int j = 0; j < n - 1 - i; j++) {  // 每轮末尾已有序，少比较一个
            if (a[j] > a[j + 1]) {             // 相邻元素逆序则交换
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;                   // 本轮无交换说明已有序，提前结束
    }
}
int main() {
    int a[10] = {5, 3, 8, 1, 9, 2, 7, 4, 6, 0};
    int n = 10;
    bubbleSort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

形象理解冒泡像汽水里的气泡：每轮扫描，把当前最大（小）的元素一路“冒”到末尾。已经有序的数组一轮扫描没发生交换（swapped == false）就可以提前收工。

易错点冒泡边界最难：外层 i < n-1 轮，内层 j < n-1-i。口诀：“每轮少比较一个，因为末尾已经归位”。写错边界会多比一轮或漏比一轮。

三、选择排序

每轮从剩余元素中找最值，交换到正确位置。

C++ 实例

#include <iostream>
using namespace std;

// 选择排序：每轮从剩余元素里挑最小的，放到当前最前
void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int mn = i;                       // 记录"最小元素下标"，先假设是 i
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[mn]) mn = j;     // 找到更小的就更新下标
        }
        swap(a[i], a[mn]);                // 把最小元素交换到位置 i
    }
}
int main() {
    int a[6] = {64, 25, 12, 22, 11, 8};
    selectionSort(a, 6);
    for (int v : a) cout << v << " ";     // 范围 for 遍历
    cout << endl;
    return 0;
}

形象理解选择排序像体育老师排队：每轮从没排好的队伍里挑最矮的，拉到队首。注意它只做“找最值 + 一次交换”，比冒泡的交换次数少很多。

易错点找最值时要记录下标而不是值：int mn = i; 从当前位开始找，找到更小的更新下标，最后 swap(a[i], a[mn])。从 0 开始找会把已排好的部分搞乱。

四、插入排序

像打扑克牌理牌，把新元素插入到已有序的前半部分。

C++ 实例

#include <iostream>
using namespace std;

// 插入排序：像打牌时把新牌插进手里已排好序的位置
void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];              // 当前要插入的"新牌"
        int j = i - 1;
        while (j >= 0 && a[j] > key) {   // 把比 key 大的元素往后挪
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;              // 找到空位，插入 key
    }
}
int main() {
    int a[5] = {9, 1, 5, 3, 7};
    insertionSort(a, 5);
    for (int v : a) cout << v << " ";
    cout << endl;
    return 0;
}

形象理解插入排序像打扑克理牌：新摸一张牌，从右往左找到合适位置“插”进去，手里的牌始终有序。数据越接近有序，它越快（最好 O(n)）。

考级视角笔试常问“对几乎有序的数组，哪种排序最快”——插入排序（O(n)）。还会考它稳定、原地；理解“边比较边后移”的 while 循环是手写重点。

五、归并排序（分治；O(n log n)，稳定）

把数组一分为二，各自排好后再合并。逆序对统计常基于它（见第 16/19 章）。

C++ 实例

#include <iostream>
using namespace std;
const int N = 100005;
int a[N], tmp[N];               // tmp 为归并用的临时数组

// 归并排序：先拆到最小，再两两有序合并（分治思想）
void mergeSort(int l, int r) {
    if (l >= r) return;                 // 递归终止：区间只有一个元素
    int mid = (l + r) / 2;
    mergeSort(l, mid);                  // 左半排序
    mergeSort(mid + 1, r);              // 右半排序
    // 合并两个有序区间 [l,mid] 和 [mid+1,r]
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {        // 双指针比较，取较小者进 tmp
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++]; // 左半剩余
    while (j <= r) tmp[k++] = a[j++];   // 右半剩余
    for (int t = l; t <= r; t++) a[t] = tmp[t];  // 拷贝回原数组
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    mergeSort(0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

归并排序 + 逆序对计数（竞赛高频）

C++ 实例

long long inv = 0;               // 逆序对计数（可能很大，用 long long）
// 归并排序过程中顺便统计逆序对：合并时右半元素先出队即发现逆序
void mergeCount(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeCount(l, mid);
    mergeCount(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {                     // a[j] 比 a[i] 小：a[i..mid] 都与 a[j] 构成逆序对
            inv += mid - i + 1;    // 一次性累加 mid-i+1 个
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = tmp[t];
}

形象理解归并排序像把两叠已排好的试卷合并：两个手指各指一叠的开头，谁小先拿谁，合并后依然有序。先拆到最小（分），再两两合并（治），就是“分治”。

易错点逆序对计数最容易漏：当 a[i] > a[j] 时，左半从 i 到 mid 的所有元素都比 a[j] 大，都要计入（inv += mid - i + 1），不能只加 1。另外 inv 用 long long，n=10^5 时逆序对可超过 int。

六、快速排序（分治；O(n log n)）

选"基准"，把比它小的放左边、大的放右边，再递归两边。STL 的 sort 实现是"快排 + 插入排序"混合。

C++ 实例

#include <iostream>
using namespace std;

// 快速排序：选基准，把小于基准的放左边、大于的放右边，再递归两侧
void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int p = a[(l + r) / 2];          // 基准（取中间元素，避免有序数据退化成 O(n^2)）
    int i = l, j = r;
    while (i <= j) {
        while (a[i] < p) i++;        // 从左找第一个 >=p 的位置
        while (a[j] > p) j--;        // 从右找第一个 <=p 的位置
        if (i <= j) {                // 找到一对需要交换的
            swap(a[i], a[j]);
            i++; j--;
        }
    }
    quickSort(a, l, j);              // 递归排序左侧（都 <=p 的一段）
    quickSort(a, i, r);              // 递归排序右侧（都 >=p 的一段）
}
int main() {
    int a[9] = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    quickSort(a, 0, 8);
    for (int v : a) cout << v << " ";
    cout << endl;
    return 0;
}

最坏情况（如已排序 + 固定选首元素）会退化为 O(n²)；随机化 / 取中间元素可避免。

形象理解快排像班主任分座位：先选一个“基准同学”站中间，矮的站左边、高的站右边，然后左右两拨人各自再选基准重复——分而治之，最后全场有序。

易错点快排最怕基准选得极端：已排序数组固定选首元素会退化成 O(n²)。用 a[(l+r)/2] 取中间元素或随机选基准能有效避免。笔试常考退化条件与复杂度。

七、查找：顺序查找与二分查找

7.1 顺序查找（O(n)）

找到第一个目标的位置，找不到输出 -1。

C++ 实例

// 线性查找：从头到尾逐个比较，O(n)
int linearSearch(int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key) return i;   // 找到返回下标
    return -1;                       // 没找到返回 -1
}

7.2 二分查找（O(log n)），前提：已排序

C++ 实例

// 二分查找：在递增数组里每次砍掉一半，O(log n)
// 在 [l, r) 中找第一个 >= key 的位置（左闭右开写法）
int lowerBound(int a[], int n, int key) {
    int l = 0, r = n;              // 左闭右开区间
    while (l < r) {
        int mid = l + (r - l) / 2; // 防溢出写法，等价 (l+r)/2
        if (a[mid] < key) l = mid + 1;   // mid 太小，答案在右半
        else r = mid;                    // mid 可行，答案可能是 mid 或更左
    }
    return l;                      // l 指向第一个 >= key 的下标
}

手写二分要点： - mid = l + (r - l) / 2 避免 (l+r) 溢出。 - 明确"找第一个 ≥ key"还是"最后一个 ≤ key"，对应不同的更新规则； - 复杂度 O(log n)，n=10^9 也能秒过。

形象理解二分查找像猜数字游戏：1~100 猜一个数，每次报“大了/小了”就能排除一半——所以最多 log2(100)≈7 次。前提是数字已经排好序。

易错点手写二分三坑：① mid = (l+r)/2 可能溢出，用 l + (r-l)/2；② 没先排序直接二分结果全错；③ 边界用“左闭右开 [l, r)”还是“闭区间”必须全程一致，混用必错。

八、C++ STL 排序与查找（竞赛必备）

C++ 实例

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a[6] = {3, 1, 4, 1, 5, 9};
    int n = 6;
    sort(a, a + n);             // 默认升序排序（内部是优化过的快排）
    // 降序写法：sort(a, a+n, greater<int>());
    for (int v : a) cout << v << " ";
    cout << endl;

    // 二分查找（必须先排序）
    int *pos = lower_bound(a, a + n, 4);   // 返回第一个 >=4 的迭代器
    bool has = binary_search(a, a + n, 5); // 是否存在元素 5
    cout << "第一个>=4的位置: " << (pos - a) << endl;   // 指针相减得下标
    cout << "是否有5: " << has << endl;

    // 最大值/最小值（返回迭代器，解引用取值）
    cout << *max_element(a, a + n) << " " << *min_element(a, a + n) << endl;
    return 0;
}

形象理解STL 的 sort 像一键整理：内部是快排+插入排序的混合优化，竞赛日常排序直接用它，别自己手写 O(n²) 的排序去交题。

易错点lower_bound 返回的是指针/迭代器，求下标写 pos - a；binary_search 只返回 bool。sort 默认升序，降序用 sort(a, a+n, greater<int>())，别手滑写成 greater() 少了模板参数。

九、易错点 / 常见坑点

⚠️ 边界搞错：for (j = 0; j < n - 1 - i; j++) 冒泡的 i、j 范围是最大难点，多调试输出。
⚠️ 选择排序找的"最值下标"初始化错误（应从 i 开始而非 0）。
⚠️ 归并排序的 tmp 拷贝方向写反导致结果错乱。
⚠️ 快排在大量重复元素时可能退化，注意相等元素处理（<=/>= 的移动逻辑）。
⚠️ 二分前提是已排序，忘了 sort 会得到乱结果。
⚠️ lower_bound 返回的是指针/迭代器，求下标要 pos - a。
⚠️ 逆序对统计中 inv 使用 long long（n 大时可能超 int）。

十、考级要求 vs 竞赛进阶

考级要求：冒泡/插入/选择排序的代码理解与手写、排序稳定性概念（GESP 4 级），归并/快排与二分查找/二分答案（GESP 5 级）；要求能分析最坏时间复杂度。
竞赛进阶（CSP-J/NOIP）：默认用 std::sort 提速；但归并排序求逆序对、快排思想（nth_element）、二分查找/二分答案是核心高频题型；要求理解稳定排序概念与手写下限。

十一、课内练习建议

手写冒泡、选择、插入排序，对随机数组验证正确性。
手写归并排序并在此基础上统计逆序对个数。
对 n=10^5 级数据比较 sort 与自己手写排序的速度（体会常数差异）。
二分查找练习：给定有序数组，找第一个 ≥ x、最后一个 ≤ x 的位置。