#xp001. 选择排序(交换式)

选择排序(交换式)

选择排序(交换式)

题目描述

​ 给定 n 个整数 x_i,请使用**选择排序(交换式)**的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。

算法概念

​ 选择排序(Selection Sort)是一种简单直观的排序算法。其基本思想是:每次从待排序序列中选出最小元素,放到已排序序列的末尾。

​ 本题采用一种常见的实现方式:在每一轮中,用当前位置的元素与后面所有元素逐一比较,一旦发现更小元素就立即交换,从而保证当前位置最终存放的是未排序部分的最小值。该版本虽然交换次数较多,但逻辑直接,适合初学者理解选择排序的核心思想。另一种更高效的标准选择排序会先记录最小下标,最后只交换一次,将在后续练习中出现。

算法原理与步骤

  1. 外层循环:从第 1 个位置到第 n-1 个位置,依次确定每个位置上的最终元素(即未排序部分的最小值)。
  2. 内层循环:对于当前位置 i,遍历其后的所有位置 j(从 i+1 到 n),将 a[j] 与 a[i] 比较。
  3. 若 a[j] 小于 a[i],则立即交换 a[i] 和 a[j]。此操作使得 a[i] 在遍历过程中始终为当前已扫描过的元素中的最小值。
  4. 因为每一次发现更小值都会交换,所以每轮内层循环可能进行多次交换,但最终效果与标准选择排序一致:将最小值放到位置 i。
  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 < 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 开始,循环边界需仔细检查,防止越界。