插入排序

image.png

当31要插入已排序部分的具体操作

image.png

# coding utf8

'''
插入排序：算法O(n^2)
概述：
把列表分为两部分，一部分是排序好的，另一部分是待插入的
每次插入一个待插入的，并与排序好的部分进行比较，然后插入到正确位置上。
思路：
首先传入一个数组，从下标1开始到数组的长度-1进行遍历
把要插入的值视为当前值，下表视为当前下标。
循环判断该下标是否大于0并且下标为0到当前下标-1的值是否大于当前值
如果是就交换位置，并且当前下标-1，如果不是就说明当前比前面的值都大。
'''

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                              # 最后才插入


alist = [54,26,93,17,77,31,4,55,20]
insertionSort(alist)
print(alist)

# [4, 17, 20, 26, 31, 54, 55, 77, 93]