选择排序
来自智得网
简介
选择排序中的选择是指在循环过程中每一轮找到最大值，然后把值直接放置在其最终位置的排序方式。
所以选择排序可以认为是冒泡排序的优化过程，都是每一轮找到剩余元素的最大值，但是选择排序在每一轮获取最大值的过程，不会两两交换数据，而是使用一个临时变量存储这个最大值，循环结束之后再将做一次交换，将最大值和位置上当前的值就行交换。
流程
选择排序的流程整体也是分为两轮循环。
- 因为选择排序每一次循环都可以确认一个最大值的位置，所以n个数字的数据集需要n-1轮才能确认所有数的位置。所以外循环循环n-1次。
- 每一轮内循环就是寻找数据集中最大值的过程，确认最大值之后将其和其位置上的当前值进行交换，一轮内循环确认一个最大值的位置之后，下一轮内循环只需要将数据集中该位置之前的数据重复该内循环的过程。
样例
例如输入{4，6，8，3，9， 5}将其从小到大排序。
输入的数据集一共是6个数字，所以循环5次可以完成选择排序的过程。
第一轮找出数据集的最大值，可以使用哨兵先将最大值置为第一个数字4，然后向后循环，发现比最大值大的数字就将最大值改写为该值，第一轮循环的时候，最大值是9，该值应该放在数据集最后的位置，所以将9和5交换。
因为9的位置已经确认，所以还剩余5个数字待排序，重复第一轮的循环过程，找出剩余数据的最大值8，将其和目前的第5位的数字5进行交换。
依此类推，将6、5、4、3依次放置在正确的位置。
分析
选择排序的过程是两轮循环，每一轮循环的数据量级是数据规模，所以其时间复杂度是。
选择排序过程中使用一个变量存储的当前的最大值，数据交换的过程也可能需要一个临时变量，空间复杂度是。
因为选择排序过程中本轮最大值和其位置上的当前值交换，所以数据本来的顺序可能会打乱，所以选择排序不是稳定的排序。
代码
#include<iostream>
using namespace std;
void select_sort(int* a,int n)
{
for (int i = 0; i < n; i++)
{
int index = i;
for (int j = i + 1; j < n; j++)
{
if (a[index] > a[j])index = j;
}
swap(a[i], a[index]);
}
}
void main()
{
int a[10]{ 5,7,9,6,3,1,4,8 };
select_sort(a, 8);
for (int i = 0; i < 8; i++)
{
cout << a[i]<<" ";
}
}