排序算法之插入排序

一、原理

将序列分為有序區和無序區兩個部分，剛開始有序區隻有一個元素，每次從無序區選擇一個元素插入到有序區的位置，直到無序區為空。

關鍵點：

• 插入到有序區時遵循從後向前進行掃描，然後将無序區的元素插入。
• 此時無序區的第一個元素作為有序區的第一個元素

二、實作

def insert_sort(li):

    for i in range(1,len(li)): #對無序區的元素進行循環，i表示第一個元素的下标，因為有序區已經有一個元素了
        temp=li[i] #将無序區取出的元素進行儲存
        j=i-1 #是有序區的最後一個位置下标
        while j>=0 and li[j]>temp: #j表示有序區的元素
            li[j+1]=li[j] #将有序區的元素向後移動，因為從無序區已經取出一個元素，空了一個位置
            j-=1 #有序區的元素繼續向前循環比較
            
        #将無序區的元素插入到有序區
        li[j+1]=temp  

l=[3,5,2,9]
insert_sort(l)
print(l) #[2, 3, 5, 9]      

總結：

• 有序區已經有一個元素，第一層循環無序區是從第二個元素開始
• 無序區的元素需要儲存，防止被覆寫
• while循環無序區從後向前
• 有序區需要元素後移以便無序區的元素插入

 原文：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/3.insertionSort.md

作者：iveBoy

出處：http://www.cnblogs.com/shenjianping/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須在文章頁面給出原文連接配接，否則保留追究法律責任的權利。