Python插入排序算法

Num01–>定义

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

Num02–>排序过程分析图

Num03–>Python代码实现

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author  : xiaoke


def insert_sort(alist):
    """插入排序"""
    n = len(alist)
    for j in range(1, n):
        # 控制将拿到的元素放到前面有序序列中正确位置的过程
        for i in range(j, 0, -1):
            # 如果比前面的元素小，则往前移动
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
            # 否则代表比前面的所有元素都小，不需要再移动
            else:
                break


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print("原列表为：%s" % alist)
    insert_sort(alist)
    print("新列表为：%s" % alist)

# 结果如下：
# 原列表为：[54, 26, 93, 17, 77, 31, 44, 55, 20]
# 新列表为：[17, 20, 26, 31, 44, 54, 55, 77, 93]

Num04–>时间复杂度分析

最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
最坏时间复杂度：O(n2)
稳定性：稳定