私は最近、いくつかの基本事項をブラッシュアップしていて、リンクリストのマージソートがかなり良い課題であることに気づきました。優れた実装がある場合は、ここでそれを披露してください。
質問する
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
興味深い方法の1つは、スタックを維持し、スタック上のリストに同じ数の要素がある場合にのみマージし、それ以外の場合は、着信リストの要素がなくなるまでリストをプッシュしてから、スタックをマージすることです。
于 2008-08-11T13:57:59.063 に答える
2
最も単純なのは、 Gonnet + Baeza Yates HandbookofAlgorithmsからです。必要な数のソートされた要素でそれを呼び出します。これは、サイズ1のリストの要求に達するまで再帰的に二分され、その後、元のリストの前面を剥がします。これらはすべて、フルサイズのソート済みリストにマージされます。
[最初の投稿のクールなスタックベースのものはオンラインマージソートと呼ばれ、KnuthVol3の演習で最も小さな言及があります]
于 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
私はこのアルゴリズムのためにクラッターを最適化することに執着していましたが、最終的にたどり着いたのは以下です。インターネットと 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 のリストの null リストなどの場合には、特別な処理は必要ありません。これらのケースは「うまくいく」。
- 多くの「標準」アルゴリズムのテキストには、残りの要素を調べて、一方のリストが他方より短い場合に対処するための 2 つのループがあります。上記のコードにより、その必要がなくなります。
- ソートが安定していることを確認します
- ホット スポットである内側の while ループは、反復ごとに平均 3 つの式を評価します。これは、最小であると思います。
更新: @ideasman42 が上記のコードを C/C++に変換し、コメントの修正ともう少し改善するための提案を行いました。上記のコードは、これらで最新のものになりました。
于 2014-12-27T03:02:15.093 に答える
1
mono eglibには、非再帰的なリンクリストのマージソートがあります。
基本的な考え方は、さまざまなマージの制御ループが 2 進整数のビット単位のインクリメントに対応しているということです。マージ ツリーにnノードを「挿入」するO(n)マージがあり、それらのマージのランクは、インクリメントされる 2 進数に対応します。このアナロジーを使用すると、マージ ツリーのO(log n)ノードだけを一時的な保持配列に具体化する必要があります。
于 2013-08-15T05:34:58.650 に答える
1
これは、Knuth の「リスト マージ ソート」(TAOCP 第 3 版、第 2 版のアルゴリズム 5.2.4L) の私の実装です。最後にコメントを追加しますが、要約は次のとおりです。
ランダムな入力では、Simon Tatham のコード (リンク付きの Dave Gamble の非再帰的な回答を参照) よりも少し速く実行されますが、Dave Gamble の再帰的なコードよりは少し遅くなります。どちらかよりも分かりにくいです。少なくとも私の実装では、各要素に要素への 2 つのポインターが必要です。(代替手段は、1 つのポインターとブール値のフラグです。) したがって、これはおそらく有用なアプローチではありません。ただし、1 つの特徴的な点は、入力に既に並べ替えられた長いストレッチがある場合、非常に高速に実行されることです。
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
関数がクラスの一部ではない、リンクされたリストの非再帰マージソートの別の例。このコード例と HP / Microsoftstd::list::sortはどちらも同じ基本アルゴリズムを使用しています。リストの最初のノードへのポインターの小さな (26 ～ 32) 配列を使用するボトムアップ、非再帰、マージ ソートarray[i]。私のシステム、Intel 2600K 3.4ghz では、32 ビットの符号なし整数をデータとして持つ 400 万ノードを約 1 秒でソートできます。
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 2015std::list::sortは、リストではなく反復子に基づくように変更され、スキャンのオーバーヘッドが必要なトップダウン マージ ソートにも変更されました。最初は、イテレータを操作するにはトップダウンへの切り替えが必要だと思っていましたが、再度尋ねられたときにこれを調査したところ、遅いトップダウン方式への切り替えは不要であり、ボトムアップは次の方法で実装できると判断しました。同じ反復子ベースのロジック。このリンクの回答はこれを説明し、スタンドアロンの例とstd::list::sort()、インクルード ファイル「リスト」の VS2019 の代替を提供します。
于 2015-11-29T20:47:50.073 に答える
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 に答える