Selection Sort

Find the smallest element using a linear scan and move it to the front. Then find the second smallest element and move it. Continue doing this until all the elements are inplace.

核心：不断地选择剩余元素中的最小者。

1. 找到数组中最小元素并将其和数组第一个元素交换位置。

2. 在剩下的元素中找到最小元素并将其与数组第二个元素交换，直至整个数组排序。

性质：

• 比较次数=(N-1)+(N-2)+(N-3)+...+2+1~N^2/2

• 交换次数=N

• 运行时间与输入无关

• 数据移动最少

复杂度分析

平均情况与最坏情况均为 ，空间复杂度为 .+

https://einsqiang.gitbooks.io/python-algorithm/content/basics_sorting/selection_sort.html