插入排序

插入排序的定义每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。实现 原理从第一个元素开始，该元素可以认为已经被排序与第二个元素比较，如果第二个元素小于第一个元素，就把第一个元素往后挪，否则不变重复1-2步骤随着已排序部分元素个数的增加，来自未排序部分的新元素必须与已排序部分的所有元素进行比较，然后才能插入过程List = [5,2,6,4,7,9,1]第一步：选出第0位为默认排好序的第二步：未排序的为[2,6,4,7,9,1]第三步：选出2和5做比较，2<5,所以列表变为[2,5,6,4,7,9,1]第四步: 选出6和5做比较，5<6,所以原列表不变第五部: 选出4和6做比较，6>4,所以6的位置插入到4后面，但是5又比4大….. 原列表为[2,4,5,6,7,9,1]第六步: 再选出6和7做比较，原列表不动第七步：选出7和9做比较第八步：选出9和1做比较代码 # def insert(list):# # 确认循环次数# for i in range(1, len(list)):# # 确认需要排序的元素# temp = list[i]# # 把当前的元素与已经排好序的元素做比较交换# while i > 0 and list[i-1] > temp:# # 把已经排好序的元素想后移动一位,留下插入的位置# list[i] = list[i-1]# i -= 1# # 把需要排好序的元素插入到指定位置# list[i] = temp# return list # print(insert([5, 2, 6, 4, 7, 9, 1])) import numpy as np def insert(list): b = [list[0], np.inf] for i in range(1, len(list)): #b列表是正确的顺序，第二个for循环是将list[i]一一与b的比较 for x in range(len(b)): #这样插入的时候只要判断<=即可， #不用担心这个数是最大的一个， #因为在大打不过inf if list[i] <= b[x]: b.insert(x,list[i]) print(b) break b.pop() return b print(insert([5, 2, 6, 4, 7, 9, 1]))