阅读3:

1  #include <iostream>
2  #include <vector>
3  
4  using namespace std;
5  
6  void merge(vector<int>& arr, int l, int m, int r) {
7      int n1 = m - l + 1;
8      int n2 = r - m;
9  
10     vector<int> L(n1), R(n2);
11 
12     for (int i = 0; i < n1; i++)
13         L[i] = arr[l + i];
14     for (int i = 0; i < n2; i++)
15         R[i] = arr[m + 1 + i];
16 
17     int i = 0, j = 0, k = l;
18     while (i < n1 && j < n2) {
19         if (L[i] <= R[j]) {
20             arr[k] = L[i];
21             i++;
22         } else {
23             arr[k] = R[j];
24             j++;
25         }
26         k++;
27     }
28 
29     while (i < n1) {
30         arr[k] = L[i];
31         i++;
32         k++;
33     }
34 
35     while (j < n2) {
36         arr[k] = R[j];
37         j++;
38         k++;
39     }
40 }
41 
42 void mergeSort(vector<int>& arr, int l, int r) {
43     if (l >= r)
44         return;
45 
46     int m = l + (r - l) / 2;
47     mergeSort(arr, l, m);
48     mergeSort(arr, m + 1, r);
49     merge(arr, l, m, r);
50 }
51 
52 int main() {
53     int n;
54     cin >> n;
55     vector<int> arr(n);
56     for (int i = 0; i < n; i++) {
57         cin >> arr[i];
58     }
59 
60     mergeSort(arr, 0, n - 1);
61 
62     for (int i = 0; i < n; i++) {
63         cout << arr[i] << " ";
64     }
65     cout << endl;
66 
67     return 0;
68 }

判断题

1. 如果输入的数组已经有序，那么程序的输出不会改变数组的顺序。（ ）{{ select(1) }}

• 正确
• 错误

2. 此程序的最坏时间复杂度是O(n^2)。（ ）{{ select(2) }}

• 正确
• 错误

3. 此算法会基于原数组排序，不需要开辟额外的存储空间。（ ）{{ select(3) }}

• 正确
• 错误

单选题

4. 如果将第 48 行代码 mergeSort(arr, m + 1, r); 修改为 mergeSort(arr, l, r);，那么程序将如何表现？（ ）{{ select(4) }}

• 正常工作，输出排序后的数组
• 导致程序崩溃或死循环
• 输出错误的排序结果
• 输出与原程序相同的结果

5. 如果输入数组为 [10, -1, 3, 7]，程序的输出将为（ ）{{ select(5) }}

• -1 3 7 10
• 10 7 3 -1
• -1 10 3 7
• 7 -1 3 10

6. 对于一个包含 16 个元素的数组，归并排序的递归调用的最大层数是多少？（ ）{{ select(6) }}

• 2
• 4
• 5
• 16