插入排序(python实现)

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序步骤

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

• 从头到尾依次扫描未排序序列，将未排序的每个元素插入有序序列的适当位置。

• 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

• 插入时，插入位置之后的所有数往后移动一位，然后将待插入的元素插入到该位置。

# -*- coding:utf-8 -*-

def insertion_sort(arr):
    '''
    插入排序
    '''
    # 索引为0的第一个元素，其为有序序列，无须再插入
    for i in range(1, len(arr)):
        pre_index = i-1  # 有序序列的最后一个元素的索引
        current = arr[i]  # 保存当前的数据
        # 待排元素小于有序序列的最后一个元素时，一直向前插入
        while pre_index >= 0 and arr[pre_index] > current:
            arr[pre_index+1] = arr[pre_index]  # 向前插入：即原数据往后退一位
            pre_index -= 1
        arr[pre_index+1] = current  # 将current数据插入最终的合适位置
    return arr


if __name__ == '__main__':
    array = [2, 4, 1, 3, 5, 8, 7, 8, 4, 1]
    print insertion_sort(array)

插入排序复杂度

1.时间复杂度：

• 平均时间复杂度：O(n^2)
• 最大时间复杂度：O(n^2)
• 最小时间复杂度：O(n)

2. 空间复杂度：O(1)
3. 稳定性：稳定