Martin (Jambo@home.se) 写道
>> ...有没有更好的方法来排序链表？

在文章 <F5BpFJ.1Ms@fcshome.stoneham.ma.us> 中 fred smith <fredex@fcshome.stoneham.ma.us> 写道
>对已存在的链表进行排序可能很繁琐且
>资源密集。

实际上，归并排序通常既简单又高效。归并排序中最难的部分是将列表一分为二。如果你不关心“稳定性”排序，可以通过交替的方式轻松地将其分成两半

	/*
	 * 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;

将列表分成两半后，左右两半应该分别进行归并排序，然后可以将这两个列表合并起来。这就像拿到一副洗乱的扑克牌，把一半交给朋友让他排序，然后将两堆已排序好的牌进行逐对合并

/* 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);
}

这样就只剩下排序一个空列表的退化情况在整个排序例程的顶部，你就会得到类似这样的结果

	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);
	}

换句话说，每个要排序半副牌的朋友，都是通过将*那*半副牌一分为二，让另外两个朋友排序，然后再将它们合并起来来完成*他的*工作的。（根据上面的说明，与人不同的是，将“无牌”交给和取回“无牌”比识别出“一张牌”已经排好序要容易。也有其他的归并排序实现方式，包括进行一次初始的“计数节点”传递；在这种情况下，你可以停在“count < 2".)

>我更喜欢在构建时就确保它是排序好的。

在某些应用中，这是一种很好的方法；然而，它的复杂度通常是 O(n^2)，而归并排序是 O(n log n)。通常，如果要保持数据沿途有序，使用某种树形结构是合适的。
--
现实生活中：Chris Torek，Berkeley Software Design Inc
El Cerrito, CA 域名：torek@bsdi.com +1 510 234 3167
http://claw.bsdi.com/torek/ (不一定在线) 我会将垃圾邮件报告给 abuse@。