选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序算法思想：
选择排序的算法思想是：每一次从待排序序列中选出一个最大（或最小）的元素，让它存放在序列的起始位置。（这里的起始位置是未排序序列的起始位置，下面算法举例中详细解释）
选择排序算法举例：
例如，现在对序列｛1，4，3，2｝进行选择排序
- 第一趟
在未排序序列｛1，4，3，2｝中寻找最小元素为1，放到第一位。此时序列为：｛1，4，3，2｝
- 第二趟
未排序序列变为｛4，3，2｝，此时寻找该序列的最小元素，放到第一位，即｛2，4，3｝，加上之前已排序的｛1｝，就是｛1，2，4，3｝
- 第三趟
未排序序列为｛4，3｝，此时寻找该序列的最小元素3，放到第一位，即｛3，4｝，加上之前已排序的｛1，2｝，就是｛1，2，3，4｝。
此时未排序序列只有一个元素｛4｝，即为原序列最大值，无需排序。排序完成。
代码实现：
#include<stdio.h> //输出数组 void printArr(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d--", a[i]); } printf(" "); } //选择排序 void SelectionSort(int *a, int n) { //1，4，3，2 register int i, j, min, temp; for (i = 1; i < n; i++)//i从1开始，只需选择排序(n-1)趟即可，因为最后一个未排序元素即为最大（或最小）值 { min = i - 1;//此时将min设置为“每一趟”未排序序列的第一个元素！！ for (j = i; j < n; j++)//未排序序列的循环比较 { if (a[min] > a[j])//如果发现未排序元素中，后面的元素a[j]有比第一个元素a[min]小的，将该元素的索引赋值给min { min = j; } } if (min != i - 1)//一趟比较结束，如果min不是未排序序列的第一个元素了，也就是索引发生了改变，此时a[min]为序列最小元素，将其与未排序序列的第一个元素交换位置。 { temp = a[min]; a[min] = a[i - 1]; a[i - 1] = temp; } } printArr(a, n); } void main() { int a[] = { 1,4,3,2 }; SelectionSort(a, 4); getchar(); }
时间复杂度：
最好情况：所有元素都有序，那么交换次数为0，比较次数为1+2+3+...+（n-1），即 n*(n-1)/2
最坏情况：交换次数为（n-1）次，比较次数仍为 n*(n-1)/2
故最坏、最好、平均时间复杂度都是：O(n^2)
另外看到不少网上说的，最坏情况为所有元素逆序，交换次数为(n-1)次，其实不然。
例如｛3，2，1｝，所有元素逆序，只需要交换1次，即第一趟找到最小值1，和序列首位元素3交换，得到结果｛1，2，3｝之后再无交换。
反观序列｛3，1，2｝，首先第一次3、1交换得到｛1，3，2｝，再之后3、2交换得到｛1，2，3｝交换了2次。
稳定性：
看网上对选择排序的稳定性有争议吗，有人说
使用数组实现：不稳定
使用链表或者新开辟数组形式实现：稳定
对此有学者定义：有很多办法可以将任意排序算法变成稳定的，但是，往往需要额外的时间或者空间。
毕竟这个稳定性是人为定义的，具体我也不知道怎么说了。对了，要是考试就写：不稳定！！！