选择排序详解及递归实现

---

选择排序：每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的最后，知道全部排完为止。

简单的选择排序的时间复杂度是O(n^2)。

只有在两个记录交换时需要一个辅助空间，所以空间复杂度为O(1)。

1. 就选择排序方法本身来讲，它是一种稳定的排序方法。稳不稳定是看算所采用“交换记录”的策略，根据这个来判断自己所写的选择排序是不是稳定的。
2. 可用于链式存储结构
3. 移动记录次数越少，当每一种记录占用的空间较多时，此方法比直接插入排序快。

优化双层循环的选择排序
通过一次循环找出最大的数和最小的数，并且把最大的数放在右边，最小的数放在左边
注意：此时有一个特殊情况，那就是我要交换的最大数刚好被交换最小数时，被交换走了，此时我们就需要加一个判断。优化后只直接提高一半效率

优化递归循环的选择排序
通过一次循环找出最大的数和最小的数，并且把最大的数放在右边，最小的数放在左边
注意：此时有一个特殊情况，那就是我要交换的最大数刚好被交换最小数时，被交换走了，此时我们就需要加一个判断。优化后只直接提高一半效率