python实现插入排序

1、插入排序原理

     百度上的话，学术性太强，不容易看懂，我用自己的话复述一下插入排序原理。

     插入排序的核心在于，它把一个无序数列看成两个数列，假如第一个元素构成了第一个数列，那么余下的元素构成了第二个数列，很显然，第一个数列是有序的（因为只有一个元素嘛，肯定有序哦），那么我们把第二个数列的第一个元素拿出来插入到第一个数列，使它依然构成一个有序数列，直到第二个数列中的所有元素全部插入到第一个数列，这时候就排好序了。

      插入排序的复杂度是O(n^2)，在数据量较小时效率较高。

2、一图以明之

3、Python代码

lst = [4,5,6,3,2,1]
#print(insert_sort(lst))

def insertSort(arr):
    for i in range(1,len(arr)):
        j = i-1
        key = arr[i]
        while j >= 0:
            if arr[j] > key:
                arr[j+1] = arr[j]
                arr[j] = key
            j -= 1
    return arr
print(insertSort(lst))