算法核心思想

插入排序的核心思想是將數(shù)組中所有的元素分別和前面已經(jīng)排序好的元素相比較， 如果后面選擇的元素比已排序的元素小，則交換位置，直至比較完成。

具體實(shí)現(xiàn)邏輯

1. 取數(shù)組的第一個(gè)元素為已經(jīng)排序好的元素，將第一個(gè)元素看作有序序列
2. 取數(shù)組的第二個(gè)元素和已經(jīng)排序好的元素進(jìn)行比較，如果第二個(gè)元素比第一個(gè)元 素小，則交換位置，排序完成后第一個(gè)元素和第二個(gè)元素必然有序，形成新的有 序數(shù)列
3. 取數(shù)組的第三個(gè)元素，依次和第一個(gè)第二個(gè)元素進(jìn)行比較，排序完成后第一個(gè)， 第二個(gè)，第三個(gè)元素形成一個(gè)有序數(shù)列
4. 重復(fù)取第四個(gè)元素，第五個(gè)元素，第六個(gè)元素。。。
5. 最后一個(gè)元素重復(fù)上述步驟，最終實(shí)現(xiàn)整個(gè)數(shù)組有序

實(shí)現(xiàn)邏輯圖示

代碼實(shí)現(xiàn)-WHILE版本

def insertSort(arr): 
    i = 1
    while i<len(arr):
        j = i 
        while j>=1: 
            if arr[j]<arr[j-1]: 
                arr[j-1],arr[j] = arr[j],arr[j-1] 
                j-=1 
            else: 
                break 
        i+=1 
    return arr

代碼實(shí)現(xiàn)-FOR版本

def insertSort(arr):
    #拆分?jǐn)?shù)組為有序部分和無序部分
    #有序部分：arr[0]
    #無序部分：arr[1:]
    #取無序部分的元素
    for i in range(1,len(arr)):
        #arr[i]就是我們待插入的元素
        #arr[:i]是有序數(shù)組
        #arr[i:]是無序數(shù)組
        #將arr[i]插入到0到i-1的元素?cái)?shù)組里面
        #具體排序過程
        for j in range(i,0,-1):
            if arr[j]<arr[j-1]:
                arr[j],arr[j-1] = arr[j-1],arr[j]
            else:
                break
    return arr
arr = [1,22,-1,9,23,5,9,9,2,23,1,2999,92,1]
print(insertSort(arr))

時(shí)間復(fù)雜度分析

1. 在最好的情況下，即序列已經(jīng)是排好序的情況下，每次比較一次就退出while循環(huán)，則總比較次數(shù) 是n-1次，時(shí)間復(fù)雜度是O(n)
2. 在最壞的情況下，即每次while循環(huán)都要比較到第一個(gè)元素，則：
3. 第一次循環(huán)，比較了1次；
4. 第二次循環(huán)，比較了2次；
5. ...
6. 第n-1次循環(huán)，比較了n-1次；
7. 總的比較次數(shù)是1+2+3+...+(n-1) = n(n-1)/2
8. 我們上面所求得的n(n-1)/2，其時(shí)間復(fù)雜度，最大的影響因子是n²/2，故其時(shí)間復(fù)雜度是O(n²)。

優(yōu)缺點(diǎn)分析

1. 在大多數(shù)元素已經(jīng)有序的情況下，插入排序的工作量較小，這個(gè)結(jié)論很明顯，如果 一個(gè)數(shù)組大部分元素都有序，那么數(shù)組中的元素自然不需要頻繁地進(jìn)行比較和交換。
2. 在元素?cái)?shù)量較少的情況下，插入排序的工作量較小，這個(gè)結(jié)論更加顯而易見，插入 排序的工作量和n的平方成正比，如果n比較小，那么排序的工作量自然要小得多。
3. 插入排序是一種穩(wěn)定排序（穩(wěn)定的定義：相同元素的位置沒有發(fā)生變化）

執(zhí)行解析

外層for遍歷讀取第n個(gè)元素，當(dāng)讀取第n個(gè)元素的時(shí)候前面n-1個(gè)元素是已經(jīng)排序好 的序列，使用第n個(gè)元素和前面的n-1個(gè)元素進(jìn)行依次比較，如果某一個(gè)元素比較的 時(shí)候比第n個(gè)元素大，則交換該元素和第n個(gè)元素的位置，這樣比較輪下來從第0個(gè) 元素到第n個(gè)元素就是一個(gè)有序序列了。