选择排序——直接选择排序

直接选择排序：（以重复选择的思想为基础进行排序）

1、简述

顾名思义就是选出一个数，再去抉择放哪里去。

设记录R1，R2…，Rn，对i=1，2，…，n-1，重复下列工作：

(1)在Ri，…，Rn中选最小(或最大)关键字记录Rj；

(2)将Rj与第i个记录交换位置，即将选到的比i小的记录换到第i号位置上。

2、复杂度

时间复杂度： ≈O(n²)

空间复杂度：O(1)

3、稳定性：不稳定排序

4、例子

#include <iostream>
using namespace std;
// 选择排序
int main() {int arr[8] = {45, 38, 66, 90, 88, 10, 25, 45};int arrCount = sizeof(arr) / sizeof(arr[0]);for (int i = 0; i < arrCount-1; i++) {// 从第一个开始，找出最小值的下标int minIndex = i, tmp = arr[i];for (int j = i + 1; j < arrCount; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;  // 找到最小下标，并记录}}// 交换下标位置arr[i] = arr[minIndex];arr[minIndex] = tmp;cout<<i+1<<"次排序后：";for (int i = 0;i < arrCount;i++) {cout << arr[i] << " ";}cout<<endl;}cout<<"最后结果：";for (int i = 0;i < arrCount;i++) {cout << arr[i] << " ";}return 0;
}

输出结果：

1次排序后：10 38 66 90 88 45 25 45 
2次排序后：10 25 66 90 88 45 38 45 
3次排序后：10 25 38 90 88 45 66 45 
4次排序后：10 25 38 45 88 90 66 45 
5次排序后：10 25 38 45 45 90 66 88 
6次排序后：10 25 38 45 45 66 90 88 
7次排序后：10 25 38 45 45 66 88 90 
最后结果：10 25 38 45 45 66 88 90

---

生命不息，学习不止，若有不正确的地方，欢迎指正。