CSP-J 卷

以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

某同学用冒泡排序对数组 {$6, 1, 5, 2, 4$} 进行升序排序，请问需要进行多少次元素交换？（ ）

冒泡排序算法的伪代码如下：

输入：数组 $L$，$n\ge 1$。输出：按非递减顺序排序的 $L$。

算法 BubbleSort：

1  FLAG ← n    //标记被交换的最后元素位置
2  while FLAG > 1 do
3      k ← FLAG - 1
4      FLAG ← 1
5      for j = 1 to k do
6          if L(j) > L(j + 1) then do
7              L(j) ↔ L(j + 1)
8              FLAG ← j

对 $n$ 个数用以上冒泡排序算法进行排序，最少需要比较多少次？（ ）

排序算法是稳定的（Stable Sorting），就是指排序算法可以保证，在待排序数据中有两个相等记录的关键字 R 和 S（R 出现在 S 之前），在排序后的列表中 R 也一定在 S 前。下面关于排序稳定性的描述，正确的是（ ）。

对包含 n 个元素的数组进行冒泡排序，平均时间复杂度一般为（ ）。

对 N 个元素的数组执行插入排序算法，通常的时间复杂度是 $O(N^2)$。

归并排序的时间复杂度是 $O(N \log N)$。

插入排序在最好情况下的时间复杂度是（ ）。

对 int a[] = {2,0,2,4,3,1,6}，执行第一趟选择排序处理后 a 中数据变为 {0,2,2,4,3,1,6}。

如果待排序数据不能都装进内存，需要使用外排序算法。

关于直接插入排序，下列说法错误的是（ ）。

下列程序横线处，应该输入的是（ ）。

01#include<iostream>
02using namespace std;
03int n,a[10001];
04void swap(int &a,int &b)
05{
06    int t=a;
07    a=b;
08    b=t;
09}
10int main()
11{
12    cin>>n;
13    for(int i=1;i<=n;i++)
14        cin>>a[i];
15    for(int i=n;i>1;i--)
16        for(int j=1;j<i;j++)
17            if(a[j]>a[j+1])
18                ____________;
19    for(int i=1;i<=n;i++)
20        cout<<a[i]<<" ";
21    cout<<endl;
22    return 0;
23}

关于几种排序算法的说法，下面说法错误的是（ ）。

插入排序算法中，平均时间复杂度是 $O(n^2)$，最坏的情况逆序情况下，达到最大时间复杂度。

在排序算法中，稳定性指的是（ ）。

下面代码实现了冒泡排序函数，则横线上应填写（ ）。

01//交换数组arr的第i个元素和第j个元素
02void swap(vector<int> &arr, int i, int j) {
03    int tmp = arr[i];
04    arr[i] = arr[j];
05    arr[j] = tmp;
06}
07
08int bubble_sort(vector<int> &arr) {
09    for (int i = arr.size() - 1; i > 0; i--) {
10        bool flag = false; // 标志位
11        ____________{    // 在此处填入代码
12            if(arr[j] > arr[j + 1]) {
13                swap(arr, i, j);
14                flag = true;
15            }
16        }
17        if(!flag)
18            break; // 此轮"冒泡"未交换任何元素
19    }
20}
21

冒泡排序算法在最坏情况下的时间复杂度为（ ）。

选择排序是稳定的排序算法。

插入排序的时间复杂度总是比冒泡排序低。

下面关于排序算法（冒泡排序、插入排序和选择排序）的描述中，不正确的是（ ）。

冒泡排序的第一轮操作是从左到右遍历数组，通过两两比较相邻元素，将当前最大的元素移动到末尾。给定数组 arr[]={4, 1, 3, 1, 5, 2}，执行第一轮冒泡排序后数组 arr 中的内容为（ ）。

下面代码实现了插入排序函数，则横线上应填写（ ）。

01void insertion_sort(vector<int> &nums) {
02    for (int i = 1; i < nums.size(); i++) {
03        ____________   {   // 在此处填入代码
04        while (j >= 0 && nums[j] > base)
05            nums[j + 1] = nums[j];
06        j--;
07    }
08    nums[j + 1] = base;
09    }
10}

冒泡排序的平均时间复杂度为 $O(n^2)$，但最优情况下为 $O(n)$。

冒泡排序和插入排序都是稳定的排序算法。

下面关于排序稳定性的描述，正确的是（ ）。

对数组 arr[]={5, 3, 8, 1} 进行升序排序，执行第一轮冒泡排序后数组 arr 中的内容为（ ）。

插入排序在最好情况（已有序）下的时间复杂度是 $O(n^2)$。

以下哪种情况是使用插入排序的合适场景?

无论初始数组是否有序,选择排序都执行 $O(n^2)$ 次比较。

关于排序算法的稳定性，以下说法错误的是（ ）。

下面代码试图实现选择排序，使其能对数组 nums 排序为升序，则横线上应分别填写（ ）。

01void selectionSort(vector<int>& nums) {
02    int n = nums.size();
03    for (int i = 0; i < n - 1; ++i) {
04        int minIndex = i;
05        for (int j = i + 1; j < n; ++j) {
06            if ( ____________ ) {    // 在此处填入代码
07                minIndex = j;
08            }
09        }
10        ____________; // 在此处填入代码
11    }
12}

关于插入排序的时间复杂度，下列说法正确的是（ ）。

虽然插入排序的时间复杂度为 $O(n^2)$，但由于单元操作相对较少，因此在小数据量的排序任务中非常受欢迎。

对如下 $4$ 个扑克牌进行排序，

01struct Card {
02    int value;
03    char suit;  // 花色
04};
05
06Card cards[4] = {{5,'A'}, {3,'B'}, {5,'C'}, {3,'D'}};

使用某排序算法按 value 排序后，结果为：{3,'D'}，{3,'B'}，{5,'A'}，{5,'C'}，则这个排序算法是稳定的吗？

小杨在对“能量晶石”按亮度进行排序。如果两块晶石亮度相同，他希望保持它们在原始序列中的相对顺序。下列关于排序算法稳定性的说法，错误的是（ ）。