1、算法思想
选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置直到未排序元素个数为0。
2、算法描述
1>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 2>再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。 3>重复第二步，直到所有元素均排序完毕。
选择排序的整个过程：
示例代码：
#include<bits/stdc++.h>
using namespace std;
//选择排序
void SelectionSort(int a[],int n)
{
for(int i=0;i<n-1;++i){
int minIndex=i;//假设最小数的索引为i
for(int j=i+1;j<n;j++){
//cout<<a[j]<<" "<<a[minIndex] <<" "<<j;
//如何当前数小于上面假设的数值时
if(a[j]<a[minIndex])
//那么将原来设置的最小数的索引替换成当前数的索引
minIndex=j;
}
//每排完一次，改变最小数的位置
swap(a[i],a[minIndex]);
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
}
int main()
{
int sortlist[] = { 5,0,4,1,8,3,7 };
SelectionSort(sortlist,7);
}
3、选择排序优化图示
选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半。第一次选择最大值与最小值，过程如下：
优化选择排序示例代码：
#include<bits/stdc++.h>
using namespace std;
//选择排序优化后
void yh_sort(int a[],int n){
/*初始化左端、右端元素索引*/
int left = 0;
int right = n - 1;
while (left < right){
/*初始化最小值、最大值元素的索引*/
int min = left;
int max = right;
for (int i = left; i <= right; i++){
/*标记每趟比较中最大值和最小值的元素对应的索引min、max*/
if (a[i] < a[min])
min = i;
if (a[i] > a[max])
max = i;
}
/*最大值放在最右端*/
int temp = a[max];
a[max] = a[right];
a[right] = temp;
/*此处是先排最大值的位置，所以得考虑最小值（arr[min]）在最大位置（right）的情况*/
if (min == right)
min = max;
/*最小值放在最左端*/
temp = a[min];
a[min] = a[left];
a[left] = temp;
/*每趟遍历，元素总个数减少2，左右端各减少1，left和right索引分别向内移动1*/
left++;
right--;
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
}
int main()
{
int sortlist[] = { 5,0,4,1,8,3,7 };
yh_sort(sortlist,7);
}
4、算法复杂度
空间复杂度
选择排序的空间复杂度为O(1)。
稳定性
在选择排序中，每趟都会选出最大元素与最小元素，然后与两端元素交换，此时，待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏。如[5,3,5,2,9]，在array[0]与array[3]元素交换时，序列的稳定性就被破坏了，所以选择排序是一种不稳定的排序算法。
时间复杂度
选择排序的时间复杂度为O(n2)。
适用场景
待排序序列中，元素个数较少时。