选择排序
前面我们的二分查找，输入的数组是一个有序的数组，所以我们该如何得到一个有序的数组哪？排序算法有很多种我们这次来研究一下选择排序。
输入，输出
输入一个无序数组，输出一个有序数组
设计与实现
设计
基本思路：我们假设数组只有一个元素，那我们就直接返回数组，如果数组大于两个元素，我们才会进行排序。我们可以从数组中找出最小的，然后把它加入一个新的数组，然后把它从老的数组中删除，这样等到老数组为空了，那么新数组也就是一个有序的数组了。
选择排序.jpg
实现
def findSmall(list):
minNumber = list[0]
for item in list:
if item < minNumber:
minNumber = item
return list.index(minNumber)
def selectionSort(list):
if len(list) <= 1:
return list
newArray = []
for i in range(len(list)):
minNumberIndex = findSmall(list)
newArray.append(list.pop(minNumberIndex))
return newArray
print selectionSort([3])
关键点
- 我们写了一个辅助函数来查找最小值
- 把找到的最小值从老数组中删除，加入到新数组，返回新数组
- 算法复杂度为n的平方
