mergesort相关内容

Mergesort Python实现

我见过很多Mergesort Python实现，我编写了以下代码。总体逻辑运行良好，但没有返回正确的结果。我如何修复它？ 编码： def merge(left, right): temp = [] i = 0 j = 0 while i ..
发布时间：2022-08-25 10:23:39 Python

关于合并排序代码中的合并步骤的混淆

我有一个关于数组合并排序如何工作的问题。 我理解‘Divide’步骤，它将一个输入数组分成1个长度的元素。然而，当谈到‘合并’部分(合并步骤)时，我就糊涂了。 例如，给定输入3 5 1 8 2，除法过程将产生5个元素：3，5，1，8，2。我只了解合并函数会将它们组合为3 5，1 8，2，但它如何继续组合3 5和1 8？‘Combine’部分中是否涉及递归？ 推荐答案 当两个递归排序例程 ..
发布时间：2022-08-25 10:03:50 其他开发

就地归并排序实际用法

我试着到处搜索，以找出到底什么是就地合并排序，以及我需要在哪里使用它？但没有找到一个直接的答案。请在下面回答以帮助我。 1)何时何地需要就地合并？就地合并的实际用法。 2)如果未对就地合并的输入数组进行排序，会发生什么情况？ 3)在合并排序、就地合并排序和快速排序中，哪种排序占用的内存更多？ 注意：我问的是关于“std：：inplace_merge”的问题，这是一种stl算法。 ..
发布时间：2022-04-05 17:07:02 C/C++开发

如何使用归并排序算法就地排序?

我知道这个问题不太具体. 我只想有人告诉我如何将普通合并排序转换为就地合并排序(或具有恒定额外空间开销的合并排序). 我只能找到(在网上)说“它太复杂"或“超出本文范围"的页面. 唯一已知的就地合并方法(没有任何额外空间)过于复杂，无法简化为实用程序.(取自从这里) 即使太复杂了，如何就地进行归并排序的基本概念是什么? 解决方案 Knuth 将此作为练习(第 3 卷 ..
发布时间：2022-01-31 08:28:24 其他开发

如何合并排序具有 O(nlogn) 时间和 O(1) 空间复杂度的链表

(免责声明:学校) 据我所知，递归拆分链表，然后将其发送到另一个函数进行合并是 O(nlogn) 时间和 O(n) 空间.是否可以在 O(nlogn) 时间和 O(1) 空间复杂度的链表上进行归并排序?你会怎么做? 感谢任何帮助 PS:为了确保传统归并排序是空间复杂度0(n)，这是0(n)的一个例子，对吧?O(1) 空间将如何更改? void sortTrack() {节点合并 ..
发布时间：2022-01-01 18:24:48 Java开发

链表归并排序的复杂性

我有使用链表进行归并排序的代码，它工作正常，我的问题是这个算法的复杂度是多少?它是 O(nlog(n)) 吗?它是否稳定?我很感兴趣，因为我知道归并排序是稳定的，使用链表怎么样?如果我们有一些彼此相等的元素，这段代码是否保留了元素的顺序?非常感谢 #include#include 结构节点{整数；结构节点*下一个；};struct node *addnode(int number,struct ..
发布时间：2022-01-01 18:23:36 其他开发

使用归并排序对双向链表进行排序

我在互联网上找到了这段代码，它是用于数组的，我想将其更改为双向链表(而不是索引，我们应该使用指针)请您帮助我如何更改合并方法(我有自己改变了排序方法)这也不是我的家庭作业，我喜欢使用链表！！ 公共类 MergeSort {私有双链表 LocalDoublyLinkedList；公共合并排序(DoublyLinkedList 列表){LocalDoublyLinkedList = 列表；}公共无效 ..
发布时间：2022-01-01 18:04:27 Java开发

线程的并行合并排序/比 Seq 慢很多/.合并排序.帮助

http://pastebin.com/YMS4ehRj ^ 这是我对并行归并排序的实现.基本上我所做的是，对于每个拆分，前半部分由一个线程处理，而后半部分是顺序的(即)说我们有一个包含 9 个元素的数组，[0..4] 由线程 1，[0..1] 由线程 2 处理，[5..6] 由线程 3 处理(请查看源代码以进行澄清). 其他一切都保持不变，比如合并.但问题是，这比归并排序慢得多，甚至 ..
发布时间：2021-12-30 21:40:47 其他开发

理解归并排序的递归

我看到的大多数合并排序实现都与此类似.算法介绍书以及我搜索的在线实现.我的递归印章不会比弄乱斐波那契生成(这很简单)更进一步，所以也许是多次递归让我大吃一惊，但我什至无法单步执行代码，甚至在我击中之前就了解发生了什么合并功能. 它是如何逐步完成的?为了更好地理解这里的流程，我应该采取一些策略或阅读方法吗? void mergesort(int *a, int*b, int low, int ..
发布时间：2021-12-27 22:20:25 其他开发

C++中将多个排序序列合并为一个排序序列的算法

我正在寻找一种算法来合并多个排序的序列，假设 X 排序的具有 n 个元素的序列在 C++ 中合并为一个排序的序列，您能提供一些示例吗? 注意:我不想使用任何库 解决方案 有三种方法可以进行合并:- 假设您将 m 个列表与 n 个元素每个 合并 算法 1 :- 合并一次列出两个.使用像合并例程一样的合并排序在列表排序时进行合并.这很容易实现，无需任何库.但是需要时间 O ..
发布时间：2021-12-27 22:06:41 C/C++开发

归并排序中的比较次数

我在研究合并排序主题时遇到了这个概念，即合并排序中的比较次数(在最坏的情况下，根据 维基百科) 等于 (n ⌈lg n⌉ - 2⌈lg n⌉ + 1);事实上，它介于 (n lg n - n + 1) 和 (n lg n + n + O(lg n)) 之间.问题是我无法弄清楚这些复杂性试图说什么.我知道 O(nlogn) 是归并排序的复杂度，但比较次数? 解决方案 为什么要计算比较 ..
发布时间：2021-12-27 22:05:39 其他开发

'MergeSort 算法' - JAVA 中更好的实现是什么?

我知道快速排序算法，但我只关心归并排序算法. 我在互联网上发现了两种类型的归并排序算法实现.但是当我将它们与插入算法进行比较时，它们似乎效率较低，而且对于大量项目来说这不是预期的. 输入要排序的元素数:300000执行冒泡排序所花费的时间:362123 毫秒执行选择所花费的时间:108285 毫秒执行插入所花费的时间:18046 毫秒执行 MergeSort 花费的时间:35968 毫秒执 ..
发布时间：2021-12-20 16:04:21 Java开发

使用 Python 进行归并排序

我找不到任何可用的 Python 3.3 归并排序算法代码，所以我自己做了一个.有什么办法可以加快速度吗?它在大约 0.3-0.5 秒内对 20,000 个数字进行排序 def msort(x):结果 = []如果 len(x) 0) 或 (len(z) > 0):如果 len(y) >0 和 len(z) >0:如果y[0]＞z[0]:结果.追加(z [0])z.pop(0)别的:结果.附加 ..
发布时间：2021-12-10 10:57:04 Python

`std::list<>::sort()` - 为什么突然切换到自上而下的策略?

我记得从一开始，实现 std::list::sort() 的最流行方法是在 自下而上的时尚(另见是什么让 gcc std::list 排序实现如此之快?). 我记得有人恰当地将这种策略称为“洋葱链"方法. 至少在 GCC 的 C++ 标准库实现中是这样的(例如，请参见 此处).这就是 MSVC 标准库版本中旧 Dimkumware 的 STL 以及 MSVC 一直到 VS2013 ..
发布时间：2021-12-10 10:37:38 C/C++开发

为什么 Java 的 Arrays.sort 方法对不同的类型使用两种不同的排序算法?

Java 6 的 Arrays.sort 方法对原始数组使用快速排序，对对象数组使用归并排序.我相信大多数情况下 Quicksort 比合并排序更快，而且消耗的内存更少.我的实验支持这一点，尽管两种算法都是 O(n log(n)).那么为什么不同的算法用于不同的类型? 解决方案 最可能的原因:快速排序不是稳定，即相等的条目可以在排序过程中改变它们的相对位置；除此之外，这意味着如果你对一个已 ..
发布时间：2021-12-06 20:14:01 Java开发

对链表进行合并排序

我最近复习了一些基础知识，发现对链表进行合并排序是一个很好的挑战.如果你有一个很好的实现，那么在这里展示它. 解决方案 想知道为什么这里所说的它应该是一个巨大的挑战，这里是一个简单的 Java 实现，没有任何“聪明的技巧". //主要功能公共静态节点merge_sort(节点头){if(head == null || head.next == null)回头；节点中间 = getMidd ..
发布时间：2021-12-06 19:40:10 其他开发

为什么快速排序比归并排序好?

我在一次采访中被问到这个问题.它们都是 O(nlogn)，但大多数人使用 Quicksort 而不是 Mergesort.这是为什么? 解决方案 Quicksort 有 O(n2) 最坏情况运行时和 O(nlogn) 平均情况下运行时间.然而，它在很多场景下都优于归并排序，因为影响算法运行时间的因素有很多，如果把它们放在一起，快速排序就会胜出. 特别是，经常引用的排序算法的运行时间是 ..
发布时间：2021-12-06 19:34:26 其他开发