使用链表合并排序
链表合并排序是一种常见的排序算法，用于将两个有序链表合并为一个有序链表。它的基本思想是通过比较两个链表的节点值，逐个选择较小的节点，构建一个新的有序链表。
链表合并排序的步骤如下：
- 创建一个新的链表作为结果链表的头节点。
- 比较两个链表的头节点值，选择较小的节点作为结果链表的下一个节点，并将指针移动到下一个节点。
- 重复步骤2，直到其中一个链表为空。
- 将另一个非空链表的剩余部分直接连接到结果链表的末尾。
- 返回结果链表的头节点。
链表合并排序的时间复杂度为O(nlogn)，其中n是链表的总节点数。它是一种稳定的排序算法，适用于链表这种数据结构。
在腾讯云的产品中，可以使用云数据库TDSQL来存储链表的节点值，并使用云函数SCF来实现链表合并排序的逻辑。具体的产品介绍和使用方法可以参考以下链接：
需要注意的是，以上只是一种示例，实际上链表合并排序的实现并不依赖于特定的云计算产品，可以使用任何编程语言和开发环境来实现。
相关·内容
4回答
用C++对链表排序
、、、、
我被要求编写一个函数，它接受3个未排序的链表，并返回一个组合了所有这三个列表的排序链表。你能想到的最好的方法是什么？
我实际上没有内存限制，但是如果有/没有内存限制，你会怎么做？
浏览 4提问于2011-08-24得票数 6
1回答
一种分段链表重组算法
、、、、
这里的答案有一些基本的统计数据，表明打包的链表将使用合并排序执行相当快的排序：
我想知道是否有任何技术(类似于垃圾收集之类的后台工作)可以在运行时以最佳方式重新组织链表，使其更加紧凑。
浏览 19提问于2018-07-25得票数 1
回答已采纳
我在一个论坛上读到了以下内容：
合并排序对于像链表这样的不可变数据结构是非常有效的
和
当数据存储在内存中时，快速排序通常比合并排序快。然而，当数据集很大并且存储在硬盘驱动器等外部设备上时，合并排序在速度方面显然是赢家。它最大限度地减少了对外部驱动器的昂贵读取
和
在链表上操作时，合并排序只需要少量恒定的辅助存储空间
有没有人能帮我理解上面的论点？为什么合并排序是对大型链表进行排序的首选？它如何最大限度地减少对外部驱动器的昂贵读取？基本上，我想知道为什么会选择合并排序来对一个大的链表进行排序。
浏览 55提问于2011-03-08得票数 60
回答已采纳
2回答
我知道如何计算每种算法的bigO，以及它是如何工作的。例如，在链表中查找特定数字将是O(N)，因为您可能需要从头到尾检查链表中的每个输入。然而，关于时间，bigO到底意味着什么呢？为什么合并排序可以比插入排序运行得更快，尽管插入排序具有更快的“时间复杂度”？请给我你的意见，以便我能理解。非常喜欢THankyou。
浏览 2提问于2015-04-01得票数 0
2回答
方法对链表进行排序。
、、、
好的，我有一个问题，我所有的信息都被作为对象发送到链表，这就是我想要的。链表是从另一个类初始化的，这个类包含LinkedLists的所有方法。是否有一种方法可以根据数字对链表中的对象进行排序？因为每个元素看起来都像这样("800110，简，嘿，你在那里吗“)。在进入之前，它们被设置为int、string、string：
//if the command is to RecieveMessage
SinglyLinkedList <String> Jane= new SinglyLinkedList <String>();
浏览 1提问于2017-09-06得票数 0
2回答
我必须在链表上实现自然合并(这很容易)，但我不能改变节点的"next“属性，只能交换它们的值。我也不能倒退，因为节点没有"prev“属性。(链表没有随机访问)，并且我不能创建新节点。 我只需要一些关于合并功能应该是什么的提示。 我知道在合并之前保持两个子列表的顺序是关键，但我找不到这样做的方法。 这是Node类。它们保存一个泛型项和下一个节点的地址 private class Node {
Item item;
Node next;
public String toString() {
if (next == null) return
浏览 9提问于2019-05-09得票数 0
2回答
快速排序算法可分为以下步骤
1)确定枢轴。
2)基于枢轴的链表划分。
3)递归地将链表划分为两部分。
现在，如果我总是选择最后一个元素作为枢轴，那么识别pivot元素(第一步)需要O(n)时间。
在识别了pivot元素之后，我们可以存储它的数据并将其与所有其他元素进行比较，以确定正确的分区点(第二步)。当我们存储枢轴数据时，每个比较将花费O(1)时间，而每个交换则需要O(1)时间。因此，总的来说，n个元素需要O(n)时间。
所以递推关系是
T(n) = 2T(n/2) +n，为O(nlogn)，与链表合并排序相同。
那么，为什么对于链接列表来说，合并排序比快速排序更可取？
浏览 5提问于2017-11-30得票数 1
回答已采纳
1回答
我正在尝试计算链表上的mergesort与指针数组的时间效率(不担心将来如何使用它，只关心数据排序的速度)。
这样会更快。我想使用指针数组需要额外的内存访问层。但同时，假设我们已经知道链表的长度，那么访问链表会更慢，mergesort仍然需要迭代链表，从内存跳到内存，直到你得到一个指向链表中间节点的指针，我认为这比数组的时间更长。
有谁有什么见解吗？对于排序的数据，它是否更具上下文意义？
浏览 0提问于2018-11-02得票数 0
我有一个链表实现，我正在试验Mergesort和QuickSort算法。
我不明白的是为什么std::list中的排序操作这么快。查看linux下的std::list，它似乎也是一个链表，而不是一个基于数组的列表。
我尝试的合并排序几乎与Dave Gamble的版本相同：
此外，我认为我应该尝试基于以下代码的简单快速排序：
令人惊讶的是，使用std::list和sort对1000万个随机数进行排序的速度大约是其他两种方法的10倍。
对于那些正在询问的人，是的，我需要为这个项目使用我自己的list类。
浏览 0提问于2011-07-18得票数 10
回答已采纳
3回答
我需要实现最快的排序算法来对使用stdin创建的链表进行排序。
我知道合并排序的时间复杂度是O(n logn)，插入排序的时间复杂度是O(n^2) (n是链表中元素的数量)。
但是列表是由标准输入创建的，那么对未排序的列表使用merge-sort更有效，还是通过插入-排序创建列表更有效，这意味着对输入的列表进行排序？
结构是这样的：
#define SIZE 50
struct node {
int num;
char name[SIZE];
struct node* next;
};
以下是排序标准：
1. Sorted alphabetically by "na
浏览 0提问于2019-09-10得票数 2
我已经通过以下链接
它们使用另一个数组(*arr)进行排序。
有没有可能在不使用任何其他数组或链表的情况下对链表进行插入排序？
浏览 1提问于2014-05-22得票数 0
2回答
如果以前已经回答过这个问题，请给我指出正确的方向！
所以，我一直在闲逛，所以在阅读有关排序的文章时，我已经有好几次了。然而，我想知道，选择一个好的单链表排序算法与双链表排序算法(以及与数组结构相比也是链接结构)之间的主要区别是什么？
我知道(假设我们使用的是面向对象语言)，类型关系到要排序的元素，等等(原始类型通常比复杂对象更快)。我在比较Java字符串和整数。
据我所知，在处理链接结构时，我们可能应该排除快速排序和插入排序，因为它们经常处理索引问题。
这个问题可能很糟糕，但正如我所提到的，请告诉我另一个来源，在那里我可以阅读有关选择正确算法的内容(而不是如何实现一个算法)。
浏览 0提问于2018-02-15得票数 1
回答已采纳
2回答
合并排序:修订
、、
合并排序的依据是什么？
获取一列值
把它一分为二
取每个列表的第一个元素，最低值的元素进入一个新的列表(我猜是从原始列表中删除的)。comare接下来的两个数字-这样做，直到一个列表为空，然后将另一个列表的其余部分放在nw列表的末尾？
此外，在链表上执行此操作的后果是什么？
谢谢
浏览 1提问于2010-04-19得票数 0
2回答
大家好，我正在做一个项目，根据给定的标准(姓名、年龄、性别或家乡)对具有大量记录的文件进行排序，并以原始文件的格式写入输出文件。然而，我正在讨论什么是最快的方法。该文件包含如下记录：
Name Age gender hometown
Adam 28 Male New york
Kevin 42 Male Boston
...
我的想法是读取文件并创建struct的链表：
struct record
{
char * SortCriteriaString;
int SortCriteriaInt;
char * Name;
int Age;
char * Gender;
char
浏览 1提问于2017-11-16得票数 0
3回答
c++向量排序
、、、
这是一个关于使用STL std::sort函数进行排序背后的机制的一般性问题。我读过一些关于排序的文章，一般来说，排序向量比排序链表更快。对于结构/对象的向量和链表是否如此？对于结构的链表，我觉得只需修改索引就可以很容易地实现排序。另一方面，对向量进行排序似乎涉及到物理上交换结构/对象的数据的数据位置，因为它们是连续的(这是真的吗？)。在这种情况下，对链表进行排序似乎会更快。
编辑！：现在带图片：
所以我想问题的表达方式更好:排序对象、链表和向量哪个更快(尽管这可能取决于对象的大小)？另外，链表的排序是否如3)所示，向量的排序是否如2)所示？
浏览 1提问于2012-09-15得票数 3
回答已采纳
1回答
我已经完成了用C实现线性链表的操作，
为了测试我的能力，我需要解决一些基于线性链表的问题，你们可以通过建议一些问题/任务来帮助我。我认为向我的社区成员寻求这种帮助是没有错的。
浏览 1提问于2010-08-13得票数 0
回答已采纳
1回答
如果我们使用单链表或双链表，排序的时间是一样的吗？
我想对随机数进行排序。
(我知道在单链表/双链表中插入/删除元素有很大的不同)
但是，无论我们使用哪种数据结构(Singly / Doubly )或实现哪种排序技术来对数字进行排序，都需要几乎相同的时间吗？
浏览 2提问于2015-11-20得票数 0
3回答
对链表进行堆排序
、、、
我试图在c++中创建一个排序函数，它使用堆排序对链表对象进行排序，但我不确定如何开始。有人能告诉我怎么做吗？我甚至不确定如何对链表进行排序
浏览 0提问于2011-11-11得票数 0
2回答
按词法对字符串的链表进行排序
、、、、
给定一个由单个空格分隔的字符串，我需要将该字符串中的每个单词传输到一个链表中的Node，并保持该列表按词法排序(就像在字典中一样)。
我做的第一步是遍历字符串，并将每个单词放在一个单独的Node中。现在，我很难对列表进行排序--它必须以最有效的方式完成。
合并-排序为nlogn。合并排序将是最好的选择吗？
浏览 1提问于2015-06-21得票数 1
我正在编写一个需要使用数组或链表存储数据的项目。稍后，必须对数据进行排序。我觉得编码数组更容易排序，因为我们只是简单地交换。对于链表，我们不得不担心(和代码)指针，而且访问每个元素比访问数组的开销更大。我说的对吗？
浏览 3提问于2013-05-09得票数 4
回答已采纳
1回答
我想用java.util库不包含的函数实现一个单链表，比如:返回链表中的中间节点，并在链表中插入一个新的头。我的问题是: java.util链表是什么类型的链表(例如，单次、双次)？其次，我想知道您是否建议我从头开始实现链表。我关心的是能够在没有第三方库的情况下维护我自己的代码(因为依赖)，并且能够对其进行自定义。我还想实现合并排序，我觉得有一个中间节点方法很重要。谢谢！！
浏览 11提问于2020-11-18得票数 0
我想知道是否有人可以向我解释这两个算法的空间复杂性是如何工作的。我已经读过了，但如果我理解正确的话，它们似乎是矛盾的。
例如，我对链表将如何影响空间复杂性感兴趣，这个问题说它使其更快？；
然而，这个问题说这无关紧要；
现在我对编程有点新手，我想更好地理解这个理论，这样哑巴语言就会很受欢迎。
浏览 4提问于2018-03-17得票数 1
最好的排序算法，可以使用c中的结构对链表进行排序，哪种算法获得错误的可能性最小(例如分段)？
浏览 29提问于2018-05-13得票数 -2
回答已采纳
2回答
我在一个名为WordNode的类中有一个链表，它包含以下属性：
String _word; WordNode _next;
我还有一个“实际列表”类，它只包含对列表头部的引用，这个类被称为TextList，它接收一个String，并将String中的每个单词排序到列表中。例如，对于句子：
coding in Java is cool.
链表将如下所示：
coding >>> cool >>> Java >>> in >>> is.
箭头就像指向列表中下一个节点的指针。
我想首先获取所有单词并将它们放入链表(TextList
浏览 2提问于2013-06-08得票数 1
6回答
我有一个这样的数组：
1,2,3,5,6,4它是99%排序的，有40K个元素。
我可以把它们放在一个数组，列表，链表，...
但是我不知道最快的排序方法！
浏览 0提问于2009-12-10得票数 4
回答已采纳
我目前正在尝试制定一个用于单链表的mergeSort机制。通过研究和找到关于A)合并排序是对单链表进行排序的最佳方式，以及B)这些是执行此类操作的关键组件的一致想法，我得出了以下代码。它几乎完全按照预期工作，但只返回所有大于上一个输入数字的整数。例如，输入7，6，5，4，3，2，1将返回1，2，3，4，5，6，7，但输入1，2，3，4，5将只返回5。我使用了随机输入顺序，所以这不是一个仅以逆序输入数字的问题，而是字面上的任何顺序。如果数字小于最终数字，则在排序过程中将其从列表中删除。我根本找不到原因。我最初的问题是由一个错误的while循环引起的，该循环在一次go之后停止迭代，所以一旦我删除了
浏览 6提问于2020-03-06得票数 1
回答已采纳
1回答
我一直在尝试理解这个leetcode问题的递归顺序，我也找到了一个解决方案。我理解merge函数，但我不理解mergeKLists函数上的递归。如果能帮上忙，我们将不胜感激。请尽可能描述性地向我展示导致最终合并链表的调用和返回。*我理解合并函数，所以不需要解释它。 def mergeKLists(self, lists):
if not lists:
return
if len(lists) == 1:
return lists[0]
mid = len(lists)//2
l = self.mergeKLists(lists
浏览 12提问于2019-12-27得票数 0
回答已采纳
3回答
为什么Java impl选择合并排序而不是快速排序？为什么他们要将内容复制到数组中？
接口：“排序算法是一种改进的合并排序算法(如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并)。该算法提供了有保证的n log(n)性能。该实现将指定的列表转储到一个数组中，对该数组进行排序，并遍历该列表，从该数组中的相应位置重新设置每个元素。这避免了尝试对链表进行原地排序所导致的n2 log(n)性能。”
浏览 2提问于2010-08-01得票数 3
回答已采纳
2回答
我在一个航空电子操作系统(线程层)上工作，我正在寻找关于以下(简化)要求的最佳解决方案：“等待各种对象的线程按优先级顺序排队。对于相同的优先级，线程也按FIFO顺序排队”。
例如，各种对象都是信号量。
我认为我可以使用经典的链表来构建这样的等待列表，这使得插入/排序相对快速和容易，并且完全符合预期的使用(一次一个线程进入等待状态)。但是我在一个裸机目标上工作，并且我没有任何libc支持，因此我没有malloc (这对于链表非常有用！)
为了按照优先级对线程进行排序，我通常使用二进制堆()，它非常高效，但在这里不能使用它，因为“先进先出顺序”不能以这种方式管理。
当然，我可以使用更经典的排序算法
浏览 0提问于2014-06-24得票数 0
2回答
我在geeksforgeeks.org上的C++中找到了这个递归函数，用来合并和排序两个单链表，我使用netbeans调试了这段代码，但我仍然不能清楚地了解这段代码背后的功能。此外，我也看到过类似的代码堆栈溢出，但没有解释它的工作方式。我的问题是关于它背后的想法和它的工作方式，这里充分的解释也会帮助其他人解决同样的问题。
已在netbeans上调试代码以了解代码的工作流
//Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node *mer
浏览 0提问于2019-01-02得票数 0
2回答
排序k个有序链表？
、、、、
我正在阅读这里的解决方案：https://leetcode.com/problems/merge-k-sorted-lists/solution/关于如何将k个排序的链表合并为一个链表。 一个简单的解决方案是编写一个函数来完成两个链表的工作，在前两个链表上调用它，然后用前一个结果和第三个链表再次调用它，然后用前一个结果和第四个链表再次调用它，依此类推。 另一个更高效解决方案是执行以下操作： 结对k列出并合并每一对。 在第一次配对之后，k列表合并到k/2带有平均值的列表2N/k长度，然后k/4, k/8以此类推。 重复这个过程，直到我们得到最终的排序链表。 我的问题是： 为什么第二个更有效率，
浏览 31提问于2021-02-26得票数 3
回答已采纳
1回答
是的，我正在选修计算机系统课程。关于实现malloc的各种分配方案，我有几个问题。对于显式列表，如果我使用类似于LIFO的堆栈实现malloc，那么让指针指向以前释放的内存的目的到底是什么？比如，为什么你需要双向链表？单链表不是也能正常工作吗？
我在网上找到了这个链接，你可以看看幻灯片7，看看我在说什么。
在查看隔离列表分配方案时，这些列表是单向的，对吗？另外，合并机制到底是什么？例如，如果释放了4个单词，您是否会先尝试在您周围的空闲空间中加入它，然后再将其插入到相应的隔离链表中？或者，您会简单地将4字块插入相应分离链表的“4字”部分吗？
谢谢。
浏览 2提问于2012-04-04得票数 5
回答已采纳
我有一个未排序的链表。我需要按某个字段对其进行排序，然后将链表返回到以前未排序的状态。我怎么才能在不复制列表的情况下做到这一点？
浏览 0提问于2010-08-24得票数 0
回答已采纳
2回答
我一直在查看合并排序在链接列表中的应用。我看过的一些文章指出，合并排序是排序链接列表的最佳算法。分而治之策略中的征服部分是有意义的，当您最终节省所需内存(与数组相比)时，合并两个排序链接列表是有意义的。但是，我不明白的是算法中分步的时间复杂度。
对于数组来说，通过利用随机访问和将数组分割成更小的块，这个步骤是恒定的时间。但是，对于一个链表，这不是需要额外的O(n)吗？我见过弗洛伊德的算法(龟兔)用来找到链接列表的中点，并将问题分成更小的块。我对分步做了一些分析。假设链表的大小为n，那么只分解问题所涉及的#操作如下，
n/2 + n/4 * 2 + n/8 * 4 + ... = n/2 * l
浏览 3提问于2021-05-20得票数 1
回答已采纳
这个C++赋值要求我们创建一个二叉树，并检查它是否是一个二叉树。如果不是，那么我们需要一个算法来修复它，而不使用额外的空间或其他数据结构。我和我的朋友都被困在找出一个合适的算法上，因为大量的在线搜索几乎没有得到任何结果。我们不太关心运行时，我们主要专注于找出如何根据给定的需求来修复BT。
链表被用来创建树，但我们在如何实现某种算法将其转换为BST上遇到了困难。
任何建议都将不胜感激！
浏览 0提问于2015-12-10得票数 1
5回答
单链表的并行排序
、、、、
是否有任何算法使其值得对链接列表进行并行排序？
众所周知，是对进行排序的最佳算法。
大多数合并排序都用数组来解释，每一半递归排序。这将使并行化变得非常简单:分别对每一半进行排序，然后合并这两部分。
但链接列表没有“中途”点；链接列表直到结束为止：
→a→b→c→d→e→f→g→h→i→j→.
我现在已经实现了一次遍历列表以获得计数，然后递归地拆分计数，直到我们比较节点和它的NextNode为止。递归负责记住这两部分的位置。
这意味着链表的MergeSort在列表中线性地进行。由于它似乎要求通过一个列表进行线性级数，所以我认为它不能并行化。我唯一能想象的方法是：
遍历列表以获得计数O
浏览 10提问于2013-11-02得票数 6
回答已采纳
2回答
我正在学习数据结构和排序算法，我有一些问题想问：
当我们选择数组和为排序算法选择链表时
对于小数据我们应该使用什么排序算法，对于大数据我们应该使用什么排序算法？我知道这要视情况而定，我们应该选择可用的算法，但我不明白具体情况。
浏览 2提问于2014-04-22得票数 2
5回答
如何对单个链表进行排序。(这里的问题是，单个属性+使用LinkedList进行排序比使用数组更难)我希望看到伪代码。
尝试让它在时间和空间上都尽可能有效。
谢谢!
浏览 2提问于2010-07-23得票数 9
回答已采纳
1回答
我正在开发一个电话簿应用程序，其中我希望根据客户端的名称对表示每个条目的节点进行排序。我想使用存储桶排序算法，其中我有两个链表结构的数组。
问题是我不想使用删除和构造来在存储桶中移动节点。
有没有更简单的方法，使用指针？在存储桶中移动指针可能要容易得多，但我不知道如何实现它。我是用C语言来做这件事的，但欢迎使用任何其他语言提供帮助。
我很感谢你的帮助。
浏览 3提问于2011-02-11得票数 4
回答已采纳
6回答
我必须制作一个电话号码簿程序。程序应该从文件中读取名称和数字。我已经成功地创建了一个包含此数据的链表。现在我想按字母顺序对它们进行排序。我该怎么做呢？
浏览 0提问于2010-12-06得票数 1
2回答
合并两个链表
、、、、
我有一个任务，我必须在一个函数中以升序组合两个链表，而不是创建一个新的列表。就像这样：<code>D0</code> & <code>D1</code> -> <code>D2</code>。我有完整的代码，但监控程序一直报告相同的内容：<code>D3</code>。
这是我的代码(只有函数部分和<code>D4</code>定义)：
<code>A5</code>
浏览 12提问于2020-11-15得票数 0
回答已采纳
8回答
在一次采访中，我被问到这个问题:两个链表有两个头。在c中有一个合并的链表，其中第二个链表在某一时刻合并到第一个链表中。我们如何确定合并点，以及找到合并点的复杂性是什么？
有人能帮帮忙吗？
浏览 2提问于2009-12-11得票数 0
1回答
我最近一直在使用线程，我只是想要一些建议。我把函数代码放在这里只是为了解决任何歧义。
private void sort() throws FileNotFoundException, InterruptedException{
int i;
int largest = data.get(0) ;
int n = fullsize;//data.getsize
int [ ] tmp = new int [ n ] ;
for ( i = 1; i < n ; i++)
if ( largest < da
浏览 0提问于2013-08-22得票数 0
6回答
大O符号数组与链表插入：
根据学术文献，对于数组，它是常数O(1)，对于链表，它是线性O(n)。
一个数组只需要一次乘法和加法。
未在连续内存中布局的链表需要遍历。
这个问题是，O(1)和O(n)是否分别准确地描述了数组和链表的索引/搜索成本？
浏览 1提问于2011-10-15得票数 24
回答已采纳
我编程已经有一段时间了，而我与其他编程相比所缺少的是算法。我知道什么是链表和二叉树，但我不知道更多。
我在两次面试中失败了，因为练习要求我了解一些数据结构算法。我也开始构建一个javascript项目，它有一些很大的处理量，我需要知道一些常用的好算法？
浏览 0提问于2013-07-16得票数 4
回答已采纳
1回答
实现链表的快速排序？
、、、
我需要使用除插入排序之外的任何方法对双向链表进行排序，它的运行时间也比O(n^2)更快。我正在考虑使用快速排序，但在理解算法方面遇到了问题。你能告诉我任何简单易懂的文档可以帮助我入门吗？
浏览 6提问于2012-03-27得票数 1
3回答
昨晚我问了一个关于如何在C++中sort()一个双向链表的问题。我设法让它工作，但现在我想合并两个列表，但我不能让它工作。我没有太多的代码，对不起。我试过的每一件事都毫无意义。我只是希望有人能给我一些提示，告诉我从哪里开始，或者如何做，以及我将提供的信息。
这是我在开始的时候所做的：
void next() { if (curr != tail) curr = curr->next; }
我想我只需要这些。
我在网上看了一些例子，但对我来说没有任何意义。它看起来和我现在所拥有的非常不同。显然，这应该比执行排序函数容易得多，我几乎没有遇到任何问题。
任何解释/提示都将不胜感激！我再一次为代
浏览 0提问于2012-10-26得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
