首页 后端开发 Python教程 理解插入排序:问题驱动的方法

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

Oct 16, 2024 pm 04:13 PM

Understanding Insertion Sort: A Question-Driven Approach

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

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

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

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

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

插入排序实现

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

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)-1
while 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 left

index = len(values)-1
while index>=0:
    if values[index]<new_value: break
    index-=1

print(values,new_value,index)
登录后复制

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

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# if traversal from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value:break
    index-=1

values = values[:index+1] + [new_value] + values[index+1:]
print(values)
登录后复制

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

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

given_index = 3

# above given

n = len(values)-1

index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

print(values)

values[given_index+1] = new_value

print(values)
登录后复制

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

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

print(values)

### given a sorted list, then appended with new value, sort the list
####

n = len(values)-1
new_value = values[-1]

# find the index at which the value is to be inserted
# right to left
index = n-1
while index>=0:
    if values[index]<new_value:break
    index-=1
given_index = index 
print("given_index : "  , given_index)

# move the values forward by one step until we reach the given index
index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

values[index+1] = new_value

print(values)
登录后复制

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

values = [4, 8, 12, 16, 20, 24, 30]

new_values = [14,32]

values += new_values

print(values)

# given a sorted list, then appended with two new value(s), sort the list

n = len(values)-1

new_value_start_index = n - 1

print(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_value

print(values)
登录后复制

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

import random

values = 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_value

print(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,其中包含全套问题和我自己的答案,这使我能够完全理解插入排序的实现。

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

欢迎指正和建议。

以上是理解插入排序:问题驱动的方法的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

<🎜>:泡泡胶模拟器无穷大 - 如何获取和使用皇家钥匙
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系统,解释
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆树的耳语 - 如何解锁抓钩
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

热门话题

Java教程
1675
14
CakePHP 教程
1429
52
Laravel 教程
1333
25
PHP教程
1278
29
C# 教程
1257
24
Python与C:学习曲线和易用性 Python与C:学习曲线和易用性 Apr 19, 2025 am 12:20 AM

Python更易学且易用,C 则更强大但复杂。1.Python语法简洁,适合初学者,动态类型和自动内存管理使其易用,但可能导致运行时错误。2.C 提供低级控制和高级特性,适合高性能应用,但学习门槛高,需手动管理内存和类型安全。

学习Python:2小时的每日学习是否足够? 学习Python:2小时的每日学习是否足够? Apr 18, 2025 am 12:22 AM

每天学习Python两个小时是否足够?这取决于你的目标和学习方法。1)制定清晰的学习计划,2)选择合适的学习资源和方法,3)动手实践和复习巩固,可以在这段时间内逐步掌握Python的基本知识和高级功能。

Python vs.C:探索性能和效率 Python vs.C:探索性能和效率 Apr 18, 2025 am 12:20 AM

Python在开发效率上优于C ,但C 在执行性能上更高。1.Python的简洁语法和丰富库提高开发效率。2.C 的编译型特性和硬件控制提升执行性能。选择时需根据项目需求权衡开发速度与执行效率。

Python vs. C:了解关键差异 Python vs. C:了解关键差异 Apr 21, 2025 am 12:18 AM

Python和C 各有优势,选择应基于项目需求。1)Python适合快速开发和数据处理,因其简洁语法和动态类型。2)C 适用于高性能和系统编程,因其静态类型和手动内存管理。

Python标准库的哪一部分是:列表或数组? Python标准库的哪一部分是:列表或数组? Apr 27, 2025 am 12:03 AM

pythonlistsarepartofthestAndArdLibrary,herilearRaysarenot.listsarebuilt-In,多功能,和Rused ForStoringCollections,而EasaraySaraySaraySaraysaraySaraySaraysaraySaraysarrayModuleandleandleandlesscommonlyusedDduetolimitedFunctionalityFunctionalityFunctionality。

Python:自动化,脚本和任务管理 Python:自动化,脚本和任务管理 Apr 16, 2025 am 12:14 AM

Python在自动化、脚本编写和任务管理中表现出色。1)自动化:通过标准库如os、shutil实现文件备份。2)脚本编写:使用psutil库监控系统资源。3)任务管理:利用schedule库调度任务。Python的易用性和丰富库支持使其在这些领域中成为首选工具。

科学计算的Python:详细的外观 科学计算的Python:详细的外观 Apr 19, 2025 am 12:15 AM

Python在科学计算中的应用包括数据分析、机器学习、数值模拟和可视化。1.Numpy提供高效的多维数组和数学函数。2.SciPy扩展Numpy功能,提供优化和线性代数工具。3.Pandas用于数据处理和分析。4.Matplotlib用于生成各种图表和可视化结果。

Web开发的Python:关键应用程序 Web开发的Python:关键应用程序 Apr 18, 2025 am 12:20 AM

Python在Web开发中的关键应用包括使用Django和Flask框架、API开发、数据分析与可视化、机器学习与AI、以及性能优化。1.Django和Flask框架:Django适合快速开发复杂应用,Flask适用于小型或高度自定义项目。2.API开发:使用Flask或DjangoRESTFramework构建RESTfulAPI。3.数据分析与可视化:利用Python处理数据并通过Web界面展示。4.机器学习与AI:Python用于构建智能Web应用。5.性能优化:通过异步编程、缓存和代码优

See all articles