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

巴扎黑
發布: 2016-11-26 11:52:46
原創
1346 人瀏覽過

插入排序的基本思想:

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

例:

       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值時,可以跳出這個向前比較的循環,演算法的速度有明顯提升。

程式碼:

 

Python程式碼  

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
登入後複製


相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板