#cr001. 插入排序
插入排序
插入排序
题目描述
给定 n 个整数 ,请使用插入排序(Insertion Sort) 的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。
算法概念
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是将待排序序列分为已排序和未排序两部分,每次从未排序部分取出第一个元素,将其插入到已排序部分的正确位置,使得已排序部分始终保持有序。
算法原理与步骤
- 初始时,将第一个元素视为已排序部分(下标 1 到 1)。
- 从第二个元素开始(下标 i = 2 到 n),依次将当前元素 x = a[i] 插入到已排序部分。
- 在已排序部分(下标 1 到 i-1)中从后往前扫描,若遇到比 x 大的元素,则将该元素向后移动一位,为 x 腾出位置。
- 当遇到第一个不大于 x 的元素或到达序列开头时,停止移动,将 x 放入该位置(即 a[j+1] = x)。
- 重复上述步骤,直到所有元素都插入完成,序列完全有序。
输入格式
第一行一个正整数 n,表示数字个数。 第二行 n 个整数,每个数在 int 范围内。
输出格式
一行,输出排序后的 n 个整数,相邻数字用空格隔开。
输入输出样例
5
3 1 2 1 3
1 1 2 3 3
数据规模与约定
1 ≤ n ≤ 5000
数值范围:-10^9 ≤≤ 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 的位置)