一、选择排序的基本概念
选择排序（Selection Sort）是一种简单直观的排序算法，其核心思想是每次从待排序元素中找到最值（最小值或最大值），将其放到已排序序列的末尾，重复此过程直到所有元素完成排序。
与冒泡排序通过相邻元素交换逐步"浮"出最值不同，选择排序通过"选择"最值并一次性交换到目标位置，减少了交换操作的次数。这种特性使选择排序在某些场景下（如交换成本较高的情况）表现优于冒泡排序。
二、选择排序的工作原理
选择排序的工作过程可分为以下步骤，我们以升序排序（找最小值）为例说明：
- 划分区域：将数组分为"已排序区域"和"未排序区域"。初始状态下，已排序区域为空，未排序区域为整个数组。
- 查找最值：在未排序区域中找到最小元素，记录其索引。
- 交换元素：将找到的最小元素与未排序区域的第一个元素交换，此时该元素被纳入已排序区域。
- 重复迭代：缩小未排序区域的范围（左边界右移一位），重复步骤2和3，直到未排序区域为空。
示例演示：
对数组 [64, 25, 12, 22, 11] 进行升序排序的过程：
- 第1轮：未排序区域为
[64, 25, 12, 22, 11]，最小值为11（索引4），与未排序区域第一个元素64交换 → 数组变为[11, 25, 12, 22, 64]（已排序区域：[11]）。 - 第2轮：未排序区域为
[25, 12, 22, 64]，最小值为12（索引2），与25交换 → 数组变为[11, 12, 25, 22, 64]（已排序区域：[11, 12]）。 - 第3轮：未排序区域为
[25, 22, 64]，最小值为22（索引3），与25交换 → 数组变为[11, 12, 22, 25, 64]（已排序区域：[11, 12, 22]）。 - 第4轮：未排序区域为
[25, 64]，最小值为25（索引3），无需交换 → 数组保持[11, 12, 22, 25, 64]（已排序区域：[11, 12, 22, 25]）。 - 结束：未排序区域仅剩最后一个元素64，排序完成。
三、算法特性分析
-
时间复杂度
选择排序的时间复杂度不受输入数据的影响，始终为 O(n²)：- 外层循环需要执行
n-1次（每次确定一个元素的位置）。 - 内层循环在第
i轮需要遍历n-i个元素（寻找未排序区域的最值）。 - 总操作次数为
(n-1) + (n-2) + ... + 1 = n(n-1)/2，近似为n²/2，因此时间复杂度为 O(n²)。
- 外层循环需要执行
-
空间复杂度
选择排序仅使用常数级别的额外空间（如存储最值索引和临时交换变量），因此空间复杂度为 O(1)，是一种"原地排序"算法。 -
稳定性
选择排序是不稳定的排序算法。例如，对数组[2, 2, 1]排序时，第一个2会与1交换，导致两个2的相对位置发生改变（原顺序为[2₁, 2₂, 1]，排序后为[1, 2₂, 2₁]）。 -
优缺点
- 优点：实现简单，空间复杂度低，交换操作次数少（最多
n-1次）。 - 缺点：时间复杂度高，不适合处理大规模数据；稳定性差，不适用于要求保持相等元素相对顺序的场景。
- 优点：实现简单，空间复杂度低，交换操作次数少（最多
四、C/C++代码实现
下面是选择排序的C++实现，包含完整的排序函数、测试用例和打印函数：
#include <iostream>
#include <vector>using namespace std;// 选择排序函数（升序）
void selectionSort(int arr[], int n) {// 外层循环：控制已排序区域的边界（0 ~ i-1为已排序）for (int i = 0; i < n - 1; i++) {int minIndex = i; // 记录未排序区域中最小值的索引，初始假设为i// 内层循环：在未排序区域（i ~ n-1）中寻找最小值for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j; // 更新最小值索引}}// 将找到的最小值与未排序区域的第一个元素（arr[i]）交换if (minIndex != i) { // 若最小值就是当前元素，无需交换int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}// 打印数组元素
void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;
}int main() {// 测试用例1：整数数组int arr1[] = {64, 25, 12, 22, 11};int n1 = sizeof(arr1) / sizeof(arr1[0]);cout << "排序前的数组：";printArray(arr1, n1);selectionSort(arr1, n1);cout << "排序后的数组：";printArray(arr1, n1);// 测试用例2：包含重复元素的数组int arr2[] = {3, 1, 4, 1, 5, 9, 2, 6};int n2 = sizeof(arr2) / sizeof(arr2[0]);cout << "\n排序前的数组（含重复元素）：";printArray(arr2, n2);selectionSort(arr2, n2);cout << "排序后的数组（含重复元素）：";printArray(arr2, n2);return 0;
}五、代码解析
-
排序函数
selectionSort- 外层循环变量
i表示已排序区域的边界（0 ~ i-1为已排序元素），循环范围为0 ~ n-2（最后一个元素无需排序）。 - 内层循环从
i+1开始遍历未排序区域，通过minIndex记录最小值的位置。 - 找到最小值后，若其位置与
i不同，则交换arr[i]和arr[minIndex]，将最小值放入已排序区域的末尾。
- 外层循环变量
-
辅助函数
printArray
用于打印数组元素，方便观察排序前后的变化。 -
测试用例
- 第一个测试用例验证基本排序功能，第二个测试用例验证对含重复元素数组的排序效果（可观察到选择排序的不稳定性）。
六、优化方向
标准选择排序可通过以下方式优化：
-
双向选择排序
每次迭代同时寻找未排序区域的最小值和最大值，分别放到已排序区域的两端，减少循环次数（迭代次数从n-1减少到n/2）。void bidirectionalSelectionSort(int arr[], int n) {int left = 0, right = n - 1;while (left < right) {int minIndex = left, maxIndex = right;// 找最小值和最大值for (int i = left; i <= right; i++) {if (arr[i] < arr[minIndex]) minIndex = i;if (arr[i] > arr[maxIndex]) maxIndex = i;}// 交换最小值到左侧swap(arr[left], arr[minIndex]);// 若最大值在左侧（被交换过），更新maxIndexif (maxIndex == left) maxIndex = minIndex;// 交换最大值到右侧swap(arr[right], arr[maxIndex]);left++;right--;} } -
优化交换操作
对于大型元素（如结构体），交换操作成本较高，可先记录最值位置，最后一次性移动元素（减少复制次数）。
七、适用场景
选择排序适合以下场景：
- 数据量较小（如
n < 100），对排序效率要求不高。 - 内存空间有限，需要原地排序（空间复杂度O(1)）。
- 交换操作成本较高（选择排序的交换次数最少）。
对于大规模数据（n > 1000），建议使用快速排序、归并排序等O(n log n)级别的算法。
选择排序是一种基础的排序算法，其核心思想是"选择最值并交换"，实现简单但效率较低。
在实际开发中，需根据数据规模、空间限制和稳定性要求，选择合适的排序算法。
