目录
选择排序思想
在所有数中选出最小的数放在前面，然后在剩下的所有数中选出最小值，放在前面，后面过程依次类推，直到只剩最后一个数，此时，排序已完成。
选择排序图解
代码实现（初阶版)
//选择排序 void selectSort(int* a, int n) { int i, j; for (i = 0; i < n; i++) { for (j = i; j < n; j++) { if (a[i] > a[j]) { Swap(&a[i], &a[j]); } } } }
分析：在寻找最小值时，此代码要不断的进行数组元素的交换，因此，此方法比较低效。
代码实现（加强版）
通过交换数组的下标的方法寻找最大值，从而解决上面代码的问题。
//选择排序的优化 void selectSort(int* a, int n) { int i, j; for (i = 0; i < n; i++) { int min = i; for (j=i; j < n; j++) { if (a[min] > a[j]) { min = j; } } Swap(&a[min], &a[i]); } }
代码实现（最终版）
我们在寻找最小值的时候同时去寻找最大值，把最小值放前面，把最大值放后面，从而优化了代码的时间复杂度。
//选择排序(优化版) void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = begin; for (int i = begin; i <= end; ++i) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } Swap(&a[begin], &a[mini]); if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]); ++begin; --end; } }
时间复杂度
从代码中可以看出一共遍历了n + n-1 + n-2 + … + 2 + 1 = n * (n+1) / 2 = 0.5 * n ^ 2 + 0.5 * n，那么时间复杂度是O(N^2)。
时间复杂度稳定，跟序列的混乱程度无关。
