算法理解之排序-選擇排序

選擇排序是一種簡單直觀的排序算法, 以當(dāng)前點(diǎn)為錨點(diǎn), 向后依次進(jìn)行比較所有未排序元素, 若比較元素小于錨點(diǎn)元素, 則將錨點(diǎn)重標(biāo)為小元素位置. 當(dāng)比較到最后一個(gè)元素時(shí), 將錨點(diǎn)位置元素與未排序第一位元素交換.

算法分析

1. 以當(dāng)前位置元素為錨點(diǎn).
2. 依次比較未排序的所有元素, 若有小于錨點(diǎn)元素, 則將更小元素標(biāo)為錨點(diǎn)元素.
3. 將錨點(diǎn)元素與未排序第一元素交換位置.
4. 執(zhí)行步驟1``步驟2``步驟3直到元素遍歷完成.

動圖效果

選擇排序.gif

時(shí)間復(fù)雜度與空間復(fù)雜度與穩(wěn)定性

穩(wěn)定性: 不穩(wěn)定
時(shí)間復(fù)雜度: O(N^2)
空間復(fù)雜度: O(1)

穩(wěn)定性分析: 錨點(diǎn)位置永遠(yuǎn)要新于已排序位置, 而無論選擇元素是否為原錨點(diǎn)元素, 錨點(diǎn)標(biāo)記循環(huán)完成時(shí), 都要與未排序的第一個(gè)元素交換(可能是自身交換自身).
時(shí)間復(fù)雜度解析: 選擇排序一共有兩次迭代, 外層確保所有元素均會被遍歷, 內(nèi)層迭代來選擇未排序的元素與錨點(diǎn)間關(guān)系. 所以時(shí)間為O(N^2).
空間復(fù)雜度解析: 所有排序均在當(dāng)前列表中完成, 不存在額外使用內(nèi)存情況. 所以空間復(fù)雜度為O(1).

代碼示例

def select_sort(li):
    # 獲取鏈表長度
    li_len = len(li)
    # 外層循環(huán), 確保所有元素被便利
    for i in range(0, li_len - 1):
        # 錨點(diǎn)標(biāo)記
        anchor = i
        # 第二層循環(huán), 重新定位錨點(diǎn)
        for j in range(i, li_len -1 ):
            # 確認(rèn)錨點(diǎn)是否需要變更
            if li[anchor] > li[j + 1]:
                anchor = j + 1
        # 變更錨點(diǎn), 這句話證明其為不穩(wěn)定
        li[anchor], li[i] = li[i], li[anchor]
    return li