1.python实现直接插入排序算法
参考动图：
https://ask.qcloudimg.com/http-save/developer-news/fhf3o8po46.gif
# 直接插入排序，升序 arr = [9, 5, 3, 2, 1, -9, 4] for i in range(1, len(arr)): # 外层循环为(n-1)*i*O(1)，即为O(n^2) j = i a = arr[i] # 当前为i，逆序则向后移动一位，直到不满足的那个j，退出循环 while j > 0 and a < arr[j - 1]: # 一次比较为O(1)，内层循环为i*O(1) arr[j] = arr[j - 1] # 所谓插入的实现，其实是本步先后移，跳出内循环后再赋值 j = j - 1 arr[j] = a # 每次赋值为一趟，共n-1趟，每趟向前比较，最多比较i次 print(arr)
2.时间复杂度分析
while j > 0 and a < arr[j - 1]: # 一次比较为O(1)，内层循环为i*O(1)
for i in range(1, len(arr)): # 外层循环为(n-1)*i*O(1)，即为O(n^2)
3.插入排序分类
直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）
属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置）
原文：https://www.cnblogs.com/sybil-hxl/p/11537639.html