基本思想
就是首先扫描整个数组，找到最小的元素，然后和第一个元素进行交换，如此一来就等同于将最小的元素放到它在有序表中最终的位置上。然后从第二个元素开始扫描整个表，找到剩余n-1个元素中最小的元素，与第二个元素交换位置。以此类推，在执行n-1遍之后，这个数组就自然有序了。（当然每次找最大的元素，与最后一个元素交换也是可行的）
复杂度
选择排序有一个最明显的优于冒泡排序的地方：数据交换的次数。在选择排序中，一共最多产生n-1次交换（有时当剩余数组第一个值就是最小值的时候甚至不需要进行交换）， 虽然选择排序的时间复杂度也是O(n^2)，选择排序的空间复杂度也是O(1)。
稳定性
不稳定排序
总结
选择排序优缺点：
优点：一轮比较只需要换一次位置；
缺点：效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。
/// <summary>
/// 简单选择排序
/// </summary>
/// <param name="array">排序数组</param>
void OptBase(int[] array)
{
if (array.Length < 2) return;
int minIdx;
for (int i = 0; i < array.Length; i++)
{
//每次循环开始，重置坐标
minIdx = i;
//前i个已经有序
//内循环是在[i,array.length-1]的区间找出最小的元素位置，和第i个进行交换
for (int j = i; j < array.Length; j++)
{
if (array[j] < array[minIdx]){
minIdx = j;
}
}
//判断第i个不是最小的进行减缓，是的话不做处理
if(i != minIdx)
{
Swap(array, minIdx, i);
}
}
}
优化
可以一次性地找到最大值和最小值，分别和头、尾两个元素进行交换。 这样一来外循环只要执行原来一半的循环次数就可以了。但是需要注意一点：每次循环要进行2次交换，第一次最小值交换结束之后，在进行最大值交换的时候要先判断，最大值是不是在第一个位置，在第一次最小值交换的时候已经换到了后面？所以要先交换最小的，再交换最大的
/// <summary>
/// 简单选择排序的优化
/// </summary>
/// <param name="array">排序数组</param>
void OptOptimize(int[] array)
{
if (array.Length < 2) return;
//一次找到最大值和最小值
int minIdx, maxIdx;
//外循环遍历一半结束
//如果完整遍历，整个数组都会变成倒序排列
for (int i = 0; i < array.Length; i++)
{
minIdx = i;
maxIdx = i;
//内循环从两边缩进
for (int j = i; j < array.Length-i; j++)
{
if (array[j] < array[minIdx])
{
minIdx = j;
}
if (array[j] > array[maxIdx])
{
maxIdx = j;
}
}
if (i != minIdx)
{
Swap(array, i, minIdx);
}
if(array.Length-1-i != maxIdx)
{
//防止最大数在第一个，优先和最小值进行交换
if(i == maxIdx)
{
Swap(array, array.Length - 1 - i, minIdx);
}
else
{
Swap(array, array.Length - 1 - i, maxIdx);
}
}
}
}
//互换函数
void Swap(int[] arr, int index1, int index2)
{
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
