我最近在复习一些基础知识，发现将链表进行归并排序是一个相当不错的挑战。如果您有良好的实现，请在这里展示出来。
合并排序链表
56
- Andrew Peters
2
https://dev59.com/eHI_5IYBdhLWcg3wBuX3#46319131 - Angus Johnson
在此解决方案中交叉发布递归实现-https://dev59.com/uLX3oIgBc1ULPQZFuF3q - snehil suresh wakchaure
20个回答
89
不明白为什么这应该是一个巨大的挑战，这里有一个直接的Java实现，没有任何“聪明的技巧”。
//The main function
public static Node merge_sort(Node head)
{
if(head == null || head.next == null)
return head;
Node middle = getMiddle(head); //get the middle of the list
Node left_head = head;
Node right_head = middle.next;
middle.next = null; //split the list into two halfs
return merge(merge_sort(left_head), merge_sort(right_head)); //recurse on that
}
//Merge subroutine to merge two sorted lists
public static Node merge(Node a, Node b)
{
Node dummyHead = new Node();
for(Node current = dummyHead; a != null && b != null; current = current.next;)
{
if(a.data <= b.data)
{
current.next = a;
a = a.next;
}
else
{
current.next = b;
b = b.next;
}
}
dummyHead.next = (a == null) ? b : a;
return dummyHead.next;
}
//Finding the middle element of the list for splitting
public static Node getMiddle(Node head)
{
if(head == null)
return head;
Node slow = head, fast = head;
while(fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
- jayadev
1
20
一种更简单/更清晰的实现可能是递归实现，从中可以更清楚地看出NLog(N)的执行时间。
typedef struct _aList {
struct _aList* next;
struct _aList* prev; // Optional.
// some data
} aList;
aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two))
{
// Trivial case.
if (!list || !list->next)
return list;
aList *right = list,
*temp = list,
*last = list,
*result = 0,
*next = 0,
*tail = 0;
// Find halfway through the list (by running two pointers, one at twice the speed of the other).
while (temp && temp->next)
{
last = right;
right = right->next;
temp = temp->next->next;
}
// Break the list in two. (prev pointers are broken here, but we fix later)
last->next = 0;
// Recurse on the two smaller lists:
list = merge_sort_list_recursive(list, compare);
right = merge_sort_list_recursive(right, compare);
// Merge:
while (list || right)
{
// Take from empty lists, or compare:
if (!right) {
next = list;
list = list->next;
} else if (!list) {
next = right;
right = right->next;
} else if (compare(list, right) < 0) {
next = list;
list = list->next;
} else {
next = right;
right = right->next;
}
if (!result) {
result=next;
} else {
tail->next=next;
}
next->prev = tail; // Optional.
tail = next;
}
return result;
}
注意：这个递归算法需要Log(N)的存储空间。性能方面应该与我之前发布的另一种策略大致相当。可以通过在(list && right)运行合并循环并简单地附加剩余列表（因为我们不关心列表的结尾；知道它们已经合并就足够了）来进行潜在的优化。
- Dave Gamble
10
本文内容大部分基于这篇优秀代码：http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
稍作修改和整理：
typedef struct _aList {
struct _aList* next;
struct _aList* prev; // Optional.
// some data
} aList;
aList *merge_sort_list(aList *list,int (*compare)(aList *one,aList *two))
{
int listSize=1,numMerges,leftSize,rightSize;
aList *tail,*left,*right,*next;
if (!list || !list->next) return list; // Trivial case
do { // For each power of two<=list length
numMerges=0,left=list;tail=list=0; // Start at the start
while (left) { // Do this list_len/listSize times:
numMerges++,right=left,leftSize=0,rightSize=listSize;
// Cut list into two halves (but don't overrun)
while (right && leftSize<listSize) leftSize++,right=right->next;
// Run through the lists appending onto what we have so far.
while (leftSize>0 || (rightSize>0 && right)) {
// Left empty, take right OR Right empty, take left, OR compare.
if (!leftSize) {next=right;right=right->next;rightSize--;}
else if (!rightSize || !right) {next=left;left=left->next;leftSize--;}
else if (compare(left,right)<0) {next=left;left=left->next;leftSize--;}
else {next=right;right=right->next;rightSize--;}
// Update pointers to keep track of where we are:
if (tail) tail->next=next; else list=next;
// Sort prev pointer
next->prev=tail; // Optional.
tail=next;
}
// Right is now AFTER the list we just sorted, so start the next sort there.
left=right;
}
// Terminate the list, double the list-sort size.
tail->next=0,listSize<<=1;
} while (numMerges>1); // If we only did one merge, then we just sorted the whole list.
return list;
}
注意：这是O(NLog(N))的保证，并且使用O(1)的资源（没有递归，没有堆栈，没有其他东西）。
- Dave Gamble
2
我想试试在我的链表上运行这段代码。但出现了一个问题，它比递归版本在一个包含1000万项的int列表上运行得更慢。递归版本大约需要6-7秒，而这个版本则需要大约10秒？ - hookenz
2没有什么意外。递归方法使用额外的存储来加速处理。 - Dave Gamble
6
一种有趣的方法是维护一个栈，只有当栈顶上的列表有相同数量的元素时才合并，否则将列表压入栈中，直到传入的列表中没有元素为止，然后向上合并整个栈。
- John with waffle
3
最简单的算法来自Gonnet + Baeza Yates算法手册。你调用它时传入你想要排序的元素数量，然后递归地将其二分，直到达到对一个大小为一的列表的请求，然后你可以将原始列表的前面元素去掉。所有这些元素都被合并成一个完整的排序列表。
（请注意，第一个帖子中的基于堆栈的酷炫算法称为在线归并排序，它在Knuth第3卷的一个练习中只有极小的提及。）
- paperhorse
2
我一直在努力优化这个算法的混乱问题，最终得出了以下结果。互联网和StackOverflow上的许多其他代码都非常糟糕。有些人试图获取列表的中间点，进行递归，对剩余节点使用多个循环，维护大量计数 - 所有这些都是不必要的。归并排序自然适用于链表，算法可以变得美观而紧凑，但要达到这种状态并不容易。
以下代码保持了最少量的变量，并且在算法所需的逻辑步骤（即不会使代码难以维护/难以阅读）方面具有最少的数量。然而，我没有尝试将代码最小化，并保留了尽可能多的空格以保持可读性。我已经通过相当严格的单元测试测试了这段代码。
请注意，此答案结合了其他答案https://dev59.com/33VD5IYBdhLWcg3wWaNh#3032462的几种技术。虽然代码是用C#编写的，但转换为C++、Java等应该很简单。
以下代码保持了最少量的变量，并且在算法所需的逻辑步骤（即不会使代码难以维护/难以阅读）方面具有最少的数量。然而，我没有尝试将代码最小化，并保留了尽可能多的空格以保持可读性。我已经通过相当严格的单元测试测试了这段代码。
请注意，此答案结合了其他答案https://dev59.com/33VD5IYBdhLWcg3wWaNh#3032462的几种技术。虽然代码是用C#编写的，但转换为C++、Java等应该很简单。
SingleListNode<T> SortLinkedList<T>(SingleListNode<T> head) where T : IComparable<T>
{
int blockSize = 1, blockCount;
do
{
//Maintain two lists pointing to two blocks, left and right
SingleListNode<T> left = head, right = head, tail = null;
head = null; //Start a new list
blockCount = 0;
//Walk through entire list in blocks of size blockCount
while (left != null)
{
blockCount++;
//Advance right to start of next block, measure size of left list while doing so
int leftSize = 0, rightSize = blockSize;
for (;leftSize < blockSize && right != null; ++leftSize)
right = right.Next;
//Merge two list until their individual ends
bool leftEmpty = leftSize == 0, rightEmpty = rightSize == 0 || right == null;
while (!leftEmpty || !rightEmpty)
{
SingleListNode<T> smaller;
//Using <= instead of < gives us sort stability
if (rightEmpty || (!leftEmpty && left.Value.CompareTo(right.Value) <= 0))
{
smaller = left; left = left.Next; --leftSize;
leftEmpty = leftSize == 0;
}
else
{
smaller = right; right = right.Next; --rightSize;
rightEmpty = rightSize == 0 || right == null;
}
//Update new list
if (tail != null)
tail.Next = smaller;
else
head = smaller;
tail = smaller;
}
//right now points to next block for left
left = right;
}
//terminate new list, take care of case when input list is null
if (tail != null)
tail.Next = null;
//Lg n iterations
blockSize <<= 1;
} while (blockCount > 1);
return head;
}
注意事项
- 对于空列表、列表中只有一个元素等情况，不需要特殊处理。这些情况都可以正常工作。
- 许多“标准”算法文本都需要两个循环来处理一个列表比另一个列表短的情况。上面的代码消除了这种需要。
- 我们确保排序是稳定的。
- 内部的 while 循环是一个热点，平均每次迭代会计算 3 个表达式，我认为这是最少可以做到的。
更新：@ideasman42已经将上述代码翻译成了C/C++，并提出了修复注释和更多改进的建议。上面的代码现在已经更新。
- Shital Shah
5
这太棒了！我将其转换为Delphi，它非常好用。谢谢您，先生！ - Marus Gradinaru
这些注释似乎没有更新以匹配代码。它们引用了代码中不存在的变量
p q & k，我认为应该分别是 left right & block_size。 - ideasman42改进了这个答案的版本：https://gist.github.com/ideasman42/5921b0edfc6aa41a9ce0 1）使用尾部指针（去掉2个条件检查，减少代码大小）。2）避免重新分配大小不变的空值。3）更正注释。 - ideasman42
感谢@ideaman42。我已经在上面的代码中添加了一个改进。对于tail_p，没有直接的C#等效项，所以它保持不变:(。 - Shital Shah
虽然这个效果相当不错，但在我的测试中，Mono的eglib版本表现略微更快(经过优化的C)，大约快10-20％，请参见：https://dev59.com/33VD5IYBdhLWcg3wWaNh#18246901 - ideasman42
2
这里是另一种递归版本。它不需要遍历列表来分割它：我们提供一个指向头部元素的指针（它不是排序的一部分）和一个长度，递归函数会返回已排序列表的末尾指针。
element* mergesort(element *head,long lengtho)
{
long count1=(lengtho/2), count2=(lengtho-count1);
element *next1,*next2,*tail1,*tail2,*tail;
if (lengtho<=1) return head->next; /* Trivial case. */
tail1 = mergesort(head,count1);
tail2 = mergesort(tail1,count2);
tail=head;
next1 = head->next;
next2 = tail1->next;
tail1->next = tail2->next; /* in case this ends up as the tail */
while (1) {
if(cmp(next1,next2)<=0) {
tail->next=next1; tail=next1;
if(--count1==0) { tail->next=next2; return tail2; }
next1=next1->next;
} else {
tail->next=next2; tail=next2;
if(--count2==0) { tail->next=next1; return tail1; }
next2=next2->next;
}
}
}
- Ed Wynn
1
2
我决定测试这里的示例，以及Jonathan Cunningham在Pop-11中最初编写的一种方法。我将所有方法都编写成了C#代码，并与各种不同大小的列表进行了比较。我比较了Raja R Harinath的Mono eglib方法、Shital Shah的C#代码、Jayadev的Java方法、David Gamble的递归和非递归版本、Ed Wynn的第一份C代码（这在我的样本数据集上崩溃了，我没有进行调试）以及Cunningham的版本。完整代码在此处：https://gist.github.com/314e572808f29adb0e41.git。
Mono eglib基于与Cunningham相似的思路，并且速度相当快，除非列表已经排序，否则Cunningham的方法要快得多（如果部分排序，eglib略快）。eglib代码使用固定表来保存归并排序递归，而Cunningham的方法通过使用递归的不断增加级别来工作——因此它从不使用递归开始，然后是1级递归，然后是2级递归等等，根据需要做排序的步骤数。我发现Cunningham的代码更容易理解，而且不需要猜测递归表应该有多大，所以我更喜欢它。我从这个页面尝试的其他方法要慢两倍或更多。
这是Pop-11排序的C#移植版本：
Mono eglib基于与Cunningham相似的思路，并且速度相当快，除非列表已经排序，否则Cunningham的方法要快得多（如果部分排序，eglib略快）。eglib代码使用固定表来保存归并排序递归，而Cunningham的方法通过使用递归的不断增加级别来工作——因此它从不使用递归开始，然后是1级递归，然后是2级递归等等，根据需要做排序的步骤数。我发现Cunningham的代码更容易理解，而且不需要猜测递归表应该有多大，所以我更喜欢它。我从这个页面尝试的其他方法要慢两倍或更多。
这是Pop-11排序的C#移植版本：
/// <summary>
/// Sort a linked list in place. Returns the sorted list.
/// Originally by Jonathan Cunningham in Pop-11, May 1981.
/// Ported to C# by Jon Meyer.
/// </summary>
public class ListSorter<T> where T : IComparable<T> {
SingleListNode<T> workNode = new SingleListNode<T>(default(T));
SingleListNode<T> list;
/// <summary>
/// Sorts a linked list. Returns the sorted list.
/// </summary>
public SingleListNode<T> Sort(SingleListNode<T> head) {
if (head == null) throw new NullReferenceException("head");
list = head;
var run = GetRun(); // get first run
// As we progress, we increase the recursion depth.
var n = 1;
while (list != null) {
var run2 = GetSequence(n);
run = Merge(run, run2);
n++;
}
return run;
}
// Get the longest run of ordered elements from list.
// The run is returned, and list is updated to point to the
// first out-of-order element.
SingleListNode<T> GetRun() {
var run = list; // the return result is the original list
var prevNode = list;
var prevItem = list.Value;
list = list.Next; // advance to the next item
while (list != null) {
var comp = prevItem.CompareTo(list.Value);
if (comp > 0) {
// reached end of sequence
prevNode.Next = null;
break;
}
prevItem = list.Value;
prevNode = list;
list = list.Next;
}
return run;
}
// Generates a sequence of Merge and GetRun() operations.
// If n is 1, returns GetRun()
// If n is 2, returns Merge(GetRun(), GetRun())
// If n is 3, returns Merge(Merge(GetRun(), GetRun()),
// Merge(GetRun(), GetRun()))
// and so on.
SingleListNode<T> GetSequence(int n) {
if (n < 2) {
return GetRun();
} else {
n--;
var run1 = GetSequence(n);
if (list == null) return run1;
var run2 = GetSequence(n);
return Merge(run1, run2);
}
}
// Given two ordered lists this returns a list that is the
// result of merging the two lists in-place (modifying the pairs
// in list1 and list2).
SingleListNode<T> Merge(SingleListNode<T> list1, SingleListNode<T> list2) {
// we reuse a single work node to hold the result.
// Simplifies the number of test cases in the code below.
var prevNode = workNode;
while (true) {
if (list1.Value.CompareTo(list2.Value) <= 0) {
// list1 goes first
prevNode.Next = list1;
prevNode = list1;
if ((list1 = list1.Next) == null) {
// reached end of list1 - join list2 to prevNode
prevNode.Next = list2;
break;
}
} else { // same but for list2
prevNode.Next = list2;
prevNode = list2;
if ((list2 = list2.Next) == null) {
prevNode.Next = list1;
break;
}
}
}
// the result is in the back of the workNode
return workNode.Next;
}
}
- Jon Meyer
2
mono eglib 方法与我在答案中发布的方法类似，两者本质上与 HP / Microsoft STL std::list::sort() 相同。在 mono eglib 示例中，“递归”表被反转，rank[i] 指向长度为 2 的 i 次幂的运行，除了最后一个条目 rank[MAX_RANKS-1] 指向无限大小的列表，并通过合并长度为 2 的 MAX_RANK-2 次幂的运行来添加。MAX_RANK 在 26 到 32 之间已经足够了。 - rcgldr
在浮点数求和函数中，使用了类似的策略，其中一个由浮点数指数索引的部分和数组用于保存部分和，因此只有具有相同指数的值才会被添加，直到通过从最小到最大的顺序将数组中的值相加来返回完整的总和。我不确定哪个是先发明的，求和函数还是链表归并排序。 - rcgldr
1
这是一个非递归的链表归并排序示例，其中函数不是类的一部分。此示例代码和 HP / Microsoft 的
Visual Studio 2015将
std::list::sort 使用相同的基本算法。这是一种自底向上、非递归的归并排序，使用一个小型（26到32个）指向列表第一个节点的指针数组，其中array[i] 要么为0，要么指向大小为2的i次方的列表。在我的系统上，Intel 2600K 3.4ghz，它可以在大约1秒钟内对具有32位无符号整数数据的400万个节点进行排序。typedef struct NODE_{
struct NODE_ * next;
uint32_t data;
}NODE;
NODE * MergeLists(NODE *, NODE *); /* prototype */
/* sort a list using array of pointers to list */
/* aList[i] == NULL or ptr to list with 2^i nodes */
#define NUMLISTS 32 /* number of lists */
NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS]; /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
if(pList == NULL) /* check for empty list */
return NULL;
for(i = 0; i < NUMLISTS; i++) /* init array */
aList[i] = NULL;
pNode = pList; /* merge nodes into array */
while(pNode != NULL){
pNext = pNode->next;
pNode->next = NULL;
for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
pNode = MergeLists(aList[i], pNode);
aList[i] = NULL;
}
if(i == NUMLISTS) /* don't go beyond end of array */
i--;
aList[i] = pNode;
pNode = pNext;
}
pNode = NULL; /* merge array into one list */
for(i = 0; i < NUMLISTS; i++)
pNode = MergeLists(aList[i], pNode);
return pNode;
}
/* merge two already sorted lists */
/* compare uses pSrc2 < pSrc1 to follow the STL rule */
/* of only using < and not <= */
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL; /* destination head ptr */
NODE **ppDst = &pDst; /* ptr to head or prev->next */
if(pSrc1 == NULL)
return pSrc2;
if(pSrc2 == NULL)
return pSrc1;
while(1){
if(pSrc2->data < pSrc1->data){ /* if src2 < src1 */
*ppDst = pSrc2;
pSrc2 = *(ppDst = &(pSrc2->next));
if(pSrc2 == NULL){
*ppDst = pSrc1;
break;
}
} else { /* src1 <= src2 */
*ppDst = pSrc1;
pSrc1 = *(ppDst = &(pSrc1->next));
if(pSrc1 == NULL){
*ppDst = pSrc2;
break;
}
}
}
return pDst;
}
Visual Studio 2015将
std::list::sort更改为基于迭代器而不是列表，并且还更改为自上而下的归并排序，这需要扫描开销。我最初认为切换到自上而下是必要的，以便与迭代器一起使用，但当再次被问及时，我进行了调查，并确定切换到较慢的自上而下方法是不必要的，可以使用相同的基于迭代器的逻辑实现自下而上。此链接中的答案解释了这一点，并提供了一个独立的示例，以及VS2019中std::list::sort()的替代品在包含文件"list"中。
- rcgldr
1
基于得票最高的答案，这是一个经过测试、可用的单链表的C++版本。
singlelinkedlist.h:
#pragma once
#include <stdexcept>
#include <iostream>
#include <initializer_list>
namespace ythlearn{
template<typename T>
class Linkedlist{
public:
class Node{
public:
Node* next;
T elem;
};
Node head;
int _size;
public:
Linkedlist(){
head.next = nullptr;
_size = 0;
}
Linkedlist(std::initializer_list<T> init_list){
head.next = nullptr;
_size = 0;
for(auto s = init_list.begin(); s!=init_list.end(); s++){
push_left(*s);
}
}
int size(){
return _size;
}
bool isEmpty(){
return size() == 0;
}
bool isSorted(){
Node* n_ptr = head.next;
while(n_ptr->next != nullptr){
if(n_ptr->elem > n_ptr->next->elem)
return false;
n_ptr = n_ptr->next;
}
return true;
}
Linkedlist& push_left(T elem){
Node* n = new Node;
n->elem = elem;
n->next = head.next;
head.next = n;
++_size;
return *this;
}
void print(){
Node* loopPtr = head.next;
while(loopPtr != nullptr){
std::cout << loopPtr->elem << " ";
loopPtr = loopPtr->next;
}
std::cout << std::endl;
}
void call_merge(){
head.next = merge_sort(head.next);
}
Node* merge_sort(Node* n){
if(n == nullptr || n->next == nullptr)
return n;
Node* middle = getMiddle(n);
Node* left_head = n;
Node* right_head = middle->next;
middle->next = nullptr;
return merge(merge_sort(left_head), merge_sort(right_head));
}
Node* getMiddle(Node* n){
if(n == nullptr)
return n;
Node* slow, *fast;
slow = fast = n;
while(fast->next != nullptr && fast->next->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
Node* merge(Node* a, Node* b){
Node dummyHead;
Node* current = &dummyHead;
while(a != nullptr && b != nullptr){
if(a->elem < b->elem){
current->next = a;
a = a->next;
}else{
current->next = b;
b = b->next;
}
current = current->next;
}
current->next = (a == nullptr) ? b : a;
return dummyHead.next;
}
Linkedlist(const Linkedlist&) = delete;
Linkedlist& operator=(const Linkedlist&) const = delete;
~Linkedlist(){
Node* node_to_delete;
Node* ptr = head.next;
while(ptr != nullptr){
node_to_delete = ptr;
ptr = ptr->next;
delete node_to_delete;
}
}
};
}
main.cpp:
#include <iostream>
#include <cassert>
#include "singlelinkedlist.h"
using namespace std;
using namespace ythlearn;
int main(){
Linkedlist<int> l = {3,6,-5,222,495,-129,0};
l.print();
l.call_merge();
l.print();
assert(l.isSorted());
return 0;
}
- Rick
1
感谢您提供模块化的代码。我有一个关于获取列表中间元素的条件的疑问。
我正在使用以下代码：
while(slow ! = nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
它没有给我正确的输出，而是崩溃了。请问您能否解释一下您使用的条件，即：
slow = slow->next;
fast = fast->next->next;
}为什么我们要检查fast->next->next？谢谢。 - Chandra Shekhar网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接