什么是选择排序？¶
选择排序（Selection Sort）是一种简单直观的排序算法。它的核心思想是：每一次从待排序的元素中选出最小（或最大）的一个元素，将其放到已排序序列的末尾，直到所有元素都排序完成。
举个生活中的例子：假设你要整理一堆杂乱的扑克牌，每次从剩下的牌中找出最小的那张，放到最左边，直到所有牌都排好序。
选择排序的基本思路¶
- 外层循环：控制当前需要排序的起始位置（例如第i个位置，i从0开始）。
- 内层循环：在剩余未排序的元素中（从i到数组末尾），找到最小元素的位置。
- 交换操作：将找到的最小元素与当前起始位置的元素交换，确保最小元素被放到正确的位置。
- 重复步骤：直到外层循环结束，所有元素排序完成。
步骤分析¶
以数组 arr = {64, 25, 12, 22, 11} 为例：
1. 初始状态：未排序部分为整个数组，已排序部分为空。
2. 第一次外层循环（i=0）：
- 内层循环从 j=1 到 4，找到最小值 11，位置在 4。
- 交换 arr[0] 和 arr[4]，数组变为 {11, 25, 12, 22, 64}。此时第0位已排好。
3. 第二次外层循环（i=1）：
- 内层循环从 j=2 到 4，找到最小值 12，位置在 2。
- 交换 arr[1] 和 arr[2]，数组变为 {11, 12, 25, 22, 64}。此时第1位已排好。
4. 第三次外层循环（i=2）：
- 内层循环从 j=3 到 4，找到最小值 22，位置在 3。
- 交换 arr[2] 和 arr[3]，数组变为 {11, 12, 22, 25, 64}。此时第2位已排好。
5. 第四次外层循环（i=3）：
- 内层循环从 j=4 到 4，最小值是 25（位置3），无需交换。
6. 结束：数组已完全排序。
C++代码实现¶
#include <iostream>
using namespace std;
// 选择排序函数：对数组arr进行排序，n为数组长度
void selectionSort(int arr[], int n) {
// 外层循环：控制当前需要放置最小值的位置（i从0到n-2，最后一个元素无需排序）
for (int i = 0; i < n - 1; i++) {
// 初始假设第i个元素是最小值
int minIndex = i;
// 内层循环：在剩余元素中找到最小值的位置
for (int j = i + 1; j < n; j++) {
// 如果当前元素比minIndex位置的元素小，更新minIndex
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换当前i位置元素与最小值元素
// 如果minIndex == i，交换后数组不变（无影响）
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// 主函数：测试选择排序
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
// 输出排序前的数组
cout << "排序前的数组：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 调用选择排序函数
selectionSort(arr, n);
// 输出排序后的数组
cout << "排序后的数组：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
代码解释¶
- 外层循环：
i从0到n-2（因为最后一个元素无需排序），表示当前要放置最小值的位置。 - 内层循环：
j从i+1开始遍历剩余元素，找到最小值的索引minIndex。 - 交换操作：通过临时变量
temp交换arr[i]和arr[minIndex]，确保最小值被放到第i个位置。 - 时间复杂度：两层循环，时间复杂度为 O(n²)（n为数组长度），空间复杂度为 O(1)（仅用临时变量交换）。
运行结果¶
排序前的数组：64 25 12 22 11
排序后的数组：11 12 22 25 64
总结¶
选择排序的核心是每次找到最小值并交换，适合小规模数据排序。虽然时间复杂度较高，但实现简单，无需额外空间，是理解排序算法的基础之一。初学者可以通过手动模拟排序过程（如上面的例子）加深对算法逻辑的理解。