选择排序

前面我们的二分查找，输入的数组是一个有序的数组，所以我们该如何得到一个有序的数组哪？排序算法有很多种我们这次来研究一下选择排序。

输入，输出

输入一个无序数组，输出一个有序数组

设计与实现

设计

基本思路：我们假设数组只有一个元素，那我们就直接返回数组，如果数组大于两个元素，我们才会进行排序。我们可以从数组中找出最小的，然后把它加入一个新的数组，然后把它从老的数组中删除，这样等到老数组为空了，那么新数组也就是一个有序的数组了。

选择排序.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的平方