选择排序

选择排序属于选择类排序算法。

我打扑克牌的时候，会习惯性地从左到右扫描，然后将最小的牌放在最左边，然后从第二张牌开始继续从左到右扫描第二小的牌，放在最小的牌右边，以此反复。选择排序和我玩扑克时的排序特别相似。

现在有一堆乱序的数，比如：。

第一轮迭代，从第一个数开始，左边到右边进行扫描，找到最小的数 1，与数列里的第一个数交换位置。

第二轮迭代，从第二个数开始，左边到右边进行扫描，找到第二小的数 3，与数列里的第二个数交换位置。

第三轮迭代，从第三个数开始，左边到右边进行扫描，找到第三小的数 4，与数列里的第三个数交换位置。

经过交换，最后的结果为：1 3 4 5 6 6 6 8 9 14 25 49，我们可以看到已经排好序了。

每次扫描数列找出最小的数，然后与第一个数交换，然后排除第一个数，从第二个数开始重复这个操作，这种排序叫做简单选择排序。

举个简单例子，选择排序一个 4 个元素的数列：4 2 9 1：

橙色表示已完成排序的元素
绿色表示扫描元素

比较的次数和冒泡排序一样多，因为扫描过程也是比较的过程，只不过交换的次数减少为每轮 1 次。最佳和最坏时间复杂度仍然是：O(n^2)。

选择排序是一个不稳定的排序算法，比如数组：，第一轮迭代时最小的数是 1，那么与第一个元素 5 交换位置，这样数字 1 就和数字交换了位置，导致两个相同的数字 5 排序后位置变了。

每进行一轮迭代，我们都会维持这一轮最小数：min 和最小数的下标：minIndex，然后开始扫描，如果扫描的数比该数小，那么替换掉最小数和最小数下标，扫描完后判断是否应交换，然后交换：。

上面的算法需要从某个数开始，一直扫描到尾部，我们可以优化算法，使得复杂度减少一半。

我们每一轮，除了找最小数之外，还找最大数，然后分别和前面和后面的元素交换，这样循环次数减少一半，如：

输出：