1. 概念
不断的选择剩余元素中的最小者，将其放到顺序的位置上。
2. 实现流程
- 找到数组中最小的那个元素
- 将它和数组的第一个元素交换位置
- 在剩下的元素中找到最小的元素
- 将它与数组的第二个元素交换位置
3.算法图解
选择排序
选择排序
红色表示当前最小值，黄色表示已排序的序列，蓝色表示当前位置。
4.代码实现
void selection_sort(int arr[],int len) {
int min_key,temp;
for (int i = 0; i < len; i++) {
min_key = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[min_key]) {
min_key = j;
}
}
temp = arr[min_key];
arr[min_key] = arr[i];
arr[i] = temp;
}
}
5.时间复杂度
最差时间复杂度 O( n^2 )
最优时间复杂度 O( n^2 )
平均时间复杂度 O( n^2 )
最差空间复杂度 O( n ),需要辅助空间O(1)
就算数组之前是排好序的，选择排序依然也需要同样时间，并不会缩短排序时间
