📄 mergesort.ct.html
字号:
<html><!-- Mirrored from c-faq.com/lib/mergesort.ct.html by HTTrack Website Copier/3.x [XR&CO'2008], Sat, 14 Mar 2009 08:01:32 GMT --><head><title>Sorting linked lists</title></head><body>From: torek@elf.bsdi.com (Chris Torek)<br>Newsgroups: comp.lang.c<br>Subject: Re: Sorting linked lists<br>Date: 10 Jan 1999 05:39:20 -0800<br>Message-ID: <77aai8$f48@elf.bsdi.com><p>Martin (Jambo@home.se) wrote:<br>>> ... is there any better way to sort linked list?<p>In article <F5BpFJ.1Ms@fcshome.stoneham.ma.us> fred smith<fredex@fcshome.stoneham.ma.us> wrote:<br>>Sorting a linked list which already exists can be tedious and<br>>resource-intensive.<p>Actually, a merge sort is generally both simple and efficient.The hardest part about a merge sort is breaking a list in half.If you do not care about "stable" sorts, you can break it in halfthe easy way, by alternation:<p><pre> /* * split the list (turning this into a function, or inserting * it into mergesort() below, is left as an exercise to the reader, * as are better methods of splitting). */ struct list *left, *right, **lp, **rp; /* input: list != NULL; it has an even or odd number of entries */ lp = &left; rp = &right; do { /* put one node on the left-hand list */ *lp = list; lp = &list->next; list = list->next; /* that could be the last node, so check */ if (list == NULL) break; /* put another node on the right-hand list */ *rp = list; rp = &list->next; list = list->next; /* and repeat until we run out of nodes */ } while (list != NULL); /* * Make sure the two lists are properly terminated. One of * these two assignments is unnecessary, but so what? */ *lp = NULL; *rp = NULL;</pre><p>Once you have broken the list into two halves, the left and righthalves should be merge-sorted independently, and then the two listscan be merged together. This is like taking a deck of cards thathas been shuffled, giving each half to a friend and having him sortit, and then taking the two sorted piles and merging them pairwise:<p><pre>/* merge left and right lists (of any length) */struct list *merge(struct list *left, struct list *right, int (*compare)(struct list *, struct list *)) { struct list *new, **np; /* * Build the new list by putting in the smaller of each pair. */ np = &new; while (left != NULL && right != NULL) { if (compare(left, right) > 0) { /* left > right */ *np = right; /* so put the right node */ np = &right->next; /* onto the new list */ right = right->next; } else { /* left <= right */ *np = left; /* so put the left node */ np = &left->next; /* onto the new list */ left = left->next; } } /* * Now at least one of "left" and "right" is NULL, but not both. * If the left list is non-empty, the right one is empty, and we * just need to tack the left one on to the total list. If the * right list is non-empty, the left one is empty and we just need * to tack on the right-hand one. If both are empty, we need to * set *np = NULL, but in this case, "*np = right" will do the * trick too, so one single ?: expression suffices. */ *np = left != NULL ? left : right; return (new);}</pre><p>That leaves only the degenerate case of sorting an empty list at thetop of the overall sort routine, and you get something like this:<p><pre> struct list *mergesort(struct list *list, int (*compare)(struct list *, struct list *)) { struct list *left, *right; if (list == NULL) /* nothing to split */ return NULL; split(list, &left, &right); left = mergesort(left, compare); right = mergesort(right, compare); return merge(left, right, compare); }</pre><p>In other words, each friend who has to sort half the card-deck does<em>his</em> job by splitting <em>that</em> half-deck in half, having two morefriends sort those, and then merging those back. (Given theconstruction above, unlike with people, it is easier to hand off"no cards" and take back "no cards" than it is to recognize that"one card" is already sorted. Other merge-sort implementationsare possible, including doing an initial "count the nodes" pass;in this case, you can stop at "<TT>count < 2</TT>".)<p>>My preferred way is to make sure it is sorted when you build it.<p>In some applications, this is a good approach; however, it tends tobe O(n^2), while merge sort is O(n log n). Generally, if somethingshould be kept sorted as you go along, some kind of tree structureis appropriate.<br>-- <br>In-Real-Life: Chris Torek, Berkeley Software Design Inc<br>El Cerrito, CA Domain: torek@bsdi.com +1 510 234 3167<br>http://claw.bsdi.com/torek/ (not always up) I report spam to abuse@.</body><!-- Mirrored from c-faq.com/lib/mergesort.ct.html by HTTrack Website Copier/3.x [XR&CO'2008], Sat, 14 Mar 2009 08:01:32 GMT --></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -