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

插入排序，时间复杂度O(n^2)，使用shift代替swap，shift操作时间约为swap时间的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()
复制代码

作者：SpikeKing
来源：掘金