I was recently brushing up on some fundamentals and found merge sorting a linked list to be a pretty good challenge. If you have a good implementation then show it off here.
问问题
92675 次
19 回答
88
想知道为什么它应该是一个很大的挑战，正如这里所说，这里是一个简单的 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;
}
于 2011-11-23T06:46:38.353 回答
19
一个更简单/更清晰的实现可能是递归实现，从中 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) 存储要求。性能应该与我发布的其他策略大致相当。这里有一个潜在的优化，通过运行合并循环 while (list && right)，并简单地附加剩余的列表（因为我们并不真正关心列表的结尾；知道它们已合并就足够了）。
于 2010-06-13T14:29:29.877 回答
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) 资源（没有递归，没有堆栈，什么都没有）。
于 2010-06-13T13:53:46.487 回答
6
One interesting way is to maintain a stack, and only merge if the list on the stack has the same number of elements, and otherwise push the list, until you run out of elements in the incoming list, and then merge up the stack.
于 2008-08-11T13:57:59.063 回答
2
我一直痴迷于优化这个算法的混乱，下面是我最终得出的结论。Internet 和 StackOverflow 上的许多其他代码都非常糟糕。有些人试图获得列表的中间点，进行递归，对剩余节点进行多个循环，维护大量事物的数量 - 所有这些都是不必要的。MergeSort 自然适合链表，算法可以很漂亮和紧凑，但要达到那种状态并非易事。
据我所知，下面的代码维护最少数量的变量和算法所需的最少逻辑步骤（即不使代码不可维护/不可读）。但是，我没有尝试最小化 LOC 并保留尽可能多的空白以保持可读性。我已经通过相当严格的单元测试测试了这段代码。
请注意，此答案结合了其他答案https://stackoverflow.com/a/3032462/207661中的一些技术。虽然代码在 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;
}
兴趣点
- 对于需要的 1 列表的空列表等情况，没有特殊处理。这些案例“有效”。
- 许多“标准”算法文本有两个循环来遍历剩余元素，以处理一个列表比另一个列表短的情况。上面的代码消除了对它的需要。
- 我们确保排序是稳定的
- 作为热点的内部while循环平均每次迭代评估3个表达式，我认为这是最低限度的。
更新：@ideasman42 已将上述代码翻译为 C/C++，并附有修复注释和更多改进的建议。上面的代码现在是最新的。
于 2014-12-27T03:02:15.093 回答
2
最简单的是来自 Gonnet + Baeza Yates Handbook of Algorithms。你用你想要的排序元素的数量来调用它，它递归地被二等分，直到它达到一个大小为一列表的请求，然后你只需剥离原始列表的前面。这些都被合并成一个完整大小的排序列表。
[请注意，第一篇文章中基于堆栈的很酷的称为 Online Mergesort，它在 Knuth Vol 3 的练习中得到了最少的提及]
于 2008-09-04T09:22:26.480 回答
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;
}
}
}
于 2012-07-15T10:06:25.030 回答
2
我决定在这里测试这些示例，以及另一种方法，最初由 Jonathan Cunningham 在 Pop-11 中编写。我用 C# 编写了所有方法，并与一系列不同的列表大小进行了比较。我比较了 Raja R Harinath 的 Mono eglib 方法、Shital Shah 的 C# 代码、Jayadev 的 Java 方法、David Gamble 的递归和非递归版本、Ed Wynn 的第一个 C 代码（这与我的示例数据集崩溃了，我没有调试）和坎宁安的版本。完整代码在这里：https ://gist.github.com/314e572808f29adb0e41.git 。
Mono eglib 基于与 Cunningham 类似的想法并且具有相当的速度，除非列表恰好已经排序，在这种情况下，Cunningham 的方法要快得多（如果它部分排序，eglib 会稍微快一些）。eglib 代码使用一个固定的表来保存合并排序递归，而 Cunningham 的方法通过使用递增级别的递归来工作 - 所以它开始使用不递归，然后是 1-deep recursion，然后是 2-deep recursion 等等，根据进行排序需要多少步骤。我发现 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;
}
}
于 2015-11-24T17:17:07.087 回答
1
这是我对 Knuth 的“列表合并排序”的实现（来自 TAOCP 第 3 卷的算法 5.2.4L，第 2 版）。我会在最后添加一些评论，但这里是一个摘要：
在随机输入上，它的运行速度比 Simon Tatham 的代码快一点（参见 Dave Gamble 的非递归答案，带有链接），但比 Dave Gamble 的递归代码慢一点。这比任何一个都更难理解。至少在我的实现中，它要求每个元素都有两个指向元素的指针。（另一种方法是一个指针和一个布尔标志。）因此，这可能不是一种有用的方法。然而，一个独特的点是，如果输入有很长的一段已经排序，它会运行得非常快。
element *knuthsort(element *list)
{ /* This is my attempt at implementing Knuth's Algorithm 5.2.4L "List merge sort"
from Vol.3 of TAOCP, 2nd ed. */
element *p, *pnext, *q, *qnext, head1, head2, *s, *t;
if(!list) return NULL;
L1: /* This is the clever L1 from exercise 12, p.167, solution p.647. */
head1.next=list;
t=&head2;
for(p=list, pnext=p->next; pnext; p=pnext, pnext=p->next) {
if( cmp(p,pnext) > 0 ) { t->next=NULL; t->spare=pnext; t=p; }
}
t->next=NULL; t->spare=NULL; p->spare=NULL;
head2.next=head2.spare;
L2: /* begin a new pass: */
t=&head2;
q=t->next;
if(!q) return head1.next;
s=&head1;
p=s->next;
L3: /* compare: */
if( cmp(p,q) > 0 ) goto L6;
L4: /* add p onto the current end, s: */
if(s->next) s->next=p; else s->spare=p;
s=p;
if(p->next) { p=p->next; goto L3; }
else p=p->spare;
L5: /* complete the sublist by adding q and all its successors: */
s->next=q; s=t;
for(qnext=q->next; qnext; q=qnext, qnext=q->next);
t=q; q=q->spare;
goto L8;
L6: /* add q onto the current end, s: */
if(s->next) s->next=q; else s->spare=q;
s=q;
if(q->next) { q=q->next; goto L3; }
else q=q->spare;
L7: /* complete the sublist by adding p and all its successors: */
s->next=p;
s=t;
for(pnext=p->next; pnext; p=pnext, pnext=p->next);
t=p; p=p->spare;
L8: /* is this end of the pass? */
if(q) goto L3;
if(s->next) s->next=p; else s->spare=p;
t->next=NULL; t->spare=NULL;
goto L2;
}
于 2012-07-14T19:15:54.240 回答
1
mono eglib中有一个非递归链表合并排序。
基本思想是各种合并的控制循环平行于二进制整数的按位递增。有O(n)次合并将n 个节点“插入”到合并树中，这些合并的等级对应于递增的二进制数字。使用这个类比，只有合并树的O(log n)个节点需要物化到一个临时保存数组中。
于 2013-08-15T05:34:58.650 回答
1
链表的非递归合并排序的另一个示例，其中函数不是类的一部分。此示例代码和 HP / Microsoftstd::list::sort都使用相同的基本算法。自下而上、非递归、合并排序，它使用一个小的（26 到 32）指针数组，指向列表的第一个节点，其中array[i]0 或指向大小为 2 的 i 次幂的列表。在我的系统 Intel 2600K 3.4ghz 上，它可以在大约 1 秒内将 400 万个具有 32 位无符号整数的节点排序为数据。
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为基于迭代器而不是列表，并且还更改为自上而下的合并排序，这需要扫描的开销。我最初认为需要切换到自上而下才能与迭代器一起使用，但是当再次询问时，我对此进行了调查并确定不需要切换到较慢的自上而下方法，并且可以使用自下而上实现相同的基于迭代器的逻辑。此链接中的答案解释了这一点，并提供了一个独立的示例以及std::list::sort()包含文件“列表”中 VS2019 的替代品。
于 2015-11-29T20:47:50.073 回答
1
一个经过测试的工作C++版本的单链表，基于最高投票的答案。
单链表.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;
}
}
};
}
主.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;
}
于 2019-01-04T09:06:14.603 回答
0
最简单的Java实现：
时间复杂度：O(nLogn) n = 节点数。链表的每次迭代都会使已排序的较小链表的大小加倍。例如，在第一次迭代之后，链表将被分成两半。第二次迭代后，链表将被分成四半。它将继续排序到链表的大小。这将使小链表的大小增加 O(logn) 倍才能达到原始链表的大小。nlogn 中的 n 存在是因为链表的每次迭代所花费的时间与原始链表中的节点数成正比。
class Node {
int data;
Node next;
Node(int d) {
data = d;
}
}
class LinkedList {
Node head;
public Node mergesort(Node head) {
if(head == null || head.next == null) return head;
Node middle = middle(head), middle_next = middle.next;
middle.next = null;
Node left = mergesort(head), right = mergesort(middle_next), node = merge(left, right);
return node;
}
public Node merge(Node first, Node second) {
Node node = null;
if (first == null) return second;
else if (second == null) return first;
else if (first.data <= second.data) {
node = first;
node.next = merge(first.next, second);
} else {
node = second;
node.next = merge(first, second.next);
}
return node;
}
public Node middle(Node head) {
if (head == null) return head;
Node second = head, first = head.next;
while(first != null) {
first = first.next;
if (first != null) {
second = second.next;
first = first.next;
}
}
return second;
}
}
于 2019-05-21T14:42:56.170 回答
0
这是使用Swift Programming Language的解决方案。
//Main MergeSort Function
func mergeSort(head: Node?) -> Node? {
guard let head = head else { return nil }
guard let _ = head.next else { return head }
let middle = getMiddle(head: head)
let left = head
let right = middle.next
middle.next = nil
return merge(left: mergeSort(head: left), right: mergeSort(head: right))
}
//Merge Function
func merge(left: Node?, right: Node?) -> Node? {
guard let left = left, let right = right else { return nil}
let dummyHead: Node = Node(value: 0)
var current: Node? = dummyHead
var currentLeft: Node? = left
var currentRight: Node? = right
while currentLeft != nil && currentRight != nil {
if currentLeft!.value < currentRight!.value {
current?.next = currentLeft
currentLeft = currentLeft!.next
} else {
current?.next = currentRight
currentRight = currentRight!.next
}
current = current?.next
}
if currentLeft != nil {
current?.next = currentLeft
}
if currentRight != nil {
current?.next = currentRight
}
return dummyHead.next!
}
这是节点类和getMiddle 方法
class Node {
//Node Class which takes Integers as value
var value: Int
var next: Node?
init(value: Int) {
self.value = value
}
}
func getMiddle(head: Node) -> Node {
guard let nextNode = head.next else { return head }
var slow: Node = head
var fast: Node? = head
while fast?.next?.next != nil {
slow = slow.next!
fast = fast!.next?.next
}
return slow
}
于 2020-07-28T20:13:13.660 回答
0
我在这里没有看到任何 C++ 解决方案。所以，就这样吧。希望它可以帮助某人。
class Solution {
public:
ListNode *merge(ListNode *left, ListNode *right){
ListNode *head = NULL, *temp = NULL;
// Find which one is the head node for the merged list
if(left->val <= right->val){
head = left, temp = left;
left = left->next;
}
else{
head = right, temp = right;
right = right->next;
}
while(left && right){
if(left->val <= right->val){
temp->next = left;
temp = left;
left = left->next;
}
else{
temp->next = right;
temp = right;
right = right->next;
}
}
// If some elements still left in the left or the right list
if(left)
temp->next = left;
if(right)
temp->next = right;
return head;
}
ListNode* sortList(ListNode* head){
if(!head || !head->next)
return head;
// Find the length of the list
int length = 0;
ListNode *temp = head;
while(temp){
length++;
temp = temp->next;
}
// Reset temp
temp = head;
// Store half of it in left and the other half in right
// Create two lists and sort them
ListNode *left = temp, *prev = NULL;
int i = 0, mid = length / 2;
// Left list
while(i < mid){
prev = temp;
temp = temp->next;
i++;
}
// The end of the left list should point to NULL
if(prev)
prev->next = NULL;
// Right list
ListNode *right = temp;
// Sort left list
ListNode *sortedLeft = sortList(left);
// Sort right list
ListNode *sortedRight = sortList(right);
// Merge them
ListNode *sortedList = merge(sortedLeft, sortedRight);
return sortedList;
}
};
于 2018-08-14T00:08:49.237 回答
0
这是整个代码段，展示了我们如何在 java 中创建链接列表并使用合并排序对其进行排序。我在 MergeNode 类中创建节点，还有另一个 MergesortLinklist 类，其中有划分和合并逻辑。
class MergeNode {
Object value;
MergeNode next;
MergeNode(Object val) {
value = val;
next = null;
}
MergeNode() {
value = null;
next = null;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public MergeNode getNext() {
return next;
}
public void setNext(MergeNode next) {
this.next = next;
}
@Override
public String toString() {
return "MergeNode [value=" + value + ", next=" + next + "]";
}
}
public class MergesortLinkList {
MergeNode head;
static int totalnode;
public MergeNode getHead() {
return head;
}
public void setHead(MergeNode head) {
this.head = head;
}
MergeNode add(int i) {
// TODO Auto-generated method stub
if (head == null) {
head = new MergeNode(i);
// System.out.println("head value is "+head);
return head;
}
MergeNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new MergeNode(i);
return head;
}
MergeNode mergesort(MergeNode nl1) {
// TODO Auto-generated method stub
if (nl1.next == null) {
return nl1;
}
int counter = 0;
MergeNode temp = nl1;
while (temp != null) {
counter++;
temp = temp.next;
}
System.out.println("total nodes " + counter);
int middle = (counter - 1) / 2;
temp = nl1;
MergeNode left = nl1, right = nl1;
int leftindex = 0, rightindex = 0;
if (middle == leftindex) {
right = left.next;
}
while (leftindex < middle) {
leftindex++;
left = left.next;
right = left.next;
}
left.next = null;
left = nl1;
System.out.println(left.toString());
System.out.println(right.toString());
MergeNode p1 = mergesort(left);
MergeNode p2 = mergesort(right);
MergeNode node = merge(p1, p2);
return node;
}
MergeNode merge(MergeNode p1, MergeNode p2) {
// TODO Auto-generated method stub
MergeNode L = p1;
MergeNode R = p2;
int Lcount = 0, Rcount = 0;
MergeNode tempnode = null;
while (L != null && R != null) {
int val1 = (int) L.value;
int val2 = (int) R.value;
if (val1 > val2) {
if (tempnode == null) {
tempnode = new MergeNode(val2);
R = R.next;
} else {
MergeNode store = tempnode;
while (store.next != null) {
store = store.next;
}
store.next = new MergeNode(val2);
R = R.next;
}
} else {
if (tempnode == null) {
tempnode = new MergeNode(val1);
L = L.next;
} else {
MergeNode store = tempnode;
while (store.next != null) {
store = store.next;
}
store.next = new MergeNode(val1);
L = L.next;
}
}
}
MergeNode handle = tempnode;
while (L != null) {
while (handle.next != null) {
handle = handle.next;
}
handle.next = L;
L = null;
}
// Copy remaining elements of L[] if any
while (R != null) {
while (handle.next != null) {
handle = handle.next;
}
handle.next = R;
R = null;
}
System.out.println("----------------sorted value-----------");
System.out.println(tempnode.toString());
return tempnode;
}
public static void main(String[] args) {
MergesortLinkList objsort = new MergesortLinkList();
MergeNode n1 = objsort.add(9);
MergeNode n2 = objsort.add(7);
MergeNode n3 = objsort.add(6);
MergeNode n4 = objsort.add(87);
MergeNode n5 = objsort.add(16);
MergeNode n6 = objsort.add(81);
MergeNode n7 = objsort.add(21);
MergeNode n8 = objsort.add(16);
MergeNode n9 = objsort.add(99);
MergeNode n10 = objsort.add(31);
MergeNode val = objsort.mergesort(n1);
System.out.println("===============sorted values=====================");
while (val != null) {
System.out.println(" value is " + val.value);
val = val.next;
}
}
}
于 2017-05-21T09:11:49.400 回答
0
嘿，我知道这是一个有点晚的答案，但得到了一个快速简单的答案。
代码在 F# 中，但可以使用任何语言。由于这是 ML 家族中一种不常见的语言，我将给出一些提高可读性的要点。F# 是通过制表完成的嵌套。函数（嵌套部分）中的最后一行代码是返回值。(x, y) 是一个元组，x::xs 是一个头部 x 和尾部 xs 的列表（其中 xs 可以为空），|> 将最后一行的结果作为一个管道它作为它右边表达式的参数(可读性增强) 和 last (fun args -> some expression) 是一个 lambda 函数。
// split the list into a singleton list
let split list = List.map (fun x -> [x]) lst
// takes to list and merge them into a sorted list
let sort lst1 lst2 =
// nested function to hide accumulator
let rec s acc pair =
match pair with
// empty list case, return the sorted list
| [], [] -> List.rev acc
| xs, [] | [], xs ->
// one empty list case,
// append the rest of xs onto acc and return the sorted list
List.fold (fun ys y -> y :: ys) acc xs
|> List.rev
// general case
| x::xs, y::ys ->
match x < y with
| true -> // cons x onto the accumulator
s (x::acc) (xs,y::ys)
| _ ->
// cons y onto the accumulator
s (y::acc) (x::xs,ys)
s [] (lst1, lst2)
let msort lst =
let rec merge acc lst =
match lst with
| [] ->
match acc with
| [] -> [] // empty list case
| _ -> merge [] acc
| x :: [] -> // single list case (x is a list)
match acc with
| [] -> x // since acc are empty there are only x left, hence x are the sorted list.
| _ -> merge [] (x::acc) // still need merging.
| x1 :: x2 :: xs ->
// merge the lists x1 and x2 and add them to the acummulator. recursiv call
merge (sort x1 x2 :: acc) xs
// return part
split list // expand to singleton list list
|> merge [] // merge and sort recursively.
重要的是要注意这是完全尾递归的，因此没有堆栈溢出的可能性，并且通过首先将列表扩展为单例列表，我们可以降低最坏成本的常数因子。由于合并正在处理列表列表，我们可以递归地合并和排序内部列表，直到我们到达所有内部列表都被排序到一个列表中的固定点，然后我们返回该列表，因此从一个列表列表折叠到一个列表再次。
于 2020-01-29T08:53:56.517 回答
0
这是链表上合并排序的Java实现：
- 时间复杂度：O(n.logn)
- 空间复杂度：O(1) - 链表上的合并排序实现避免了通常与算法相关的 O(n) 辅助存储成本
class Solution
{
public ListNode mergeSortList(ListNode head)
{
if(head == null || head.next == null)
return head;
ListNode mid = getMid(head), second_head = mid.next; mid.next = null;
return merge(mergeSortList(head), mergeSortList(second_head));
}
private ListNode merge(ListNode head1, ListNode head2)
{
ListNode result = new ListNode(0), current = result;
while(head1 != null && head2 != null)
{
if(head1.val < head2.val)
{
current.next = head1;
head1 = head1.next;
}
else
{
current.next = head2;
head2 = head2.next;
}
current = current.next;
}
if(head1 != null) current.next = head1;
if(head2 != null) current.next = head2;
return result.next;
}
private ListNode getMid(ListNode head)
{
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
于 2019-01-01T14:35:25.403 回答
-4
public int[] msort(int[] a) {
if (a.Length > 1) {
int min = a.Length / 2;
int max = min;
int[] b = new int[min];
int[] c = new int[max]; // dividing main array into two half arrays
for (int i = 0; i < min; i++) {
b[i] = a[i];
}
for (int i = min; i < min + max; i++) {
c[i - min] = a[i];
}
b = msort(b);
c = msort(c);
int x = 0;
int y = 0;
int z = 0;
while (b.Length != y && c.Length != z) {
if (b[y] < c[z]) {
a[x] = b[y];
//r--
x++;
y++;
} else {
a[x] = c[z];
x++;
z++;
}
}
while (b.Length != y) {
a[x] = b[y];
x++;
y++;
}
while (c.Length != z) {
a[x] = c[z];
x++;
z++;
}
}
return a;
}
于 2011-07-07T09:25:05.940 回答