2018-07-10插入排序

插入排序

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

插入算法， 仍然把序列视为两个部分：有序和无序

选择排序：认为序列最左部分有序，右边无序，把最小值依次放入最左边
插入排序：把右边的元素与最左边从右向左比对，放入合适位置

代码实现：

# coding:utf-8

def insert_sort(alist):
    """插入排序"""
    n = len(alist)
    # 从右边的无序序列中取出多少个元素执行这样的过程
    for j in range(1, n):
        # i = [1,2,3,,,,,n]
        # i代表内层循环起始
        i = j
        # 执行从右边的无序序列中取出第一个元素，即i位置的元素
        # 然后将其插入到前面的正确位置中
        while i>0:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break

if __name__ == "__main__":
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(alist)
    insert_sort(alist)
    print(alist)

对于特殊情况，比如原本就是有序序列，最优时间复杂度O(n)
最坏时间复杂度O(n*n)

实现结果：

插入排序

时间复杂度

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