排序算法之 '插入排序'

python實作排序算法中的插入排序

插入排序

插入排序是指在待排序的元素中，假設前面n-1(其中n>=2)個數已經是排好順序的，現将第n個數插到前面已經排好的序列中，然後找到合适自己的位置，使得插入第n個數的這個序列也是排好順序的。按照此法對所有元素進行插入，直到整個序列排為有序的過程，稱為插入排序

算法穩定性

插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列隻有1個元素，就是第一個元素。比較是從有序序列的末尾開 始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相 等的，那麼插入元素把想插入的元素放在相等元素的後面。是以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，是以插入排序是穩定的排序算法。

Python實作

def inset_sort(lst):
    length = len(lst)
    for i in range(1, length):
        while i > 0:
            if lst[i] < lst[i - 1]:
                lst[i], lst[i - 1] = lst[i - 1], lst[i]
                i -= 1
            else:
                break
    return lst


if __name__ == '__main__':
    lst = [3, 4, 5, 7, 1, 2, 6, 9, 0]
    print(inset_sort(lst))


 
# [0, 1, 2, 3, 4, 5, 6, 7, 9]
           

抟扶搖而上者九萬裡