Python程式設計：排序算法之插入排序

插入排序

清單被分為有序區和無序區兩個部分，最初有序區隻有一個元素

每次從無序區選擇一個元素，插入到有序區的位置，直到無需去變空

代碼實作

# -*- coding: utf-8 -*-

# @File    : insert_sort_demo.py
# @Date    : 2018-06-11


import random

# 插入排序 O(n^2)
def insert_sort(lst):
    count = 0
    for i in range(1, len(lst)):
        tmp = lst[i]
        j = i - 1
        while j >=0 and tmp < lst[j]:
            lst[j+1] = lst[j]
            j -= 1
            count += 1
        lst[j+1] = tmp
    print("count: %s"% count)

lst = list(range(10))
random.shuffle(lst)
insert_sort(lst)
print(lst)
# count: 20
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]