当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

2.

01 #include<iostream>
02 using namespace std;
03 int a[100005], b[100005], n, m;
04 void very_quick_sort(int l, int r, int p, int q){
05 		if(l >= r || p > q){ // ①
06 		return;
07 }
08 int mid = (l + r) / 2;
09 int p0 = p - 1;
10 int q0 = q + 1;
11 for(int i = p;i <= q;i ++){
12 		if(a[i] > mid) b[++ p0] = a[i];
13 		else b[-- q0] = a[i];
14 }
15 for(int i = p;i <= q;i ++)
16 		a[i] = b[i];
17 very_quick_sort(mid + 1, r, p, p0);
18 very_quick_sort(l, mid, q0, q);
19 }
20 int main(){
21     cin >> n >> m;
22     for(int i = 1;i <= n;i ++)
23         cin >> a[i];
24     very_quick_sort(1, m, 1, n);
25 // ②
26     for(int i = 1;i <= n;i ++)
27         cout << a[i] << " ";
28     cout << endl;
29     return 0;
30 }

保证输入的 𝒏 不超过 $𝟏𝟎^𝟓$，𝒎 不超过 $𝟏𝟎^𝟗$，且 𝟏 ≤ 𝒂𝟏, 𝒂𝟐, ⋯ , 𝒂𝒏 ≤ 𝒎。完成下面的

判断题和单选题

判断题

22. 上述代码实现了一种排序算法，可以将 a 数组按照从小到大的顺序排序。（ ）{{ select(22) }}

• 正确
• 错误

23. 如果在程序开始之前向 b 数组里写入数据（保证不会发生数组越界），则上述代码的输出不会发生变化。 （ ）{{ select(23) }}

• 正确
• 错误

24. 若 𝑛 = 𝑚，存在某种数据构造方式，使得上述代码运行的时间复杂度为 $𝑂(𝑛^2 )$，这是因为算法本身是对快速排序的改进，但是这种改进不能避免由于对数组的划分不够均等而在极端数据下导致复杂度发生退化。 （ ）{{ select(24) }}

• 正确
• 错误

25. 如果将 ① 处的 l >= r 条件删除（同时删除 || 使得程序能正常编译运行，下同），程序的时间复杂度不会发生变化；而将 p > q 条件删除，程序在某些数据下的运行效率将会明显降低。 （ ）{{ select(25) }}

• 正确
• 错误

选择题

26. 不认为 𝑛, 𝑚 同阶，即可能出现 𝑛 远大于 𝑚 或者 𝑚 远大于 𝑛 的情况。则该程序的最坏时间复杂度为（ ）。{{ select(26) }}

• $o(𝑛^2 + 𝑚^2 )$
• $o(m log m)$
• $o(m log n)$
• $o(n log m)$

27. 若输入数据为：

10 10

10 4 5 2 2 3 1 5 8 3

那么在程序执行到 ② 位置时， b 数组 内的值为 （）。{{ select(27) }}

• [10,8,3,5,1,3,2,2,5,4]
• [3,5,1,3,2,2,5,4,10,8]
• [10,8,5,5,4,3,3,2,2,1]
• [1,2,2,3,3,4,5,5,8,10]