CSP-J/S冲奖第20天：选择排序

摘要：定义：选择排序是一种简单直观的排序算法，每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。类比：就像整理书架时，每次都从剩下的书中找到最小的那本，放在正确的位置。特点：时间复杂度为 (O(n^2))，适合小规模数据。交换次数少，性能比冒泡排序略优

一、什么是选择排序？

定义：选择排序是一种简单直观的排序算法，每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。类比：就像整理书架时，每次都从剩下的书中找到最小的那本，放在正确的位置。特点：时间复杂度为 (O(n^2))，适合小规模数据。交换次数少，性能比冒泡排序略优。

二、选择排序的步骤

遍历未排序部分：从数组的第一个元素开始，假设当前位置为最小值。寻找最小值：在未排序部分中找到最小值的索引。交换元素：将找到的最小值与未排序部分的第一个元素交换位置。重复过程：缩小未排序部分的范围，直到整个数组有序。

三、代码实现

1. 升序排序

#include
usingnamespacestd;

intmain{
int arr = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < n - 1; i++) {
int minIndex = i; // 假设当前未排序部分的第一个元素是最小值
// 寻找未排序部分的最小值索引
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换最小值到已排序部分的末尾
swap(arr[i], arr[minIndex]);
}

// 输出排序后的数组
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;

return0;
}

运行结果：

11 12 22 25 64

2. 降序排序

#include
usingnamespacestd;

intmain{
int arr = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < n - 1; i++) {
int maxIndex = i; // 假设当前未排序部分的第一个元素是最大值
// 寻找未排序部分的最大值索引
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
// 交换最大值到已排序部分的末尾
swap(arr[i], arr[maxIndex]);
}

// 输出排序后的数组
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;

return0;
}

运行结果：

64 25 22 12 11

四、代码解析

外层循环：

控制已排序部分的边界（i 表示当前已排序部分的末尾）。

内层循环：

在未排序部分（从 i+1 到 n-1）中寻找最小值（或最大值）的索引。

交换操作：

将找到的最小值（或最大值）与未排序部分的第一个元素交换。

五、时间复杂度分析

时间复杂度：(O(n^2))（无论最好或最坏情况）。交换次数：(O(n))（比冒泡排序少，性能略优）。

六、竞赛注意事项

数据范围：如果 n 超过 10000，选择排序可能超时，建议使用 std::sort。选择排序代码简单，适合快速实现小规模排序。如果已排序部分和未排序部分同时寻找最小值和最大值，可以减少循环次数（进阶技巧）。输入n个学生的成绩，按升序输出。

参考代码：

#include
usingnamespacestd;

intmain{
int n;
cin >> n;
int scores[n];
for (int i = 0; i < n; i++) {
cin >> scores[i];
}

// 选择排序
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (scores[j] < scores[minIndex]) {
minIndex = j;
}
}
swap(scores[i], scores[minIndex]);
}

for (int i = 0; i < n; i++) {
cout << scores[i] << " ";
}
cout << endl;

return0;
}

练习 2：找出第 k 小的元素

输入一个数组和整数k，使用选择排序找到第k小的元素。

参考代码：

#include
usingnamespacestd;

intmain{
int n, k;
cin >> n >> k;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

// 选择排序，只排到第 k 个元素
for (int i = 0; i < k; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}

cout << "第 " << k << " 小的元素：" << arr[k-1] << endl;
return0;
}