#xp002. 选择排序(标准式)

选择排序(标准式)

选择排序(标准式)

题目描述

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

算法概念

​ 标准选择排序是一种改进的选择排序实现方式。与交换式选择排序每轮多次交换不同,标准版在每一轮中只记录未排序部分的最小值下标,内层循环结束后再将该最小值与当前位置交换一次。这样大幅减少了交换次数,提高了效率,更符合选择排序“选择最小元素”的原始定义。

算法原理与步骤

  1. 外层循环:从第 1 个位置到第 n-1 个位置,依次确定每个位置上的最终元素(即未排序部分的最小值)。
  2. 内层循环:对于当前位置 i,首先假设 a[i] 为最小值,用变量 x 记录其下标(x = i)。然后遍历其后的所有位置 j(从 i+1 到 n),若 a[j] 小于 a[x],则将 x 更新为 j(仅记录下标,不交换)。
  3. 内层循环结束后,x 指向未排序部分的最小值所在位置。
  4. 若 x 不等于 i,则交换 a[i] 和 a[x],将最小值放到正确位置。
  5. 重复上述过程,直到所有位置确定,序列完全有序。

​ 与交换式选择排序的区别:交换式在发现 a[j] < a[i] 时立即交换,可能多次交换;标准版仅记录最小下标,每轮最多交换一次,效率更高。

输入格式

​ 第一行一个正整数 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++) {
    int minIndex = i;  // 记录最小值下标,初始设为 i
    // 内层循环:在 i 之后寻找更小值的下标
    for (int j = i + 1; j <= n; j++) {
        // TODO: 如果 a[j] 比 a[minIndex] 小,则更新 minIndex = j
        // 提示:只记录下标,不交换
    }
    // 若最小值不在当前位置,则交换一次
    if (minIndex != i) {
        // TODO: 交换 a[i] 和 a[minIndex]
        // 提示:使用 swap(a[i], a[minIndex])
    }
}

​ 运用提示:

​ 标准选择排序与交换式选择排序的核心区别:标准版只记录最小值的下标,内层循环结束后才进行交换,每轮最多交换一次;交换版则在每次发现逆序时立即交换,可能导致多次交换。

​ 虽然两者比较次数相同(均为 O(n2n^2)),但标准版交换次数大幅减少,在处理大型数据或元素交换代价较高时优势明显。

​ 注意内层循环中只更新下标,不要进行交换操作,否则就变回交换式了。

​ 最后判断 minIndex != i 再交换,避免不必要的操作。