选择排序

选择排序的思想：对一个规模为 n 的列表，遍历 n 次，每次从中选出最小的 1 个数。这样，循环 n 次，逐次拿出的数的序列就刚好是排好序的列表。

核心过程：给定一个数组，找到最小值。

找最小值的思想： - 循环不变式：当前的变量 i 存储着当前列表的最小值。 - 维护循环不变式： -- 列表为空，直接退出 -- 列表有一个元素，则 i = array[0]，因为不存在比它更小的元素 -- 假设对规模为 n 的列表的前 n-1 的部分已有最小值 i，那么，补充考虑第 n 个元素时，只需要将 i 和 array[n] 对比，返回其中更小的一个，即可保持循环不变式成立

所以这里实际上是用递归的思想，来寻找最小值。 如果只有一个元素，则取第一个元素，即是要求的结果。 如果又不止一个元素，则取第一个元素，它必然对 array[:1] 这个子列表成立循环不变式。然后，将规模从 1 逐步扩展至 n，在循环中维护循环不变式，循环结束时，循环不变式将在 n 的规模上继续成立，此时的 i 即为算法所求的结果。

引用自《算法图解》