标题：
链接列表内存排序
语言：
C
作者：
Philip J. Erdelsky
日期：
1998年7月31日
用法：
公共区域; 没有使用限制
可移植性：
任何 C 编译器
关键词：
链接列表，排序
抽象：
AC函数使用任意比较函数和磁带合并（tape-merge）算法对内存中的链表进行排序，在所有情况下复杂度都是 O(n log n)。该函数是非递归和可重入的，只更改链接。
链接列表和排序例程在编程中非常常见。
函数 sort_linked_list() 将使用调用程序提供的比较函数对几乎任何类型的单链表进行排序。它比 qsort() 具有以下优点：
- 它对可变大小的元素进行排序。
- 无论初始顺序如何，它都需要 O(n log n) 次比较。对列表进行排序的时间是可预测且一致的。已知这种性能对于一般排序是最佳的。
- 该算法是迭代的，而不是递归的，因此不存在堆栈溢出问题。堆栈要求是可预测的，一致的，并且很小。
- 它通过更改指针来排序链接列表，而不是通过移动元素本身。
- 它可以对太大而无法放入数组中的列表进行排序。
该函数仅对单向链接列表进行排序。如果列表是双向链接的，则可以通过几行代码在排序后恢复后向指针。
要排序的链表的每个元素必须包含一个或多个指针作为其第一个成员。其中一个指针必须位于每个元素的相同位置，它是指向下一个元素的指针。该指针在最后一个元素中为NULL。
索引是每个该针在元素中的位置。第一个指针为0，第二个指针为1，等等。
让 compare() 成为比较两个元素的比较函数，如下所示：
n = compare(p，q，pointer);
void * p，* q; 指向两个列表元素的指针
void *pointer; 用户定义的指针传，通过linked_list_sort()递给compare()
int n; 比较* p和* q的结果
> 0如果* p按排序顺序在* q之后
< 0如果* p按排序顺序在* q之前
如果* p和* q的顺序无关，则为0
让“first”成为指向列表第一个元素的指针。然后，以下函数调用对列表进行排序，并返回指向排序列表的第一个元素的指针：
first_sorted = sort_linked_list（first，index，compare，pointer，pcount）;
第四个参数（pointer）传递给 compare() 而不做任何更改。这里给出的例子不使用指针。但是，如果两个或更多比较方法共享大量代码并且仅在一个或多个参数值方面不同，则它可以是非常有用的特征。
最后一个参数（pcount）是类型（unsigned long *）。如果它不是NULL，则将* pcount设置为等于列表中的记录数。
允许对空列表进行排序。如果first == NULL，则返回的值也将为NULL。
例如，元素可以包含名称和数字：
struct element
{
struct element * next_in_alphabetical_order;
struct element * next_in_numerical_order;
char name [9];
int number;
/ *其他成员，如果有的话* /
};
最初，每个元素中的两个指针是相同的，并且列表是任意顺序，其中“first”是指向第一个元素的指针。以下两个函数调用对列表进行两次排序：
first_in_alphabetical_order = sort_linked_list(first, 0, compare_names, NULL);
first_in_numerical_order = sort_linked_list(first, 1, compare_numbers, NULL);
以下是比较功能：
int compare_names(struct element * p, struct element * q, void *pointer）
{
return strcmp(p-> name, q-> name);
}
int compare_numbers(struct element * p, struct element * q, void *pointer)
{
return p->number > q->number ? 1 : -1;
/ *注意：返回 p->number – q->number就足够了，
如果没有数字溢出的危险* /
}
此类型的先前版本发布在技术期刊中，要求前向链接位于每个元素的开头。虽然这使得排序更有效，但它也使得难以与多重链表一起使用。
算法相当简单。链表（通过类似于旧磁带称为“磁带”）首先被分成两个相同或几乎相同大小的磁带。这是通过交替地将元素“写入”到两个磁带来完成的。
然后，两个磁带逐个元素地合并到每个包含两个元素的排序块中。这些块交替写入另外两个磁带。
然后将这两个磁带逐块合并为每个四个元素的排序块，并将这些块交替写入另外两个磁带。
该过程继续，每次将块大小加倍，直到所有元素都在一个磁带上的单个排序块中。该函数返回指向该磁带的第一个元素的指针。
每个合并都需要 O(n) 比较，其中n是元素的数量。合并的数量是 O(log n)。因此整个排序需要进行 O(n log n) 比较。
如果比较函数是可重入的，则 sort_linked_list() 函数是可重入的。
C aficionados很高兴知道这个算法不能在Ada或Pascal中轻松编码，因为它依赖于类型转换。
如果包含头文件 LLMSORT.H，则可以从 C++ 程序轻松调用 sort_linked_list() 函数，并使用一些类型检查。它包含一个用于在sort_linked_list() 上内联生成调用的模板。通话的格式如下：
#include“llmsort.h”
first_sorted = sort_list(first, compare, pointer, pcount);
yourclass * first;
yourclass * first_sorted;
void *pointer;
unsigned long * pcount;
函数 compare() 调用如下：
n = compare(p, q, pointer);
const yourclass * p;
const yourclass * q;
void * pointer;
int n;
这里“yourclass”是你可以定义的任何类。编译器将检查参数类型的一致性，并在 sort_linked_list() 上生成适当的调用。
文本格式的源代码：