理解插入排序：问题驱动的方法

百变鹏仔 4天前 #Python

文章标签方法

在这篇博文中，我们将采用问题驱动的方法来了解插入排序算法的基础知识。当我试图找到一种更好的方法来理解插入算法和我即将学习的其他算法时，我想到了这种方法。我想建立一个可以应用于我将要学习的大多数（如果不是全部）算法的策略。当我思考这个问题时，我确信我可能必须使用第一原理思考

受到第一原理思维的启发，这种方法首先要尝试掌握算法，无论我们最初的理解是模糊还是清晰。然后，我们确定构成算法的微小概念或机制。通过围绕这些机制或微小概念提出问题。我们本质上是试图从不同的小角度理解算法的工作原理，重点是尝试解决我们自己形成的问题。

您形成的答案最初可能与实际算法中使用的语法相似，也可能不相似。目标应该是自己回答问题，无论语法是否接近。一旦你有了清晰的理解，你就可以转换、合并你的答案以使用语法，类似于算法的实际实现。我相信这个过程可以让您探索代码的替代形式，理解为什么使用特定语法，以更好的方式自行处理边缘情况。

我相信这种方法可以确保我们理解每行代码背后的理论和推理，使实现过程更加直观和有意义。以下问题和我经历的思考过程帮助我更好地理解插入排序，并使我能够有效地编码。

对于你来说，问题可能会有所不同；它们可以更多、更少或完全不同。有人可能会说这类似于逆向工程，不管你怎么称呼它，这个方法让我对插入排序算法有了透彻的了解。我希望它对您的任何其他算法也能起到同样的作用。苏，让我们开始吧！

插入排序实现

这是我们最终将实现插入排序的代码形式。

def insertion_sort(values):    for new_value_index in range(1,len(values)):        new_value = values[new_value_index]        index = new_value_index-1        while index>=0:            if values[index]<new_value:break            values[index+1] = values[index]            index-=1        values[index+1] = new_value

问题

给定一个排序列表，使用 while 循环，从右到左打印值。

values = [4,8,12,16,20,24,30]# given a sorted list, using while loop, print values from right to left.index = len(values)-1while index>=0:    print(values[index],end = " ")    index-=1

给定一个排序列表和一个新值，找到要插入新值的索引以保持列表排序。

values = [4, 8, 12, 16, 20, 24]new_value = 14# using while loop, if traversing from right to leftindex = len(values)-1while index>=0:    if values[index]<new_value: break    index-=1print(values,new_value,index)

给定一个排序列表和一个新值，将新值插入到列表中，使其保持排序。

values = [4, 8, 12, 16, 20, 24]new_value = 14# if traversal from right to leftindex = len(values)-1while index>=0:    if values[index]<new_value:break    index-=1values = values[:index+1] + [new_value] + values[index+1:]print(values)

给定一个排序列表，然后附加一个新值，将新值移动到给定的索引位置。

values = [4, 8, 12, 16, 20, 24, 30]new_value = 14values.append(new_value)given_index = 3# above givenn = len(values)-1index = n-1while index>given_index:    values[index+1] = values[index]    index-=1print(values)values[given_index+1] = new_valueprint(values)

给定一个排序列表，然后附加一个新值，对列表进行排序。

values = [4, 8, 12, 16, 20, 24, 30]new_value = 14values.append(new_value)print(values)### given a sorted list, then appended with new value, sort the list####n = len(values)-1new_value = values[-1]# find the index at which the value is to be inserted# right to leftindex = n-1while index>=0:    if values[index]<new_value:break    index-=1given_index = index print("given_index : "  , given_index)# move the values forward by one step until we reach the given indexindex = n-1while index>given_index:    values[index+1] = values[index]    index-=1values[index+1] = new_valueprint(values)

给定一个排序列表，然后附加一个新值，对列表进行排序。

values = [4, 8, 12, 16, 20, 24, 30]new_values = [14,32]values += new_valuesprint(values)# given a sorted list, then appended with two new value(s), sort the listn = len(values)-1new_value_start_index = n - 1print(new_value_start_index, values[new_value_start_index])for new_value_index in range(new_value_start_index,len(values)):    new_value = values[new_value_index]    index = new_value_index-1    while index>=0:        if values[index]<new_value: break        values[index+1] = values[index]        index-=1    values[index+1] = new_valueprint(values)

给定一个列表，对其进行排序。

import randomvalues = random.sample(range(10,90), k = 10)values

print(values)for new_value_index in range(1,len(values)):    new_value = values[new_value_index]    index = new_value_index-1    while index>=0:        if values[index]<new_value:break        values[index+1] = values[index]        index-=1    values[index+1] = new_valueprint(values)

插入排序实现

def insertion_sort(values):    for new_value_index in range(1,len(values)):        new_value = values[new_value_index]        index = new_value_index-1        while index>=0:            if values[index]<new_value:break            values[index+1] = values[index]            index-=1        values[index+1] = new_value

其他资源

虽然我最初通过了一系列全面的问题来更好地理解算法，但我认为上述一组问题对于更好地理解插入排序非常重要。如果包含我所解决的所有问题，这篇文章就会变得相当冗长。

对于那些有兴趣查看所有问题的人，我创建了一个 jupyter notebook，其中包含全套问题和我自己的答案，这使我能够完全理解插入排序的实现。

如果您想进一步深入研究，我鼓励您查看笔记本。

欢迎指正和建议。

文章推荐

理解插入排序：问题驱动的方法

使用Networxx模块的超链接诱导主题搜索（HITS）算法- Python

使用索引列表在Python中查找元素的乘积

在Python中打印字符串的所有子序列

使用Python从字符串的末尾删除给定的子字符串

2020年适用于Linux程序员的10个最佳Python集成开发环境