概要
选择排序（Selection Sort）是一种原地比较排序算法，核心思想是每轮从未排序区选择极值（最小 / 最大），与未排序区起点交换。
整体架构流程
-
初始状态：将整个数组视为未排序区域，已排序区域为空。
-
遍历未排序区域：从当前未排序区域中找到最小值（或最大值）的索引。
-
交换元素：将找到的最小值与未排序区域的第一个元素交换位置，将该元素归入已排序区域。
-
重复操作：缩小未排序区域的范围，重复上述步骤，直到所有元素有序。
技术名词解释
-
不稳定排序：如果排序过程中相等元素的相对顺序可能改变，则该算法是不稳定的。选择排序是典型的不稳定排序（例如对序列
[5, 5, 2]排序时，第一个 5 可能被交换到第二个 5 之后）。 -
时间复杂度：算法执行时间与数据规模的关系。选择排序的时间复杂度为 O(n²)，因为需要两层循环遍历元素。
-
原地排序：排序过程中仅使用常数级别的额外空间，不依赖输入数据规模。选择排序是原地排序。
-
比较次数：无论输入数据是否有序，选择排序的比较次数恒定为 n(n-1)/2 次。
技术细节
#include <stdio.h>// 选择排序
void selectSort(int arr[], int length) {int i = 0; // 计数器int j = 0; // 计数器int k = 0; // 用于记录每一趟中最小值的下标int temp = 0; // 临时存储空间for (i = 0; i < length - 1; i++) {// 每一趟的过程k = i;for (j = i + 1; j < length; j++) {// 如果有比 arr[k] 小的值，则对 k 进行修改if (arr[j] < arr[k]) {k = j; // 记录最小值的下标}}// 如果 k != i，则证明这一趟中找到了比 arr[i] 小的值，// 进而交换 arr[i] 和 arr[k] 的值if (k != i) {temp = arr[k];arr[k] = arr[i];arr[i] = temp;}}
}int main() {int arr[] = { 1, 5, 2, 12, 54, 2, 23 }; // 待排序的数组int sz = sizeof(arr) / sizeof(arr[0]); // 计算数组的大小selectSort(arr, sz); // 选择排序// 输出排序后的数组printf("排序后的数组: ");for (int i = 0; i < sz; i++) {printf("%d ", arr[i]);}printf("\n");return 0; // 程序正常结束
}在这段代码中，selectSort 函数实现了选择排序的逻辑。外层 for 循环控制排序的轮数，内层 for 循环用于在每一轮中寻找未排序部分的最小值的索引 k。
如果找到的最小值索引 k 与当前未排序部分的起始索引 i 不同，就通过临时变量 temp 交换 arr[i] 和 arr[k] 的值，从而将最小值放到已排序部分的末尾。
小结
选择排序的优势与局限性：
-
优点：实现简单、空间复杂度低，适合小规模数据或交换成本高的场景（如对存储介质上的数据排序）。
-
缺点：时间复杂度较高，不适合大规模数据；不稳定排序的特性可能导致问题。
适用场景：
-
数据量较小（例如 n < 1000）。
-
对内存使用有严格限制的环境。
替代算法：
-
快速排序：平均时间复杂度 O(n log n)，适合大规模数据。
-
插入排序：对小规模或部分有序数据更高效。
附
感谢阅读。
