#cr001. 插入排序

插入排序

插入排序

题目描述

​ 给定 n 个整数 xix_i,请使用插入排序(Insertion Sort) 的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。

算法概念

​ 插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是将待排序序列分为已排序和未排序两部分,每次从未排序部分取出第一个元素,将其插入到已排序部分的正确位置,使得已排序部分始终保持有序。

算法原理与步骤

  1. 初始时,将第一个元素视为已排序部分(下标 1 到 1)。
  2. 从第二个元素开始(下标 i = 2 到 n),依次将当前元素 x = a[i] 插入到已排序部分。
  3. 在已排序部分(下标 1 到 i-1)中从后往前扫描,若遇到比 x 大的元素,则将该元素向后移动一位,为 x 腾出位置。
  4. 当遇到第一个不大于 x 的元素或到达序列开头时,停止移动,将 x 放入该位置(即 a[j+1] = x)。
  5. 重复上述步骤,直到所有元素都插入完成,序列完全有序。

输入格式

​ 第一行一个正整数 n,表示数字个数。 ​ 第二行 n 个整数,每个数在 int 范围内。

输出格式

​ 一行,输出排序后的 n 个整数,相邻数字用空格隔开。

输入输出样例

5
3 1 2 1 3
1 1 2 3 3

数据规模与约定

​ 1 ≤ n ≤ 5000

​ 数值范围:-10^9 ≤xi x_i ≤ 10^9

​ 时间限制:1 秒(冒泡排序最坏 O(n^2),但 n=5000 时约 2.5×10^7 次比较,配合优化通常可轻松通过)

提示

​ 代码提示:

// 插入排序
for (int i = 1; i <= ?; i++) {
    int j;
    int x = a[i];  // 当前待插入的元素
    // 在已排序部分(1 ~ i-1)中从后往前扫描
    for (j = ?; j >= ?; j--) {
        // TODO: 如果 a[j] > x,则将 a[j] 向后移动一位
        // 提示: a[j+1] = a[j];
        // 否则(a[j] <= x),停止移动,跳出循环
    }
    // 将 x 插入到正确位置
    a[j + 1] = x;
}

​ 运用提示:

​ 插入排序的核心在于“挪位”操作:将比 x 大的元素依次后移,最终将 x 放入空出的位置。

​ 注意内层循环从后往前扫描,边界条件 j >= 1 防止越界。

​ 如果当前元素 a[j] 不大于 x,则说明找到了插入位置,可以提前结束内层循环。

​ 数组下标从 1 开始,因此插入位置为 j+1(当 j 退出循环时,j 可能是 0 或第一个不大于 x 的位置)