#xp001. 选择排序(交换式)
选择排序(交换式)
选择排序(交换式)
题目描述
给定 n 个整数 x_i,请使用**选择排序(交换式)**的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。
算法概念
选择排序(Selection Sort)是一种简单直观的排序算法。其基本思想是:每次从待排序序列中选出最小元素,放到已排序序列的末尾。
本题采用一种常见的实现方式:在每一轮中,用当前位置的元素与后面所有元素逐一比较,一旦发现更小元素就立即交换,从而保证当前位置最终存放的是未排序部分的最小值。该版本虽然交换次数较多,但逻辑直接,适合初学者理解选择排序的核心思想。另一种更高效的标准选择排序会先记录最小下标,最后只交换一次,将在后续练习中出现。
算法原理与步骤
- 外层循环:从第 1 个位置到第 n-1 个位置,依次确定每个位置上的最终元素(即未排序部分的最小值)。
- 内层循环:对于当前位置 i,遍历其后的所有位置 j(从 i+1 到 n),将 a[j] 与 a[i] 比较。
- 若 a[j] 小于 a[i],则立即交换 a[i] 和 a[j]。此操作使得 a[i] 在遍历过程中始终为当前已扫描过的元素中的最小值。
- 因为每一次发现更小值都会交换,所以每轮内层循环可能进行多次交换,但最终效果与标准选择排序一致:将最小值放到位置 i。
- 重复上述过程,直到所有位置确定,序列完全有序。
输入格式
第一行一个正整数 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 < n; i++) {
// 内层循环:遍历 i 之后的所有元素
for (int j = i + 1; j <= n; j++) {
// TODO: 如果 a[j] 比 a[i] 小,则交换它们
// 提示:使用 swap(a[i], a[j])
}
}
运用提示:
该算法的核心特点是“即时交换”:每次发现逆序(a[j] < a[i])就立即进行交换,使得 a[i] 在遍历过程中不断更新为当前最小值。
虽然这种方式比标准选择排序(只记录最小下标,最后交换一次)交换次数更多,但逻辑更直观,适合初学者理解“选择最小元素”的过程。
注意内层循环从 i+1 开始,保证只与未排序部分比较;外层循环到 n-1 结束,最后一个元素无需比较。
数组下标从 1 开始,循环边界需仔细检查,防止越界。