a = [5,4,3,2,1]
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5
1：1位置开始比较，和他前面所有的数字进行比较，4和5比较，4<5所以4,5交换位置
[4,5,3,2,1]
2：2位置开始比较，和他前面所有的数字进行比较
4 3 5 2
3 4 5 2
3：3位置开始比较，和他前面所有的数字进行比较
3 4 5 2
3 4 2 5
3 2 4 5
2 3 4 5
排好序了。
依次把1坐标以后的所有元素，分别与它前面的元素进行比较
如果发生了小于的情况就插入。
原理：每次有一个数，它的前面都是排好序的，然后它要插入到
排好的序列中，插入排序
a=[3,6,1,8,4]
'''
1 [3][6] [3,6,1,8,4]
2 [3][6,1] [1,6,3]
3 [1][6,3,8] [1,6,3,8,4]
4 [1][6,3,8,4] [1,6,3,8,4]------>最小值排到了第一位，以此类推
[1,6,3,8,4]
1 [6][3] [3,6,8,4]
2 [3][6,8] [3,6,8,4]
3 [3][6,8,4] [3,6,8,4]----->[1,3,6,8,4]
[1,3,6,8,4]
1 [6][8] [6,8,4]
2 [6][8,4] [4,8,6]------>[1,3,4,8,6]
[1,3,4,8,6]
1 [8][6] [6,8]------------->[1,3,4,6,8]
'''
a = [7,3,9,1] #表示从坐标1开始，到列表最后一个元素的坐标结束,进行操作 for i in range(1,len(a)): print("****",i) #所有i坐标的元素需要依次和它前面的所有元素进行比较 for j in range(i,0,-1): print(a[j]) #如果发生了相邻的两个元素小于的情况，则交换位置 if a[j]<a[j-1]: a[j],a[j-1]=a[j-1],a[j] #否则结束当前的循环，开始下一个元素的比较循环。 else: break print(a)
插入时间复杂度：
n^2
稳定：稳定排序
方法二：
def insertion_sort(arr): """插入排序""" # 第一层for表示循环插入的遍数 for i in range(1, len(arr)): # 设置当前需要插入的元素 current = arr[i] # 与当前元素比较的比较元素 pre_index = i - 1 while pre_index >= 0 and arr[pre_index] > current: # 当比较元素大于当前元素则把比较元素后移 arr[pre_index + 1] = arr[pre_index] # 往前选择下一个比较元素 pre_index -= 1 # 当比较元素小于当前元素，则将当前元素插入在 其后面 arr[pre_index + 1] = current return arr insertion_sort([11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]) # 返回结果[11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]