算法學(xué)習(xí)：簡單選擇排序

題目：給定一個數(shù)組 [3,2,11,-9,0,12]，如何將這個數(shù)組進(jìn)行排序，得到一個有序序列

排序過程：

　　1.選擇數(shù)組中最小元素的索引（從0到length-1），和第一個元素（索引為0） 的兩個值交換位置：[-9,2,11,3,0,12]

　　2.選擇數(shù)組中最小元素的索引（從1到length-1），和第一個元素（索引為0） 的兩個值交換位置：[-9,0,11,3,2,12]

　　3.選擇數(shù)組中最小元素的索引（從2到length-1），和第一個元素（索引為0） 的兩個值交換位置：[-9,0,2,3,11,12]

排序思路總結(jié)：

　　1.選擇的次數(shù)為len(arr) :arr 為需要排序的數(shù)組

　　2.選擇的序列逐漸縮短

　　3.找到最小元素的索引

Python代碼：

def selectSort(arr):
    length = len(arr)
    for i in range(length):
        min_value_index = i
        for j in range(i+1,length):
            if arr[j] < arr[min_value_index]:
                min_value_index = j
        arr[i],arr[min_value_index] = arr[min_value_index],arr[i]
    return arr

arr = [3,2,11,-9,0,12]
print(selectSort(arr)) #[-9, 0, 2, 3, 11, 12]

時間復(fù)雜度：O(n^2)

補(bǔ)充：每次排序，元素相對位置都改變了，所以選擇排序是不穩(wěn)定的。