思路
每一轮选取未排定的部分中最小的那个元素交换到未排定部分的最开头，经过若干个步骤，就能排定整个数组。即：先选出最小的，再选出第二小的，以此类推。
代码
def select_sort(list):
for j in range(len(list)):
min_pos = j
for i in range(j, len(list)):
if list[min_pos] > list[i]:
min_pos = i
list[j], list[min_pos] = list[min_pos], list[j]
return list
动图演示
结合代码更容易理解
红色： 标记最小值，同代码中的
minIndex绿色： 内循环，用于遍历找到「未排序部分」中的最小值，同代码中的
j
复杂度分析
- 时间复杂度：O(n2)，这里 N 是数组的长度；
- 空间复杂度：O(1)，使用到常数个临时变量。
练习测试
https://leetcode-cn.com/problems/sort-an-array/submissions/
我用的python，在此题中使用选择排序，会超出时间限制。
超出时间限制的用例： https://leetcode-cn.com/submissions/detail/89203696/testcase/
我在本次测试了这个用例，用时：87.07884120941162
总结
算法思想 1：贪心算法
每一次决策只看当前，当前最优，则全局最优。注意：这种思想不是任何时候都适用。
算法思想 2：减治思想
外层循环每一次都能排定一个元素，问题的规模逐渐减少，直到全部解决，即「大而化小，小而化了」。运用「减治思想」很典型的算法就是大名鼎鼎的「二分查找」。
选择排序的优点：交换次数最少
「选择排序」看起来好像最没有用，但是如果在交换成本较高的排序任务中，就可以使用「选择排序」（《算法 4》相关章节课后练习题）。
依然是建议大家不要对算法带有个人色彩，在面试回答问题的时候和看待一个人和事物的时候，可以参考的回答模式是「具体问题具体分析，在什么什么情况下，用什么什么算法」。