python插入排序实现及详解

插入排序的思想：

插入排序的思想就是将待排序的数据插入到其合适的位置。我们先从一个简单的例子开始，假如现在有

lst= [1,2,6,7,5]

这个list基本有序，只要将5放到6之前就能完成排序。从7开始遍历，比5大的向右移动，遇到小于5的就停下来. 具体来说，从7开始向左遍历，遇到比5大的数向右移动，遇到小于等于5的数就停下来，这个位置就是5应该在的位置。但是当7向右移动的时候，占据的5的位置，那么就需要把5这个位置的数据保存下来，同时还需要把向左遍历时的索引记录记下来，最后索引停下的地方，就是5应该在的位置

实现

def insert(lst,index):
    if lst[index-1] < lst[index]:
        return
    temp = lst[index]
    temp_index = index
    while temp_index > 0 and lst[index-1] > temp:
        lst[temp_index] = lst[temp_index-1]
        temp_index = temp_index - 1
    lst[temp_index] = temp
    
def insert_sort(lst):
    for i in range(1,len(lst)):
        insert(lst,i)

lst = [10,3,9,1,7]
insert_sort(lst)
print(lst)

过程详细注释解析

def insert(lst,index):
	if lst[index - 1] < lst[index]:#如果需要比较的数的前面的数比当前的数小，那还比啥比，直接return返回
		return
	#当上面不成立的时候，说明需要比较了。
	temp = lst[index] #记住当前要比较的数
	temp_index = index #记住当前的索引
	while temp_index > 0 and lst[temp_index - 1] > temp:#当索引比0大而且前面的数却是比当前的数大，那么进入这个循环
		lst[temp_index] = lst[temp_index - 1] #把当前的位置的数据变为前面的比自己大的数据
		temp_index = temp_index - 1 #索引向前移动一个，防止前面还需要比较，也就是当前的位置还不是最终放的位置
	lst[temp_index] = temp 
	# 对lst[temp_index] = temp的解释
	# 刚才我们不是把当前的位置数据用前面一个数据覆盖了吗？
	# 这个过程在while中会不断出现，直到找到正确的位置，找到正确的位置后，我们要将该位置的数据改为我们当前的temp。
	# 比如一轮循环后，lst应该变成了[1,2,6,7,7],再一轮循环后，lst变成了[1,2,6,6,7]。
	# 此时5找到了合适的位置了，那么这个6已经往后移动了，我们需要将第一个6替换为5

def insert_sort(lst):
	for i in range(1,len(lst)):#这个地方从1开始，因为我们进入insert函数后，是有个index-1的，我们还是从第一个元素开始比较的，没问题。不可以从0开始，从0开始就越界了。
		insert(lst,i)
lst = [1,2,6,7,5]
insert_sort(lst)
print(lst)

我们输出一下在while循环中每次的lst看下， 可以看出和上面的分析是一样的

我们再看看每一轮排序后的lst 这其中while的循环是选择排序的灵魂所在