Day 15　排序、逆序对与二分边界

建议用时：22～28 分钟
今日目标：理解冒泡、选择、插入和计数排序的过程与适用条件，知道冒泡交换次数等于逆序对数量，并能读懂 sort 的排序区间和手写二分查找。

大纲定位：冒泡排序、选择排序、插入排序、计数排序、sort 与二分查找；不扩展归并、快速、堆排序的实现。

一、排序题先确认“按什么排、排到哪里”

排序是按照关键字把一组元素重新排列。初赛不只问最终结果，更常把循环截在中间，问“一轮以后”“第 k 次交换以后”数组是什么。

模拟前先圈出四个条件：升序还是降序、比较范围、循环方向、相等时是否交换。即使都叫冒泡排序，若扫描方向或比较号不同，每轮被送到边界的元素也不同。

二、四种大纲内排序的手工过程

冒泡排序比较相邻元素。升序、从左向右扫描时，若左边大于右边就交换，一轮后当前最大值会到达最右端。

6 1 5 2 4
1 6 5 2 4 → 1 5 6 2 4 → 1 5 2 6 4 → 1 5 2 4 6

选择排序每轮从未排序区间找出最小值，再与区间第一个位置交换。它不是边扫描边交换：6,1,5,2,4 第一轮只需确定最小值 1，最后与 6 交换，得到 1,6,5,2,4。

插入排序把当前元素插入前面已经有序的部分。处理 3,5,2 中的 2 时，应先把 5、3 依次右移，再把 2 放入空位，得到 2,3,5。它很像整理手中的扑克牌。

计数排序不比较两个元素的大小，而是先统计每个值出现多少次，再按值从小到大输出。例如 3,1,2,1,3 的计数为 1→2 次，2→1 次，3→2 次，据此还原为 1,1,2,3,3。

计数排序适合整数值域较小、范围明确的情况。如果数据值可能达到十亿，却只有几个数，直接开一张覆盖整个值域的计数表就不合适。

三、逆序对与冒泡交换次数

在数组中，若 i<j 且 a_i>a_j，下标对 (i,j) 构成一个逆序对。注意比较的是原数组中的先后位置，不要求两个元素相邻。

对 6,1,5,2,4：6 与后面四个数都逆序，5 与 2、4 逆序，共 6 对。

升序冒泡每次只交换一对相邻的逆序元素，这次交换恰好消去 1 个逆序对，不会改变它们与其他元素的相对关系。因此完成冒泡排序的总交换次数等于初始逆序对数。

这个结论要求交换的是“相邻逆序元素”。选择排序一次可能跨过多个元素，交换次数就不等于逆序对数。2025 年 CSP-J 单选题考查过排序交换与次序变化，遇到“交换次数”要先识别算法。

四、稳定性看的是相等记录

假设学生记录按分数排序，两名同分学生在排序前的顺序是 A₁,A₂。排序后仍保持 A₁ 在 A₂ 前面，这个排序就是稳定的。

• 常见稳定实现：冒泡排序、插入排序、归并排序；
• 常见不稳定实现：选择排序、快速排序、堆排序。

“稳定”不是指程序不会出错，也不是指数据不会移动。只含互不相同数字时，看不出稳定与否，必须给相同关键字加原始编号再观察。

算法的某些改写可能改变稳定性。例如冒泡时若连相等元素也交换，就会破坏原顺序。因此真题若给出具体代码，应以代码行为为准，而不是机械背表格。

五、sort 的区间必须看清

sort(a,a+n) 对左闭右开区间 [a,a+n) 排序，含开头元素但不含末尾指针 a+n。它不会删除重复值。

调用前要确认有效元素个数和右端点，sort(a,a+n-1) 会漏掉最后一个有效元素。相等元素在排序后仍会全部保留；sort 不负责去重。现行入门级大纲明确列出 sort，这里掌握排序区间和结果即可。

六、二分查找真正找的是“分界线”

二分查找的前提是查找区间已经按相应规则有序。升序数组中，取中点 mid 后：若 a[mid] 小于目标，目标只可能在右半边；若更大，目标只可能在左半边；若相等即可找到。

手写二分时不要混用两套区间约定。若使用闭区间 [l,r]，循环常为 l<=r；若使用左闭右开 [l,r)，循环常为 l<r。每轮都要保证区间严格缩小，否则容易死循环。

找最大值和二分查找的比较次数

在 N 个数中找最大值，每次比较最多只能淘汰一个“可能成为最大值”的候选。要从 N 个候选缩减到 1 个，至少需要 N-1 次比较；顺序扫描恰好能达到这个下界。

二分查找每比较一次就把候选区间大约减半。1000 个元素最多比较 10 次，因为 2⁹=512<1000≤1024=2¹⁰。题目问“最多”时，要按最不利的查找过程计算，不能只看平均情况。

七、阅读排序程序的固定顺序

1. 抄出排序后的有效区间，保留重复值；
2. 确认二分前数据已经有序；
3. 写清二分区间是 [l,r] 还是 [l,r)；
4. 每轮检查区间是否严格缩小，目标不存在时返回什么。

2021—2025 年 CSP-J 几乎每年都有排序或二分相关选择、阅读、完善内容。这里不要求把每种复杂度背成表，而要能准确追踪“排序—有效区间—边界”的数据变化。

今日选择题

第 1～4 题为 2021～2025 年 CSP-J 第一轮单选原题；第 5 题补计数排序，第 6～8 题巩固手写二分查找。

1. 【CSP-J 2021·第 4 题】 以比较作为基本运算，在 N 个数中找出最大数，最坏情况下所需的最少比较次数是（　）。

   A. N²　 B. N　 C. N-1　 D. N+1

2. 【CSP-J 2022·第 12 题】 以下排序算法的常见实现中，哪个选项的说法是错误的（　）。

   A. 冒泡排序通常是稳定的
   B. 简单选择排序通常是稳定的
   C. 简单插入排序通常是稳定的
   D. 归并排序可以实现为稳定排序

3. 【CSP-J 2024·第 9 题】 有序表中有 1000 个元素，使用二分查找寻找元素 x，最多需要比较（　）次。

   A. 25　 B. 10　 C. 7　 D. 1

4. 【CSP-J 2025·第 12 题】 对数组 {6,1,5,2,4} 进行升序冒泡排序，需要进行（　）次元素交换。

   A. 5　 B. 6　 C. 7　 D. 8

5. 关于计数排序，下列说法正确的是（　）。

   A. 它必须不断比较相邻元素
   B. 它先统计各个值出现的次数，适合值域较小的整数数据
   C. 它只能处理没有重复值的数据
   D. 数据值域越大，它占用的计数空间一定越少

主题程序阅读

阅读下面的程序：

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

int main() {
    int a[] = {1, 3, 5, 7, 9, 11, 13};
    int l = 0, r = 6, x = 9, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x) {
            ans = mid;
            break;
        }
        if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

6. 第一次进入循环时，mid 的值是（　）。

   A. 2　 B. 3　 C. 4　 D. 6

7. 程序输出（　）。

   A. 3　 B. 4　 C. 5　 D. 9

8. 若把 x 改为 10，程序会输出 -1。（判断对错）

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

int main() {
    int a[] = {1, 3, 5, 7, 9, 11, 13};
    int l = 0, r = 6, x = 9, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x) {
            ans = mid;
            break;
        }
        if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}