时间复杂度：O(n²) —— 无论数据初始排列如何，都需要进行n(n-1)/2次比较空间
复杂度：O(1) —— 原地排序，不需要额外存储空间
稳定性：不稳定排序（可能改变相同元素的相对位置）
适用场景：小规模数据排序，或对内存使用要求严格的场景
前言
一、算法概述
选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是：每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。这种排序方式因其工作原理类似于人们打扑克牌时整理手牌的方式，也被称为"直接选择排序"。
二、算法原理
假设我们要对数组 [64, 25, 12, 22, 11] 进行升序排序
[64, 25, 12, 22, 11]
第1轮：找到最小值11，与第1位64交换
-> [11, 25, 12, 22, 64]
第2轮：从剩余元素中找到最小值12，与第2位25交换
-> [11, 12, 25, 22, 64]
第3轮：从剩余元素中找到最小值22，与第3位25交换
-> [11, 12, 22, 25, 64]
第4轮：从剩余元素中找到最小值25，已在正确位置
-> [11, 12, 22, 25, 64]
排序完成！初始状态：整个数组为未排序部分，已排序部分为空。第1轮：遍历整个数组，找到最小元素的下标（假设为
min_index）。将min_index的元素与第1个元素交换。此时，前1个元素为已排序部分。第2轮：遍历剩余未排序部分（从第2个元素到末尾），找到最小元素的下标。将最小元素与第2个元素交换。此时，前2个元素为已排序部分。重复上述步骤，直到未排序部分只剩1个元素（此时数组已完全有序）
#include <stdio.h>
// 选择排序函数
void selectionSort(int arr[], int n) {
// 外层循环控制分界点移动（i即为分界点）
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;
}
}
// 交换操作：将最小值放到分界点位置
if (minIndex != i) { // 避免不必要的交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int size = sizeof(arr) / sizeof(arr[0]);
printf("原始数组: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
selectionSort(arr, size);
printf("排序结果: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}初始数组：[64, 25, 12, 22, 11]
第1轮：目标：在未排序部分（全部）找到最小值，放到首位。查找最小值：遍历 [64, 25, 12, 22, 11]，发现最小值是 11（下标4）。交换：64（首位）和 11 交换。结果：[11, 25, 12, 22, 64]（已排序部分：[11]，未排序部分：[25, 12, 22, 64]）第2轮：目标：在剩余未排序部分 [25, 12, 22, 64] 找最小值，放到已排序末尾（即第2位）。查找最小值：遍历 [25, 12, 22, 64]，最小值是 12（下标2）。交换：25（第2位）和 12 交换。结果：[11, 12, 25, 22, 64]（已排序部分：[11, 12]，未排序部分：[25, 22, 64]）第3轮：目标：在 [25, 22, 64] 中找最小值，放到第3位。查找最小值：最小值是 22（下标3）。交换：25（第3位）和 22 交换。结果：[11, 12, 22, 25, 64]（已排序部分：[11, 12, 22]，未排序部分：[25, 64]）第4轮：目标：在 [25, 64] 中找最小值，放到第4位。查找最小值：最小值是 25，已在正确位置（无需交换）。结果：[11, 12, 22, 25, 64]（排序完成！）
三. 针对部分有序数组的优化
void SelectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i;
int isSorted = 1;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
if (arr[j] < arr[j-1]) {
isSorted = 0;
}
}
if (isSorted) break; // 剩余部分已有序
if (minIndex != i) {
swap(&arr[i], &arr[minIndex]);
}
}
}这里的函数做了优化对于如果是【3，1，2，7】它的话第一次进入和之前一样找到最小的交换加的这个if是用来判断数组是否有序如果有序就会为1这样的话就节省了循环的次数以便于程序的进行
这个选择排序在实践中特别适用于：数据量不大但可能部分有序的场景需要保证最坏情况下仍能完成排序的场合
四、常见问题
为什么选择排序是不稳定的？示例：排序
[5, 8, 5, 2, 9]，第一个5会与2交换，导致两个5的相对顺序改变选择排序和冒泡排序的主要区别是什么？选择排序每轮只进行一次交换，而冒泡排序可能进行多次交换选择排序的比较次数固定为O(n²)，而最好情况下冒泡排序只需O(n)次比较
总结
选择排序是一种简单直观的原地排序算法，通过反复选取未排序部分的最小元素放到已排序末尾来完成排序。其主要特点包括：
时间复杂度始终为O(n²)，比较次数固定为n(n-1)/2次空间复杂度O(1)，是原地排序算法交换次数仅需O(n)次，适合元素移动成本高的场景不稳定排序，可能改变相等元素的相对位置性能与输入数据状态无关，适合小规模数据排序
算法优势在于实现简单、内存效率高，虽然在大数据量时效率较低，但仍是理解排序算法基础原理的经典案例。优化版本如双向选择排序可以进一步提升性能。