第 21 章 非比较排序与稳定性总表 · 知识细节练习

比较排序与非比较排序的区别是？

基于比较的排序算法，其最坏时间复杂度下界是？

计数/基数/桶排序能突破 $O(n \log n)$ 下界，原因是？

判断题：非比较排序的适用前提是值域有限且可枚举（计数）、元素有固定位权（基数）、值域可均分（桶）——前提不满足时它们无法工作或退化为灾难。

判断题：排序稳定性描述"相等元素的相对顺序在排序后是否保持不变"——它是 S 组初赛单选的高频考点。

下列排序算法中，属于非比较排序的是？

计数排序的核心思想是？

计数排序适用于？

计数排序的时间复杂度是？（$n$ 元素、值域 $k$）

关于计数排序的稳定性，正确的是？

判断题：计数排序需要 $O(k)$ 的计数数组和 $O(n)$ 的输出数组，是非原地排序。

判断题：值域 $10^9$ 时计数排序需要 $10^9$ 大小的数组，空间爆炸——此时不能直接使用计数排序。

对 {2, 1, 2, 0, 3} 做计数排序（值域 0~3），计数数组的最终状态是？

基数排序（LSD）的核心思想是？

LSD（最低位优先）与 MSD（最高位优先）的区别是？

判断题：LSD 基数排序每一轮（每个数位）都必须用稳定排序——否则高位排序会打乱低位已排好的相对顺序。

基数排序的时间复杂度是？（$n$ 元素、$d$ 位、每位基数 $k$）

判断题：LSD 基数排序整体是稳定排序。

基数排序最适合的场景是？

对 {53, 12, 41, 22} 做 LSD 基数排序，第一轮（个位）稳定排序后的顺序是？

桶排序的核心思想是？

桶排序中桶的划分通常依据？

桶排序的平均时间复杂度是？

桶排序的最坏情况是？

桶排序与计数排序的关系是？

判断题：桶排序的稳定性取决于桶内排序算法——桶内用稳定排序（如插入）则整体稳定。

桶排序最适合的场景是？

排序稳定性的准确定义是？

下列排序算法全部稳定的是？

下列排序算法全部不稳定的是？

判断题：判定稳定性的依据是"算法是否可能把相等的两个元素交换跨过彼此"——存在这种交换则不保证稳定。

多关键字排序（先按主关键字、同主关键字按次关键字）的正确做法是？

判断题：以下判定全部正确——"冒泡稳定、选择不稳定、插入稳定、快排不稳定、归并稳定、堆不稳定、基数稳定、朴素计数不稳定"。

关于时间复杂度，正确的总表是？

值域 $k$ 与 $n$ 同阶（如 10 万学生成绩 0~100 万）时，计数排序复杂度 $O(n+k)$ 与快排 $O(n \log n)$ 相比？

对 100 万名学生按成绩（0~750 分）排序，最佳选择是？

大数据量且要求稳定排序（内存充足），可选？

关于空间开销，正确的是？

判断题：以下选择全部合理——"值域小用计数；位数固定用基数；均匀分布用桶；通用用快排；稳定需求用归并；内存紧张用堆"。

某排序过程描述为"统计每个分数的人数，再按分数从低到高依次列出所有学生"——这是？

判断题：以下总表正确——"原地且稳定：冒泡、插入；原地不稳定：选择、快排、堆；非原地稳定：归并、基数、计数；非原地不稳定：朴素桶（桶内不稳定时）"。

判断题：实际工程中快排（及其变体）最常用——原地、平均快、缓存友好；堆排序虽同是 $O(n \log n)$ 但跳跃访问偏慢。

判断题：STL sort 常用内省排序（快排 + 小规模插入排序 + 递归过深转堆排序）——混合多种算法取长补短。

内存装不下全部数据时的外部排序，核心方法是？

判断题：C++ sort 不保证稳定（需要稳定时用 stable_sort）——stable_sort 常用归并实现。

判断题：值域 $10^9$ 的整数序列不能用朴素计数排序——$10^9$ 大小的计数数组内存装不下。

判断题：LSD 基数排序若某一轮用了不稳定排序，最终结果可能错误——因为低位已排好的相等元素相对顺序会被破坏。

判断题：所有元素落入同一个桶时，桶排序退化为桶内排序的复杂度（桶内用快排则最坏 $O(n^2)$）。

判断题："快排稳定""堆排序稳定""基数排序不稳定"——这三个说法中恰好两个正确。

判断题：以下结论全部正确——"比较排序最坏下界 $O(n \log n)$；计数排序 $O(n+k)$ 依赖值域；LSD 基数排序每轮稳定；桶排序平均 $O(n)$ 但最坏可退化"。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {2, 1, 2, 0, 3};
05    int cnt[4] = {0};
06    for (int i = 0; i < 5; i++) cnt[a[i]]++;
07    for (int i = 0; i < 4; i++) cout << cnt[i] << " ";
08    return 0;
09}

单选题：程序输出是？（0~3 各值出现的次数）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {3, 1, 2, 1, 3, 0};
05    int cnt[4] = {0};
06    for (int i = 0; i < 6; i++) cnt[a[i]]++;
07    int k = 0;
08    for (int v = 0; v < 4; v++)                 // 按值从小到大展开
09        for (int j = 0; j < cnt[v]; j++) a[k++] = v;
10    for (int i = 0; i < 6; i++) cout << a[i] << " ";
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {2, 1, 2, 0, 3};
05    int cnt[4] = {0};
06    for (int i = 0; i < 5; i++) cnt[a[i]]++;
07    for (int v = 1; v < 4; v++) cnt[v] += cnt[v - 1];   // 前缀和：cnt[v] = 值 <= v 的元素个数
08    for (int v = 0; v < 4; v++) cout << cnt[v] << " ";
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct P { int v; char tag; };
04P a[4] = {{2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}};
05P out[4];
06int main() {
07    int cnt[3] = {0};
08    for (int i = 0; i < 4; i++) cnt[a[i].v]++;
09    for (int v = 1; v <= 2; v++) cnt[v] += cnt[v - 1];   // cnt[v] = 值 <= v 的个数
10    for (int i = 3; i >= 0; i--) {                        // 倒序回填 → 稳定
11        out[--cnt[a[i].v]] = a[i];
12    }
13    for (int i = 0; i < 4; i++) cout << out[i].v << out[i].tag << " ";
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int a[5] = {3, 0, 2, 1, 2};
04int cnt[4] = {0};
05int main() {
06    for (int i = 0; i < 5; i++) ______;      // 统计频次
07    for (int v = 0; v < 4; v++)
08        for (int j = 0; j < cnt[v]; j++) cout << v << " ";
09    return 0;
10}

单选题：横线处应填入？（使输出为 0 1 2 2 3）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {5, 8, 5, 7};
05    int mx = 0;
06    for (int i = 0; i < 4; i++) mx = max(mx, a[i]);
07    cout << mx + 1;          // 计数数组所需大小
08    return 0;
09}

单选题：程序输出是？（值 0~8 共 9 个位置）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {53, 12, 41, 22};
05    int bucket[10][4] = {0}, sz[10] = {0};
06    for (int i = 0; i < 4; i++) {
07        int d = a[i] % 10;                    // 个位
08        bucket[d][sz[d]++] = a[i];
09    }
10    int k = 0;
11    for (int d = 0; d < 10; d++)              // 按个位 0~9 收集
12        for (int j = 0; j < sz[d]; j++) a[k++] = bucket[d][j];
13    for (int i = 0; i < 4; i++) cout << a[i] << " ";
14    return 0;
15}

单选题：程序输出是？（按个位稳定排序后）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {41, 12, 22, 53};   // 个位已有序
05    int bucket[10][4] = {0}, sz[10] = {0};
06    for (int i = 0; i < 4; i++) {
07        int d = a[i] / 10 % 10;              // 十位
08        bucket[d][sz[d]++] = a[i];
09    }
10    int k = 0;
11    for (int d = 0; d < 10; d++)
12        for (int j = 0; j < sz[d]; j++) a[k++] = bucket[d][j];
13    for (int i = 0; i < 4; i++) cout << a[i] << " ";
14    return 0;
15}

单选题：程序输出是？（个位有序基础上按十位稳定排序）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {329, 457, 657, 839, 436};
05    // LSD：对个位、十位、百位各做一轮稳定"分配-收集"
06    for (int pos = 1; pos <= 100; pos *= 10) {
07        int bucket[10][5] = {0}, sz[10] = {0};
08        for (int i = 0; i < 5; i++) {
09            int d = a[i] / pos % 10;
10            bucket[d][sz[d]++] = a[i];
11        }
12        int k = 0;
13        for (int d = 0; d < 10; d++)
14            for (int j = 0; j < sz[d]; j++) a[k++] = bucket[d][j];
15    }
16    for (int i = 0; i < 5; i++) cout << a[i] << " ";
17    return 0;
18}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[3] = {21, 12, 30};
05    int bucket[10][3] = {0}, sz[10] = {0};
06    for (int i = 0; i < 3; i++) {
07        int d = a[i] % 10;
08        bucket[d][sz[d]++] = a[i];
09    }
10    int k = 0;
11    for (int d = 0; d < 10; d++)
12        for (int j = 0; j < sz[d]; j++) a[k++] = bucket[d][j];
13    cout << a[0] << " " << a[1] << " " << a[2];
14    return 0;
15}

单选题：程序输出是？（第一轮按个位后：个位 0、1、2）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {53, 12, 41, 22};
05    int bucket[10][4] = {0}, sz[10] = {0};
06    for (int i = 0; i < 4; i++) {
07        int d = ______;              // 取个位
08        bucket[d][sz[d]++] = a[i];
09    }
10    int k = 0;
11    for (int d = 0; d < 10; d++)
12        for (int j = 0; j < sz[d]; j++) a[k++] = bucket[d][j];
13    for (int i = 0; i < 4; i++) cout << a[i] << " ";
14    return 0;
15}

单选题：横线处应填入？（使输出为 41 12 22 53）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {25, 16, 9, 61};
05    // 两轮 LSD：个位、十位
06    for (int pos = 1; pos <= 10; pos *= 10) {
07        int bucket[10][4] = {0}, sz[10] = {0};
08        for (int i = 0; i < 4; i++) {
09            int d = a[i] / pos % 10;
10            bucket[d][sz[d]++] = a[i];
11        }
12        int k = 0;
13        for (int d = 0; d < 10; d++)
14            for (int j = 0; j < sz[d]; j++) a[k++] = bucket[d][j];
15    }
16    for (int i = 0; i < 4; i++) cout << a[i] << " ";
17    return 0;
18}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {45, 12, 78, 23, 91, 34};
05    int bkt[10][6] = {0}, sz[10] = {0};
06    for (int i = 0; i < 6; i++) {
07        int b = a[i] / 10;                 // 十位作桶号：0~9 桶
08        bkt[b][sz[b]++] = a[i];
09    }
10    int total = 0;
11    for (int b = 0; b < 10; b++) total += sz[b];
12    cout << total << " ";
13    for (int b = 0; b < 10; b++) if (sz[b]) cout << b << " ";
14    return 0;
15}

单选题：程序输出是？（元素总数 + 非空桶号）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int bkt[3] = {23, 21, 25};    // 桶 2 内元素（桶内用插入排序）
05    for (int i = 1; i < 3; i++) {
06        int t = bkt[i], j = i - 1;
07        while (j >= 0 && bkt[j] > t) { bkt[j + 1] = bkt[j]; j--; }
08        bkt[j + 1] = t;
09    }
10    for (int i = 0; i < 3; i++) cout << bkt[i] << " ";
11    return 0;
12}

单选题：程序输出是？（桶内插入排序后）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {34, 12, 25, 41, 8};
05    int bkt[10][5] = {0}, sz[10] = {0};
06    for (int i = 0; i < 5; i++) {
07        int b = a[i] / 10;                 // 十位作桶号
08        bkt[b][sz[b]++] = a[i];
09    }
10    for (int b = 0; b < 10; b++) {          // 桶内插入排序
11        for (int i = 1; i < sz[b]; i++) {
12            int t = bkt[b][i], j = i - 1;
13            while (j >= 0 && bkt[b][j] > t) { bkt[b][j + 1] = bkt[b][j]; j--; }
14            bkt[b][j + 1] = t;
15        }
16    }
17    for (int b = 0; b < 10; b++)            // 按桶序拼接
18        for (int j = 0; j < sz[b]; j++) cout << bkt[b][j] << " ";
19    return 0;
20}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {3, 15, 27, 40};
05    // 值域 0~49 均分 5 个桶：桶号 = 值 / 10
06    int bkt[5][4] = {0}, sz[5] = {0};
07    for (int i = 0; i < 4; i++) {
08        int b = ______;              // 计算桶号
09        bkt[b][sz[b]++] = a[i];
10    }
11    int total = 0;
12    for (int b = 0; b < 5; b++) total += sz[b];
13    cout << total;
14    return 0;
15}

单选题：横线处应填入？（使输出为 4——所有元素都分入桶中）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {1, 2, 1, 3};
05    int cnt[4] = {0};
06    for (int i = 0; i < 4; i++) cnt[a[i]]++;   // 计数 = 每值一桶
07    for (int v = 1; v <= 3; v++) cout << cnt[v] << " ";
08    return 0;
09}

单选题：程序输出是？（值 1、2、3 各出现次数——计数排序可看作"每值一个桶"）

01#include <bits/stdc++.h>
02using namespace std;
03// 桶排序：桶号 = a[i] / 10，值域 0~99

单选题：下列哪个输入会让桶排序退化为最坏情况（所有元素挤进同一个桶）？

01#include <bits/stdc++.h>
02using namespace std;
03struct P { int v; char tag; };
04P a[4] = {{2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}};
05int main() {
06    // 冒泡排序（稳定）
07    for (int i = 0; i < 3; i++)
08        for (int j = 0; j < 3 - i; j++)
09            if (a[j].v > a[j + 1].v) swap(a[j], a[j + 1]);
10    for (int i = 0; i < 4; i++) cout << a[i].v << a[i].tag << " ";
11    return 0;
12}

单选题：程序输出是？（稳定排序：相等元素保持原顺序）

01#include <bits/stdc++.h>
02using namespace std;
03struct P { int v; char tag; };
04P a[4] = {{2, 'a'}, {2, 'b'}, {1, 'c'}, {3, 'd'}};
05int main() {
06    // 选择排序（不稳定）：每次选最小换到前面
07    for (int i = 0; i < 3; i++) {
08        int m = i;
09        for (int j = i + 1; j < 4; j++)
10            if (a[j].v < a[m].v) m = j;
11        swap(a[i], a[m]);
12    }
13    for (int i = 0; i < 4; i++) cout << a[i].v << a[i].tag << " ";
14    return 0;
15}

单选题：程序输出是？（观察值相同的 2a、2b 相对顺序）

01#include <bits/stdc++.h>
02using namespace std;
03struct P { int major; int minor; };   // 主关键字、次关键字
04P a[4] = {{2, 3}, {1, 5}, {2, 1}, {1, 2}};
05int main() {
06    // 先按次关键字稳定排序，再按主关键字稳定排序
07    stable_sort(a, a + 4, [](P x, P y) { return x.minor < y.minor; });
08    stable_sort(a, a + 4, [](P x, P y) { return x.major < y.major; });
09    for (int i = 0; i < 4; i++) cout << a[i].major << "," << a[i].minor << " ";
10    return 0;
11}

单选题：程序输出是？（主关键字升序、同主关键字按次关键字升序）

01#include <bits/stdc++.h>
02using namespace std;
03struct P { int v; char tag; };
04P a[5] = {{2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}, {3, 'e'}};
05P out[5];
06int main() {
07    int cnt[4] = {0};
08    for (int i = 0; i < 5; i++) cnt[a[i].v]++;
09    for (int v = 1; v <= 3; v++) cnt[v] += cnt[v - 1];
10    for (int i = 4; i >= 0; i--) out[--cnt[a[i].v]] = a[i];
11    for (int i = 0; i < 5; i++) cout << out[i].v << out[i].tag << " ";
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct P { int v; char tag; };
04P a[4] = {{21, 'a'}, {11, 'b'}, {31, 'c'}, {22, 'd'}};
05P bucket[10][4]; int sz[10] = {0};
06int main() {
07    for (int i = 0; i < 4; i++) {          // 按个位稳定分配-收集
08        int d = a[i].v % 10;
09        bucket[d][sz[d]++] = a[i];
10    }
11    int k = 0;
12    for (int d = 0; d < 10; d++)
13        for (int j = 0; j < sz[d]; j++) a[k++] = bucket[d][j];
14    for (int i = 0; i < 4; i++) cout << a[i].v << a[i].tag << " ";
15    return 0;
16}

单选题：程序输出是？（个位 1、1、1、2——桶内按原顺序收集 → 稳定）

01#include <bits/stdc++.h>
02using namespace std;
03struct P { int v; char tag; };
04int main() {
05    P a[4] = {{2, 'x'}, {1, 'a'}, {2, 'y'}, {1, 'b'}};
06    stable_sort(a, a + 4, [](P p, P q) { return p.v < q.v; });
07    for (int i = 0; i < 4; i++) cout << a[i].v << a[i].tag << " ";
08    return 0;
09}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 1000000;              // 100 万学生
05    int scoreMax = 750;           // 成绩 0~750
06    // 计数排序：数组大小 751，复杂度 O(n + 751)
07    cout << "counting " << n + scoreMax + 1;
08    return 0;
09}

判断题：100 万学生按成绩（0~750）排序，计数排序只需 751 大小的计数数组，复杂度 $O(n+751)$——此时计数排序远快于 $O(n \log n)$ 的比较排序。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    long long range = 1000000000LL;   // 值域 10^9
05    // 计数排序需要 range 大小的数组 → 内存爆炸
06    cout << (range > 100000000 ? "no-counting" : "counting");
07    return 0;
08}

单选题：程序输出是？（值域 $10^9$ 时计数数组约 4GB，开不下）

01#include <bits/stdc++.h>
02using namespace std;
03struct S { int score; int id; };   // 成绩 + 学号
04int main() {
05    // 需求：按成绩排序，同分按学号升序
06    // 做法：先按学号稳定排序，再按成绩稳定排序
07    cout << "stable needed";
08    return 0;
09}

判断题：同分保学号序——必须用稳定排序（或先学号后成绩的双关键字稳定排序）；直接用不稳定的 sort 可能打乱同分者的学号顺序。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 内存极紧张（几乎无额外空间）且要 O(n log n)
05    int n = 100000;
06    cout << "heapsort";     // 堆排序：O(1) 额外空间
07    return 0;
08}

判断题：内存极紧张时选堆排序（原地 $O(n \log n)$）；归并需要 $O(n)$ 辅助、计数需要 $O(k)$ 计数数组，都不合适。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 200000;
05    int a[200000] = {0};
06    // 同规模下实测：sort 常快于手写堆排序（缓存友好 vs 跳跃访问）
07    sort(a, a + n);
08    cout << "done";
09    return 0;
10}

判断题：同为 $O(n \log n)$，STL sort（内省排序）实际常快于堆排序——复杂度假定下常数与缓存行为差异显著。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 场景 A：0~1000 分成绩 → 计数
05    // 场景 B：10 位以内整数 1 亿个 → 基数（3~4 轮）
06    // 场景 C：通用整数 → sort
07    // 场景 D：稳定 + 大数据 → 归并 / stable_sort
08    cout << "A-count B-radix C-sort D-merge";
09    return 0;
10}

判断题：上述四种场景的算法选择全部合理。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int score[5] = {90, 80, 90, 70, 85};
05    int cnt[101] = {0};
06    for (int i = 0; i < 5; i++) cnt[score[i]]++;
07    // 前缀和：cnt[v] = 分数 <= v 的人数
08    for (int v = 1; v <= 100; v++) cnt[v] += cnt[v - 1];
09    cout << cnt[85];        // 分数 <= 85 的人数
10    return 0;
11}

单选题：程序输出是？（90、80、90、70、85 中 ≤85 的人数）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {12, 23, 34, 45, 56};
05    int cnt[10] = {0};
06    for (int i = 0; i < 5; i++) cnt[a[i] % 10]++;   // 统计个位分布
07    for (int d = 0; d < 6; d++) cout << cnt[d] << " ";
08    return 0;
09}

单选题：程序输出是？（个位 0~5 的出现次数）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string s[4] = {"banana", "apple", "cherry", "date"};
05    sort(s, s + 4);                  // 字典序
06    for (int i = 0; i < 4; i++) cout << s[i] << " ";
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int d[6] = {3, 9, 1, 7, 5, 2};
05    int k = 2;
06    priority_queue<int, vector<int>, greater<int>> q;   // 小根堆存最大的 k 个
07    for (int i = 0; i < 6; i++) {
08        if ((int)q.size() < k) q.push(d[i]);
09        else if (d[i] > q.top()) { q.pop(); q.push(d[i]); }
10    }
11    cout << q.top() << " "; q.pop();
12    cout << q.top();
13    return 0;
14}

单选题：程序输出是？（6 个数中最大的 2 个，从小到大）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 0~999 的整数：先按百位分桶（10 桶），桶内用计数排序（值域 100）
05    int a[5] = {123, 321, 231, 312, 213};
06    int bucket[10][5] = {0}, sz[10] = {0};
07    for (int i = 0; i < 5; i++) {
08        int b = a[i] / 100;              // 百位桶号
09        bucket[b][sz[b]++] = a[i];
10    }
11    cout << sz[1] << " " << sz[2] << " " << sz[3];   // 各桶元素数
12    return 0;
13}

单选题：程序输出是？（百位 1、2、3 的桶内元素数）

01#include <bits/stdc++.h>
02using namespace std;
03struct P { int v; int idx; };   // 值与原始下标
04P a[4] = {{2, 0}, {1, 1}, {2, 2}, {1, 3}};
05int main() {
06    stable_sort(a, a + 4, [](P x, P y) { return x.v < y.v; });
07    // 稳定排序后，相等元素的 idx 仍递增 → 顺序可追溯
08    for (int i = 0; i < 4; i++) cout << a[i].idx << " ";
09    return 0;
10}

单选题：程序输出是？（稳定排序后各元素的原始下标）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {2, 0, 1, 2, 1, 0};
05    int cnt[3] = {0};
06    for (int i = 0; i < 6; i++) ______;      // 统计各值出现次数
07    for (int v = 0; v < 3; v++) cout << cnt[v] << " ";
08    return 0;
09}

单选题：横线处应填入？（使输出为 2 2 2）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {1, 2, 1, 2};
05    int cnt[3] = {0};
06    for (int i = 0; i < 4; i++) cnt[a[i]]++;
07    for (int v = 1; v <= 2; v++) ______;     // 前缀和：cnt[v] = 值 <= v 的个数
08    cout << cnt[2];
09    return 0;
10}

单选题：横线处应填入？（使输出为 4）