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

建议用时：22～28 分钟。请先打开今日知识卡完成复习，再独立提交本页答案。

今日学习资料

• 打开今日蓝白学习页
• 下载今日 PDF

复习目标：理解常见基础排序的过程与稳定性，掌握冒泡交换次数与逆序对的关系，并能追踪手写二分查找。

今日练习

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

{{ select(1) }}

• $N^2$
• $N$
• $N-1$
• $N+1$

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

{{ select(2) }}

• 冒泡排序通常是稳定的
• 简单选择排序通常是稳定的
• 简单插入排序通常是稳定的
• 归并排序可以实现为稳定排序

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

{{ select(3) }}

• 25
• 10
• 7
• 1

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

{{ select(4) }}

• 5
• 6
• 7
• 8

5. 【大纲内巩固】关于计数排序，下列说法正确的是（　）。

{{ select(5) }}

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

主题程序阅读

阅读下面的程序：

#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 的值是（　）。

{{ select(6) }}

• 2
• 3
• 4
• 6

7. 程序输出（　）。

{{ select(7) }}

• 3
• 4
• 5
• 9

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

{{ select(8) }}

• 正确
• 错误