算法核心思想

選擇排序的算法核心思想是從數(shù)組中選擇最小的元素，放到第一個位置，再從數(shù)組 中選擇第二小的元素放到第二個位置，一直到數(shù)組的最后一個元素為止。

選擇排序的具體實現(xiàn)步驟

1. 選擇數(shù)組的第一小的元素，將其放在第一個位置
2. 選擇數(shù)組的第二小的元素，將其放在第二個位置
3. 重復(fù)上述步驟。。。
4. 選擇數(shù)組的第三小的元素，將其放在第n個位置

代碼實現(xiàn)

def selectSort(arr):
    length = len(arr)
    for i in range(length):
        min_value_index = i
        #查找數(shù)組的最小值的索引
        for j in range(i+1,length):
            if arr[j] < arr[min_value_index]:
                min_value_index = j
        #將最小值放到第i個位置
        arr[i],arr[min_value_index] = arr[min_value_index],arr[i]
    return arr

執(zhí)行解析

使用2層for循環(huán)，外層循環(huán)控制查找第幾小的元素，用于真正的查找，當(dāng)內(nèi)層循環(huán) 找到第n小的元素的時候，將其放置在第n個位置。當(dāng)所有的元素都放置結(jié)束后，排 序結(jié)束。

時間復(fù)雜度分析&穩(wěn)定性

選擇排序時間復(fù)雜度是0( n²)，選擇排序是一種不穩(wěn)定排序，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順 序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法。