本篇博客会讲解如何使用C语言实现选择排序。
下面我来画图讲解选择排序的思路。
假设有一个数组，其初始状态如下，我们想把这个数组排成升序。
首先我们标明范围，即[begin, end]，一开始begin(b)和end(e)分别表示数组的第一个位置和最后一个位置，我们要找到[begin, end]中的最小的数据(1)和最大的数据(5)，并且把最小的数据换到最左边，最大的数据换到最右边。
交换前：
交换后：
此时两边的数据就排好了，接下来需要排中间的n-2个数据，我们分别让begin和end向中间走一步，重复刚刚的操作，找出[begin, end]中最小的数(2)和最大的数(4)，分别换到最左边和最右边：
交换前：
交换后：
接着再让begin和end往中间走，重复上面的步骤，直到begin和end相遇为止。
需要注意的是，在把最小的数据往左边换时，如果最左边的数据刚好是最大的数据，交换之后，最大的数据的位置就变了，此时需要更新最大的数据的位置。
对于选择排序，每一趟选出最小数和最大数的遍历次数是逐渐减少的，每次减少2，其总次数是一个公差为2的等差数列求和，其时间复杂度为O(N2)。由于选择排序消耗常数的额外空间，所以其空间复杂度为O(1)。
下面来讨论选择排序的稳定性。选择排序是非常具有误导性的，很多人可能会认为选择排序是一个稳定的排序，事实上是不稳定的，下面我举一个反例。假设一个数组的初始状态如下：
当我们把最小数(2)与最左边的数据交换时，会改变两个3的相对顺序。所以，选择排序有可能会改变相同的数据的相对顺序，故选择排序是不稳定的。
代码如下：
void SelectSort(int* a, int n)
{assert(a);int begin = 0;int end = n - 1;while (begin < end){// 找出[begin, end]的最小值和最大值的下标int maxi, mini;maxi = mini = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}// 分别把最小值和最大值换到两边Swap(a + mini, a + begin);// 如果最左边本来就是最大值，就被换走了，需要修正maxiif (begin == maxi){maxi = mini;}Swap(a + maxi, a + end);++begin;--end;}
}
总结
选择排序使用一种“选数”的思路，其方法简单粗暴，通过遍历的方式每次找出最小数和最大数，并将其分别换到最左边和最右边。其时间复杂度为O(N2)，空间复杂度为O(1)。选择排序是不稳定的。
