1. 索引和指针排序
因为元素的数量或者数据量巨大等原因，我们不希望频繁移动要排序的元素。因此，不移动元素的排序方法是维持一个索引数组或者索引指针，而排序的目标就是重排索引数组或指针。 如： 初始化for(int i = 0; i < N; i++)a[i] = &data[i]; 使用间接比较#define less(A, B) (*A < *B)
使用下标或指针排序的主要原因是避免扰乱要排序的数据。我们可以对只读文件进行排序，或者针对一个文件的多个关键字进行排序。 另一个原因是避免了移动整个记录，对大型记录（相对小的关键字值）的移动开销是巨大的。 例如：struct record { char [30]name; int num;}
int less(Item a, Item b){ return a->num < b->num;}
任意sort实现都将会基于这种类型的在整型域关键字上进行指针排序；
int less(Item a, Item b){ return strcmp(a->name, b->name) < 0; }
任意sort实现都将会基于这种类型的在字符串域关键字上进行指针排序；
间接排序要求额外的空间存储下标或指针数组，以及额外的空间进行间接比较，但是相比不需要移动数据的灵活性，这些开销不算大。对于大型记录的文件，我们一般选择间接排序。
2. 链表排序应用范围和基本原理对于存储在链表中的数据，我们需要使用链表排序方式。在某些情况下，只有数据能够按照高效支持链表操作的顺序方式时，算法才会有用。通常我们所操作的表节点的指针时有应用系统的其他部分维护的（多重链表），这意味着排序程序只能改变节点中的链接，不能改变关键字值和其他信息.我们需要的是改变链接本身，以使经过链接遍历链表时，节点时按顺序出现的，同时经由其他链接访问时，不影响他们原本的顺序。算法实现
我们维持一个输入链表（h->next指向这个链表，有表头），一个输出链表（out指向这个链表）。当链表非空时，遍历链表找出最大元素（因为链表之前易于插入元素，先插大的，在大的之前依次插入小的）,然后从输入表中去除这个最大元素，把他插入到输出表的前面。其中，找出最大元素函数findMax(),返回的是最大元素节点的上一节点的地址。（因为要想删除一个节点，必须知道它前一节点的地址prev->next = prev->next->next;）
C程序实现link linklist_sort(link h){link out, t, max;out , ;while(h->next != NULL){max = findMax(h);t next;next next->next;//删除max节点t->next = out;//将t插入到out前out = t;//返回out}h->next = out;return h;}
在一些表的处理中，我们不需要详细实现排序过程，只需要像插入排序依次向表中插入新元素，使表有序。
3. 关键字索引排序原理
所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。 被排序的对象–文件由一组记录组成。记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，，称为关键字项。该数据项的值称为关键字(Key)。 在待排序的文件中，若存在多个关键字相同的记录,我们希望通过按关键字索引排序，其中关键字是在一个小范围内的整数。 例如： 1）我们统计不同值的关键字个数分别是多少：6个0,4个1,2个2,3个3. 2）局部统计比其他关键字小的关键字的个数：0个关键字比0小，6个关键字比1小，10个关键字比2小，12个关键字比3小。 3）根据上述统计数作为索引将关键字放到合适位置：在开头0开始放具有0关键字的元素0，根据0，增加指针值，放下一个0关键字的元素3……）；将具有3关键字的元素从位置12开始放起（12个比3小）；以此类推
C程序实现void keyword_sort(Item a[], int l, int r){Item b[r-l+1];int cnt[M];//M为关键字的个数for(int j = 0; j < M; j++)//初始化个数全0cnt[j] = 0;for(int i = l; i <= r; i++) //统计不同值的关键字个数，cnt[a[i]+1]++;for(int j = 1; j < M; j++)//统计比关键字j小的关键字的个数，cnt[j]存储比关键字j小的元素个数cnt[j] = cnt[j] + cnt[j-1];for(int i = l; i <= r; i++) //按关键字个数索引放到辅助数组b中b[cnt[ a[i] ]++] = a[i];for(int i = l; i <= r; i++)a[i] = b[i-l]; }
如果要排序的文件很大，使用辅助数组b会导致内存分配问题，可以通过使用原位排序避免使用额外数组完成。
参考资料
《算法：C语言实现》P180~190
『 不可能 』只存在於蠢人的字典里
