完善程序（二）- 插入排序

题目描述

（插入排序） 对一段长度为 n 的数组使用插入排序的算法进行从小到大排序。

提示： 插入排序共有 n 轮，第 i 轮时使用二分查找找到第 i 个数字应该插入的位置，然后将 pos 到 i 位置向右移动，再将数字放入 pos 位置。保持数组下标 1 ∼ i 的元素有序，继续进行下一轮插入排序。

#include <iostream>
using namespace std;
const int maxn = 1000 + 5;
int a[maxn];
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        int temp = a[i];
        int l = 1, r = 【1】, pos; // 确定二分法的上界和下界
        while(l <= r) {
            int mid = (l + r) / 2;
            if(【2】) {
                l = mid + 1;
                pos = mid;
            } else {
                r = mid - 1;
            }
        }
        【3】 { // 向右移动，腾出位置
            a[j] = a[j-1];
        }
        a[pos] = 【4】;
    }
    for(int i = 1; i <= n; i++)
        cout << a[i] << endl;
}

第 1 题（15 分） 1 处应填：{{ select(1) }}

• A. n
• B. i
• C. i-1
• D. i+1

第 2 题（20 分） 2 处应填：{{ select(2) }}

• A. mid <= a[i]
• B. mid >= a[i]
• C. a[mid] <= a[i]
• D. a[mid] >= temp

第 3 题（25 分） 3 处应填：{{ select(3) }}

• A. for(int j = pos; j <= i-1; j++)
• B. for(int j = i-1; j >= pos; j--)
• C. for(int j = pos; j <= i; j++)
• D. for(int j = i; j >= pos; j--)

第 4 题（20 分） 4 处应填：{{ select(4) }}

• A. a[i]
• B. temp
• C. a[l]
• D. a[r]

第 5 题（20 分） 该算法的平均时间复杂度和最坏时间复杂度分别为：{{ select(5) }}

• A. O(n²), O(n²)
• B. O(n log n), O(n log n)
• C. O(n log n), O(n²)
• D. O(nⁿ), O(n²)