选择排序（详解）c++
选择排序(Selection Sort)是⼀种特别直观的排序算法。每次找出未排序序列中最⼩的元素，然后放进有序序列的后⾯
算法思想:
每次找出未排序序列中最小的元素，然后放进有序序列的后面
在数组中完成选择排序
落实到代码的时候就两步：找最小+交换
- 在整个排序序列里面找出最小的一个元素
- 和未排序序列里面第一个元素做交换
代码实现：
测试代码：P1177 【模板】排序 - 洛谷
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
void select_sort()
{
//不取到n，最后一个肯定是有序的
for (int i = 1; i <= n; ++i) //待排序区间的首位置
{
//[i, n] 待排序区间
int pos = i;
for (int j = i + 1; j <= n; ++j) //查找最小元素下标
{
if (a[j] < a[pos])
{
//更新pos
pos = j;
}
}
//此时pos是[i, n]区间最小元素，与待排序首元素做交换
swap(a[i], a[pos]);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
select_sort();
for (int i = 1; i <= n; ++i) cout << a[i] << " ";
cout << '\n';
return 0;
}时间复杂度
⽆论数组有序还是⽆序，在未排序区间内找最⼩值的时候，都需要遍历⼀遍待排序的区间，因此时
间复杂度为
O(n*n
)，比如升序123456，第一次找最小元素要遍历数组1次找到1，第二次找最小要遍历5次找到最小元素2，依次类推再遍历4+3+2次找到5，如果有n个元素，要遍历n+(n-1)+…+2，时间复杂度是O(N*N)级别