实现
每次从数组中找到最小（大）的值放到前面，直到排序结束。例如：数组[8,5,2,6,9,3,1,4,0,7]，如果按照从小到大排序则,第一趟排序从全部数组中找到最小的值与index=0位置的元素交换，第二次排序是丛index=1开始之后的所有元素中选择最小的值与index=1的元素交换，第三趟排序则从index=2开始，同理各次排序结果如下：
python实现：
def selectSort(lst):
for i in range(len(lst)-1):
minidx=i
for j in range(i+1,len(lst)):
if lst[minidx]>lst[j]:
minidx=j
tp=lst[i]
lst[i]=lst[minidx]
lst[minidx]=tp
print('第',i+1,'趟排序',lst)
return lst
print(selectSort([8,5,2,6,9,3,1,4,0,7]))
运行结果如下：
第 1 趟排序 [0, 5, 2, 6, 9, 3, 1, 4, 8, 7] 第 2 趟排序 [0, 1, 2, 6, 9, 3, 5, 4, 8, 7] 第 3 趟排序 [0, 1, 2, 6, 9, 3, 5, 4, 8, 7] 第 4 趟排序 [0, 1, 2, 3, 9, 6, 5, 4, 8, 7] 第 5 趟排序 [0, 1, 2, 3, 4, 6, 5, 9, 8, 7] 第 6 趟排序 [0, 1, 2, 3, 4, 5, 6, 9, 8, 7] 第 7 趟排序 [0, 1, 2, 3, 4, 5, 6, 9, 8, 7] 第 8 趟排序 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 第 9 趟排序 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
很容易发现第2、3趟，6、7趟，8、9趟排序貌似没有什么区别，原因是第n次排序丛index=n开始之后的所有元素中选择最小的值然而最小值所在的index恰好为n此时交换相当于自身与自身交换，但是这个交换是不必要的可以通过判断来避免交换。
修改后如下：
def selectSort(lst):
for i in range(len(lst)-1):
minidx=i
for j in range(i+1,len(lst)):
if lst[minidx]>lst[j]:
minidx=j
if i ==minidx:
continue
tp=lst[i]
lst[i]=lst[minidx]
lst[minidx]=tp
print('第',i+1,'趟排序',lst)
return lst
print(selectSort([8,5,2,6,9,3,1,4,0,7]))
修改后运行结果：
第 1 趟排序 [0, 5, 2, 6, 9, 3, 1, 4, 8, 7] 第 2 趟排序 [0, 1, 2, 6, 9, 3, 5, 4, 8, 7] 第 4 趟排序 [0, 1, 2, 3, 9, 6, 5, 4, 8, 7] 第 5 趟排序 [0, 1, 2, 3, 4, 6, 5, 9, 8, 7] 第 6 趟排序 [0, 1, 2, 3, 4, 5, 6, 9, 8, 7] 第 8 趟排序 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
可以看到交换次数明显减少了。
性质
1、稳定性：
选择排序是不稳定的排序方法（比如序列[9*,9,8]第一次就将第一个[9*]与[8]交换，导致第一个9挪动到第二个9后面[8,9,9*]）。
2、时间复杂度：
比较时间复杂度为O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。
交换次数O(n)，最好情况是，已经有序，交换0次；最坏情况下，即待排序记录初始状态是按第一条记录最大，之后的记录从大到小顺序排列，则需要移动记录的次数最多为3(n-1)。
3、空间复杂度：
O(1)。简单选择排序需要占用一个临时空间，在交换数值时使用。
