目录
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
一、原理学习
假设你现在手上正有一张记录了多个同学成绩的成绩单，你现在需要将这个成绩单按照学生成绩高低的顺序排列，从而给班内学生排序，该怎么做。
有一种办法是先遍历一遍这个成绩单，找到成绩最优的学生，再将他放入一个新的成绩单。
再以同样的方式，在剩余学生中找到成绩最高的添加入新列表末尾。
重复这么做直到将最后一名学生也添加入新列表，就得了到一个有序的成绩单。
这样的排序方式就叫做选择排序，即第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
在编写代码时，我们实际执行的是交换操作，找到整个列表中最大（小）的值，找到之后将其与第一个数交换，再找到最大（小）的与第二个数交换，以此类推。
选择排序只是一种思想，而非定式，你也可以在遍历过程中同时标记最大最小的数据，然后分别放在数据的开头和结尾，一轮遍历可以同时确定两个元素位置，以减少总遍历次数。
二、代码实现
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, minIdx, temp;
for (i = 0; i < n - 1; i++) {
minIdx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// 交换找到的最小元素和当前元素
temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原数组：\n");
printArray(arr, n);
selectionSort(arr, n);
printf("排序后的数组：\n");
printArray(arr, n);
return 0;
}
三、选择排序的问题
3.1 效率低
选择排序简单易懂，但其速度不是很快，在每次在未排序列表中查询最值时，需要的时间是O(n)，而这种操作你需要执行n次，需要的总时间为O(n*n)，即O(n²)。由于其O(n²)的时间复杂度，选择排序在处理大量数据时效率会非常低，此时可以选择其他排序方式比如归并排序和堆排序。
3.2 不稳定
选择排序是个不稳定的排序算法，这里的稳定不是说的程序运行稳定，稳定排序指的是，在排序过程中，如果有两个相等的元素，排序后它们的相对位置保持不变。选择排序的过程是每一轮从剩余未排序的部分中找到最小（或最大）的元素，并将其与当前的第一个元素交换位置。这种交换可能会破坏相等元素的相对顺序。
举个例子：
假设有一个数组：
[5a, 3, 5b, 2]其中 5a 和 5b 是两个值为同5的不同的元素，用a和b来标记他们现在的位置。如果按照选择排序的过程进行排序：
第一轮：选择最小元素 2，将其与数组的第一个元素 5a 交换，得到：
[2, 3, 5b, 5a]第二轮：从剩余的部分 [3, 5b, 5a] 中选择最小元素 3，它和第一个元素 3 交换，数组不变：
[2, 3, 5b, 5a]第三轮：选择 5b 和 5a ，值相同不交换。
在这个例子中，原本 5a 在 5b 前面，但排序后 5a 被交换到了 5b 的后面，这破坏了它们的相对顺序。因此，选择排序被认为是不稳定的。