使用python實作8大排序演算法-插入排序

插入排序的基本思想：

每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。

例：

       arr = [49,38,04,97,76,13,27,49,55,65]，從第2個數為關鍵值，向前比較，如前一個數大，進行交換，

       arr = [38,49,04,97,76,13,27,49,55,65]，然後從第3個數字為關鍵值，向前比較，前大則交換，

arr = [38,04,49,97,76,13,27,49,55,65]，再繼續，arr = [04,38,49,97,76,13,27,49,55,65]

       備註：依序向前比較時，因為前面的陣列是有序的，所以當前一個數小於或等於key值時，可以跳出這個向前比較的循環，演算法的速度有明顯提升。

代碼：

def insert_sort(lists):  
    #插入排序  
    count = len(lists)  
    for i in range(1,count):#从第2个数起遍历  
        key = lists[i]  
        j = i - 1  
        while j >= 0:  
            if lists[j] > key:  
                lists[j+1], lists[j] = lists[j], key  
            else: break  #当前一个数小于或等于key时，跳出循环  
            j -= 1  
    return lists