#xp002. 选择排序(标准式)
选择排序(标准式)
选择排序(标准式)
题目描述
给定 n 个整数 ,请使用标准选择排序(Selection Sort) 的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。
算法概念
标准选择排序是一种改进的选择排序实现方式。与交换式选择排序每轮多次交换不同,标准版在每一轮中只记录未排序部分的最小值下标,内层循环结束后再将该最小值与当前位置交换一次。这样大幅减少了交换次数,提高了效率,更符合选择排序“选择最小元素”的原始定义。
算法原理与步骤
- 外层循环:从第 1 个位置到第 n-1 个位置,依次确定每个位置上的最终元素(即未排序部分的最小值)。
- 内层循环:对于当前位置 i,首先假设 a[i] 为最小值,用变量 x 记录其下标(x = i)。然后遍历其后的所有位置 j(从 i+1 到 n),若 a[j] 小于 a[x],则将 x 更新为 j(仅记录下标,不交换)。
- 内层循环结束后,x 指向未排序部分的最小值所在位置。
- 若 x 不等于 i,则交换 a[i] 和 a[x],将最小值放到正确位置。
- 重复上述过程,直到所有位置确定,序列完全有序。
与交换式选择排序的区别:交换式在发现 a[j] < a[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++) {
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()),但标准版交换次数大幅减少,在处理大型数据或元素交换代价较高时优势明显。
注意内层循环中只更新下标,不要进行交换操作,否则就变回交换式了。
最后判断 minIndex != i 再交换,避免不必要的操作。