用Python實(shí)現(xiàn)插入排序和選擇排序

shiina 發(fā)布于2019-07-31 10:24 / 1107人閱讀

摘要：具體實(shí)現(xiàn)步驟為首先我們把整個(gè)數(shù)組拆分為有序區(qū)間和未排序區(qū)間，有序區(qū)間在插入排序一開始只有一個(gè)元素，就是數(shù)組的第一個(gè)元素。

這篇是我關(guān)于用Python實(shí)現(xiàn)50個(gè)經(jīng)典算法代碼的第一篇文章，主要目的是在自己手寫一遍算法之后，在文章中對(duì)算法的細(xì)節(jié)進(jìn)行總結(jié)來加以鞏固。

話不多說，讓我們從最基本的排序算法開始吧

插入排序

如下圖所示，插入排序的實(shí)現(xiàn)思路顧名思義，就是不斷地在一個(gè)已經(jīng)是有序的數(shù)組中，尋找合適位置并插入新元素。

具體實(shí)現(xiàn)步驟為：

首先我們把整個(gè)數(shù)組拆分為有序區(qū)間和未排序區(qū)間，有序區(qū)間在插入排序一開始只有一個(gè)元素，就是數(shù)組的第一個(gè)元素。

接在有序區(qū)間之后的一個(gè)元素就是準(zhǔn)備插入的元素，在圖中就是標(biāo)為綠色的元素，在有序區(qū)間內(nèi)尋找位置并插入。

其尋找邏輯為：從后往前依次進(jìn)行比較，如果待插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位，如果待插入元素小于當(dāng)前元素，則將當(dāng)前元素后移一位。不斷重復(fù)該過程直至到數(shù)組的最后一位

其實(shí)現(xiàn)的具體代碼為：

def insertion_sort(a):
    length = len(a)
    if length <=1:
        return 
    for i in range(1,length):
        j = i-1
        value = a[i]
        while j >=0:
            if a[j]
時(shí)間復(fù)雜計(jì)算為：我們需要將整個(gè)數(shù)組遍歷一遍，所以這一部分為O(n)，在每一次遍歷中都要執(zhí)行一次插入操作，其時(shí)間復(fù)雜度為O(n)，所以總時(shí)間復(fù)雜度為O(n2)
選擇排序
選擇排序跟插入排序算法類似，都是將數(shù)組分為有序區(qū)間和未排序區(qū)間，區(qū)別在于插入排序是將一個(gè)新元素插入到有序區(qū)間內(nèi)，而選擇排序則是在未排序區(qū)間中找到最小元素，并交換到有序區(qū)間之后。

實(shí)現(xiàn)代碼為：
def selection_sort(a):
    length = len(a)
    if length <=1:
        return
    for i in range(0,length-1):
        min_value = a[i]
        min_index = i
        j = i+1
        while j
時(shí)間復(fù)雜度計(jì)算：數(shù)組長(zhǎng)度為n，一共需要尋找n次最小值，每次尋找最小值都要遍歷未排序區(qū)間一次，其時(shí)間復(fù)雜度為O(n)，乘以n次為O(n2)