選擇排序

前面我們的二分查找，輸入的數(shù)組是一個(gè)有序的數(shù)組，所以我們?cè)撊绾蔚玫揭粋€(gè)有序的數(shù)組哪？排序算法有很多種我們這次來研究一下選擇排序。

輸入，輸出

輸入一個(gè)無序數(shù)組，輸出一個(gè)有序數(shù)組

設(shè)計(jì)與實(shí)現(xiàn)

設(shè)計(jì)

基本思路：我們假設(shè)數(shù)組只有一個(gè)元素，那我們就直接返回?cái)?shù)組，如果數(shù)組大于兩個(gè)元素，我們才會(huì)進(jìn)行排序。我們可以從數(shù)組中找出最小的，然后把它加入一個(gè)新的數(shù)組，然后把它從老的數(shù)組中刪除，這樣等到老數(shù)組為空了，那么新數(shù)組也就是一個(gè)有序的數(shù)組了。

選擇排序.jpg

實(shí)現(xiàn)

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])

關(guān)鍵點(diǎn)

• 我們寫了一個(gè)輔助函數(shù)來查找最小值
• 把找到的最小值從老數(shù)組中刪除，加入到新數(shù)組，返回新數(shù)組
• 算法復(fù)雜度為n的平方