程序员须掌握的数据结构：插入排序python代码实现

插入排序，时间复杂度O(n^2)，用移位代替交换，移位操作的时间大约是交换时间的1/3。插入排序7行。

# 源码: https://github.com/SpikeKing/data_structure_with_python
def insert_sort(alist):
    """
    插入排序，子序列逐渐有序
    1. 遍历列表，存储当前值cur_val，设置游标pos
    2. 游标大于0和游标的值大于当前值，则移位，同时游标减1；
    3. 将当前值赋予游标的终止位置；
    4. 7行
    :param alist: 待排序alist
    :return: None
    """
    for i in range(1, len(alist)):
        cur_val = alist[i]
        pos = i  # 游标
        while pos > 0 and alist[pos - 1] > cur_val:
            alist[pos] = alist[pos - 1]
            pos -= 1
        alist[pos] = cur_val  # 最后游标的位置


def test_of_insert_sort():
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    insert_sort(alist)
    print(alist)


if __name__ == '__main__':
    test_of_insert_sort()
复制代码