草庐IT

python - 傻瓜合并排序的解释

coder 2023-05-25 原文

我在网上找到了这段代码:

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def mergesort(list):
    if len(list) < 2:
        return list
    middle = len(list) / 2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])
    return merge(left, right)

当我运行它时它可以 100% 工作。我只是不明白合并排序是如何工作的，或者递归函数如何能够正确地对左右排序。

最佳答案

我认为理解归并排序的关键是理解以下原则——我称之为归并原则:

Given two separate lists A and B ordered from least to greatest, construct a list C by repeatedly comparing the least value of A to the least value of B, removing the lesser value, and appending it onto C. When one list is exhausted, append the remaining items in the other list onto C in order. The list C is then also a sorted list.

如果您手动完成几次，您会发现它是正确的。例如:

A = 1, 3
B = 2, 4
C = 
min(min(A), min(B)) = 1

A = 3
B = 2, 4
C = 1
min(min(A), min(B)) = 2

A = 3
B = 4
C = 1, 2
min(min(A), min(B)) = 3

A = 
B = 4
C = 1, 2, 3

现在A已经用完了，所以用B的剩余值扩展C:

C = 1, 2, 3, 4

合并原理也很容易证明。 A的最小值小于A的所有其他值，B的最小值小于B的所有其他值。如果A的最小值小于B的最小值，那么它也必须小于小于 B 的所有值。因此它小于 A 的所有值和 B 的所有值。

因此，只要您继续将满足这些条件的值附加到 C，您就会得到一个排序列表。这就是上面的 merge 函数所做的。

现在，根据这个原则，很容易理解一种排序技术，它通过将列表划分为更小的列表、对这些列表进行排序，然后将这些排序后的列表合并在一起来对列表进行排序。 merge_sort 函数只是一个简单的函数，它将一个列表分成两半，对这两个列表进行排序，然后以上述方式将这两个列表合并在一起。

唯一的问题是，因为它是递归的，所以当它对两个子列表进行排序时，它通过将它们传递给自己来做到这一点!如果您在这里难以理解递归，我建议您先研究更简单的问题。但是，如果您已经掌握了递归的基础知识，那么您所要做的就是意识到单项列表已经排序。合并两个单项列表会生成一个已排序的两项列表；合并两个二项列表生成一个排序的四项列表；等等。

关于python - 傻瓜合并排序的解释，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10502533/

python傻瓜sectionlistcodealgorithmsortingmergesort

有关python - 傻瓜合并排序的解释的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  3. ruby - 有人可以帮助解释类创建的 post_initialize 回调吗 (Sandi Metz) - 2

    我正在阅读SandiMetz的POODR，并且遇到了一个我不太了解的编码原则。这是代码:classBicycleattr_reader:size,:chain,:tire_sizedefinitialize(args={})@size=args[:size]||1@chain=args[:chain]||2@tire_size=args[:tire_size]||3post_initialize(args)endendclassMountainBike此代码将为其各自的属性输出1,2,3,4,5。我不明白的是查找方法。当一辆山地自行车被实例化时，因为它没有自己的initialize方法

  4. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

  5. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  6. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  7. python - 如何读取 MIDI 文件、更改其乐器并将其写回？ - 2

    我想解析一个已经存在的.mid文件，改变它的乐器，例如从“acousticgrandpiano”到“violin”，然后将它保存回去或作为另一个.mid文件。根据我在文档中看到的内容，该乐器通过program_change或patch_change指令进行了更改，但我找不到任何在已经存在的MIDI文件中执行此操作的库.他们似乎都只支持从头开始创建的MIDI文件。 最佳答案 MIDIpackage会为您完成此操作，但具体方法取决于midi文件的原始内容。一个MIDI文件由一个或多个音轨组成，每个音轨是十六个channel中任何一个上的

  8. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

  9. git使用常见问题（提交代码，合并冲突） - 2

    文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g

  10. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

随机推荐