插入排序（Python实现）

原理

在列表较低的一端维护一个有序的子列表，并逐个将后面每个新元素“插入”这个子列表。

1. 将待排序列表的第一个元素当做已排序序列，第二个元素到最后一个元素当成未排序序列。
2. 取未排序序列中的第一个数据，插入到已排序序列中顺序正确的位置。将未排序的第一个数据与相邻的前一个数据(已排序序列的最后一个数)据进行比较，如果顺序错误则交换位置，交换位置后继续与相邻的前一个数据进行比较，直到不需要交换则插入完成。每次插入数据后，已排序序列都是排好序的。
3. 重复上一步，继续插入下一个数据。每进行一次插入，已排序序列的长度加1，未排序序列的长度减1，直到列表中的所有数据都插入到已排序序列了，则列表排序完成。

时间复杂度

插入排序的时间复杂度也是O(n²)。

Python 实现

# -*- coding: UTF-8 -*-
# 插入排序

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            position = position-1

        alist[position] = currentvalue
    return alist