排序算法（共 18 题）

单选题

1. 下面程序用于对 lstA 排序，使得偶数在前奇数在后，横线处应填入（ ）。

   bool isEven(int N) { return N % 2 == 0; }
   void sortA(int lstA[], int n) {
       for (int i = n-1; i > 0; i--) {
           for (int j = 0; j < i; j++) {
               if(__________________)
                   swap(lstA[j], lstA[j+1]);
           }
       }
   }
   

   {{ select(1) }}

• !isEven(lstA[j]) && isEven(lstA[j+1])
• isEven(lstA[j]) && !isEven(lstA[j+1])
• lstA[j] > lstA[j+1]
• lstA[j] < lstA[j+1]

2. 下面的排序算法都要处理多趟数据，哪种排序算法不能保证在下一趟处理时从待处理数据中选出最大或最小的数据？（ ）
   {{ select(2) }}

• 选择排序
• 快速排序
• 堆排序
• 冒泡排序

3. 在快速排序中，选择的主元素（pivot）会影响算法的（ ）。
   {{ select(3) }}

• 不影响
• 时间复杂度
• 空间复杂度
• 时间复杂度和空间复杂度

4. 下面关于排序算法的描述中，不正确的是（ ）。
   {{ select(4) }}

• 冒泡排序和插入排序都是稳定的排序算法
• 快速排序和归并排序都是不稳定的排序算法
• 冒泡排序和插入排序最好时间复杂度均为 O(n)
• 归并排序在最好、最坏和平均三种情况下的时间复杂度均为 O(n log n)

5. 假设快速排序算法的输入是一个长度为 n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（ ）描述的是在这种情况下快速排序行为。
   {{ select(5) }}

• 快速排序对于此类输入的表现最好，因为数组已经排序。
• 快速排序对于此类输入的时间复杂度是 O(n log n)。
• 快速排序对于此类输入的时间复杂度是 O(n²)。
• 快速排序无法对此类数组进行排序，因为数组已经排序。

6. 考虑以下 C++ 代码实现的快速排序算法，下面说法错误的是（ ）。

   int partition(vector<int>& arr, int low, int high) {
       int pivot = arr[high];
       int i = low - 1;
       for (int j = low; j < high; j++) {
           if (arr[j] < pivot) {
               i++;
               swap(arr[i], arr[j]);
           }
       }
       swap(arr[i+1], arr[high]);
       return i+1;
   }
   void quickSort(vector<int>& arr, int low, int high) {
       if (low < high) {
           int pi = partition(arr, low, high);
           quickSort(arr, low, pi-1);
           quickSort(arr, pi+1, high);
       }
   }
   

   {{ select(6) }}

• 快速排序通过递归对子问题进行求解。
• 快速排序的最坏时间复杂度是 O(n log n)。
• 快速排序是一个不稳定的排序算法。
• 在最优情况下，快速排序的时间复杂度是 O(n log n)。

7. 下述 C++ 代码实现了归并排序算法，下面说法正确的是（ ）。

   void merge(vector<int>& arr, int left, int mid, int right) {
       vector<int> temp(right-left+1);
       int i = left, j = mid+1, k = 0;
       while (i <= mid && j <= right) {
           if (arr[i] <= arr[j]) temp[k++] = arr[i++];
           else temp[k++] = arr[j++];
       }
       while (i <= mid) temp[k++] = arr[i++];
       while (j <= right) temp[k++] = arr[j++];
       for (int p = 0; p < k; p++) arr[left+p] = temp[p];
   }
   void mergeSort(vector<int>& arr, int left, int right) {
       if (left >= right) return;
       int mid = left + (right-left)/2;
       mergeSort(arr, left, mid);
       mergeSort(arr, mid+1, right);
       merge(arr, left, mid, right);
   }
   

   {{ select(7) }}

• 归并排序是一个不稳定的排序算法。
• 归并排序的时间复杂度在最优、最差和平均情况下都是 O(n log n)。
• 归并排序需要额外的 O(1) 空间。
• 对于输入数组 {12, 11, 13, 5, 6, 7}，代码输出结果为：7 6 5 13 12 11。

8. 下面的 C++ 代码用于对 lstA 排序，使得偶数在前奇数在后，横线处应填入（ ）。

   bool isEven(int N) { return N % 2 == 0; }
   void sortA(int lstA[], int n) {
       for (int i = n-1; i > 0; i--) {
           for (int j = 0; j < i; j++) {
               if(__________________)
                   swap(lstA[j], lstA[j+1]);
           }
       }
   }
   

   {{ select(8) }}

• !isEven(lstA[j]) && isEven(lstA[j+1])
• isEven(lstA[j]) && !isEven(lstA[j+1])
• lstA[j] > lstA[j+1]
• lstA[j] < lstA[j+1]

9. 下面关于快速排序的说法，正确的是（ ）。
   {{ select(9) }}

• 快速排序是稳定的排序算法
• 快速排序最坏情况时间复杂度为 O(n log n)
• 快速排序平均时间复杂度为 O(n log n)
• 快速排序在任何情况下都比插入排序快

10. 下述代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。

    void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
        int i = l, j = mid+1, k = l;
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= r) temp[k++] = arr[j++];
        for (int p = l; p <= r; p++) arr[p] = temp[p];
    }
    void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
        if (l >= r) return;
        int mid = l + (r-l)/2;
        mergeSort(arr, temp, l, mid);
        mergeSort(arr, temp, mid+1, r);
        merge(arr, temp, l, mid, r);
    }
    

    {{ select(10) }}

• 归并排序的平均复杂度是 O(n log n)
• 归并排序需要 O(n) 的额外空间
• 归并排序在最坏情况的时间复杂度是 O(n²)
• 归并排序适合大规模数据

判断题

11. 快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。
    {{ select(11) }}

• 正确
• 错误

12. 快速排序和归并排序都是稳定的排序算法。
    {{ select(12) }}

• 正确
• 错误

13. 归并排序的时间复杂度是 O(N log N)。
    {{ select(13) }}

• 正确
• 错误

14. 插入排序有时比快速排序时间复杂度更低。
    {{ select(14) }}

• 正确
• 错误

15. 快速排序和归并排序的平均时间复杂度均为 O(n log n)，且都是稳定排序。
    {{ select(15) }}

• 正确
• 错误

16. 快速排序的时间复杂度与输入是否有序无关，始终稳定为 O(n log n)。
    {{ select(16) }}

• 正确
• 错误

17. 归并排序算法的时间复杂度与输入是否有序无关，始终稳定为 O(n log n)。
    {{ select(17) }}

• 正确
• 错误

18. 冒泡排序和插入排序都是稳定的排序算法。
    {{ select(18) }}

• 正确
• 错误