Python实现插入排序

'''
插入排序原理：将待排序序列的第一个元素当做已排序序列，其他的元素当做未排序序列，取未排序的第一个元素与已排序的最后一个元素进行比较，
如果未排序的第一个元素小于已排序的最后一个元素则交换位置，交换位置后继续与前一个相邻位置的元素进行比较，当不需要交换时，则次轮插入完成。
继续循环上面步骤，每进行一轮插入，已排序的序列加1，未排序的序列减1，一直到列表中的元素全部被插入到已排序的序列中为止，插入排序完毕。
例如数组：{38,65,97,76,13,27,49}，具体排序过程如下：
第1轮插入38以后：[38] 65 97 76 13 27 49
第2轮插入65以后：[38 65] 97 76 13 27 49
第3轮插入97以后：[38 65 97] 76 13 27 49
第4轮插入76以后：[38 65 76 97] 13 27 49
第5轮插入13以后：[13 38 65 76 97] 27 49
第6轮插入27以后：[13 27 38 65 76 97] 49
第7轮插入49以后：[13 27 38 49 65 76 97]
'''
#实现代码
def insert_sort(arrays):
    count=len(arrays)
    for i in range(count):
        key=arrays[i]
        j=i-1
        while j>=0 and key<arrays[j]:
            arrays[j+1]=arrays[j]
            arrays[j]=key
            j-=1
    return arrays

if __name__ == '__main__':
    arrays = [38, 65, 97, 76, 13, 27, 49]
    print("排序前：" + str(arrays))
    print("排序后：" + str(insert_sort(arrays)))

看一下执行结果：

时间复杂度：

插入排序中每一轮插入都需要移动到最左端,需要进行 n-1 轮"插入",每一轮"插入"需要向前比较和移动 i 次,i 的平均值为 n/2, 时间复杂度为 T(n)=n(n-1)/2,再乘每次操作的步骤数,所以插入排序的时间复杂度为: O(n2)

空间复杂度：O(1)

欢迎大家关注我的微信公众号