李云清 杨庆红 揭安全第 10章 内排序排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内排序的各种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。
10.1 排序的基本概念假设一个文件是由 n个记录 R1,R2,…,Rn组成，
所谓排序就是以记录中某个 (或几个 )字段值不减 (或不增 )的次序将这 n个记录重新排列，称该字段为排序码。能唯一标识一个记录的字段称为关键码，关键码可以作为排序码，但排序码不一定要是关键码。
按排序过程中使用到的存储介质来分，可以将排序分成 两大类,内排序和外排序 。
内排序 是指在排序过程中所有数据均放在内存中处理，不需要使用外存的排序方法。而对于数据量很大的文件，在内存不足的情况下，则还需要使用外存，
这种排序方法称为 外排序 。
排序码相同的记录，若经过排序后，这些记录仍保持原来的相对次序不变，称这个排序算法是 稳定的 。否则，称为 不稳定的排序算法 。
评价排序算法优劣的标准,
首先考虑算法执行所需的时间，这主要是用执行过程中的比较次数和移动次数来度量；
其次考虑算法执行所需要的附加空间。
当然，保证算法的正确性是不言而喻的，可读性等也是要考虑的因素。
排序算法如未作特别的说明，使用的有关定义如下,
/*常见排序算法的头文件,文件名 table.h*/
#define MAXSIZE 100 /*文件中记录个数的最大值 */
typedef int keytype; /*定义排序码类型为整数类型 */
typedef struct{
keytype key;
/*此处还可以定义记录中除排序码外的其它域 */
}recordtype; /*记录类型的定义 */
typedef struct{
recordtype r[MAXSIZE+1];
int length; /*待排序文件中记录的个数 */
}table; /*待排序文件类型 */
为了方便,r[0]一般不用于存放排序码，在一些排序算法中它可以用来作为中间单元存放临时数据。 length
域是待排序的记录个数，它必须不大于 MAXSIZE，这样，
第 1~length个记录的排序码分别存于
r[1].key~r[length].key中
10.2 插入排序插入排序的基本方法是,
将待排序文件中的记录,逐个地按其排序码值的大小插入到目前已经排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。
10.2.1 直接插入排序直接插入排序算法的思路是,初始可认为文件中的第 1个记录己排好序，然后将第 2个到第 n个记录依次插入已排序的记录组成的文件中。在对第 i个记录 Ri进行插入时,R1,R2,…,Ri-1已排序，将记录 Ri的排序码
keyi与已经排好序的排序码从右向左依次比较，找到 Ri
应插入的位置，将该位置以后直到 Ri-1各记录顺序后移，
空出该位置让 Ri插入。
一组记录的排序码分别为,
312,126,272,226,28,165,123
初始时将第 1个排序码作为已经排好序的,把排好序的数据记录放入中括号 []中,表示有序的文件,剩下的在中括号外,如下所示：
[312],126,272,226,28,165,123
设前 3个记录的排序码已重新排列有序,构成一个含有 3个记录的有序文件,
[126,272,312],226,28,165,123
现在要将第 4个排序码 226插入 ！
[126,272,312],226,28,165,123
现在要将第 4个排序码 226插入 ！
将待插入的排序码 226和已经有序的最后一个排序码 312比较，因为待插入的排序码 226小于 312，所以 226肯定要置于 312的前面，至于是否就是置于 312
的前一个位置，此时还不能确定，需要继续向左比较；
将所有大于待插入排序码 226的那两个排序码
312和 272依次后移一个位置，在空出的位置插入待排序的排序码 226，得一含有 4个记录的有序文件：
[126,226,272,312],28,165,123
需要注意的是，当待插入排序码小于所有已排序的排序码时，如在插入第 5个值 28时：
[126,226,272,312],28,165,123
算法设计的时候如处理？
方法之一：设置“哨兵”
void insertsort(table *tab)
{
int i,j;
for(i=2;i<=tab->length;i++)/*依次插入从第 2个开始的所有元素 */
{ j=i-1;
tab->r[0].key=tab->r[i].key;/*设置哨兵,准备找插入位置 */
while(tab->r[0].key<tab->r[j].key) /*找插入位置并后移 */
{ tab->r[j+1].key=tab->r[j].key; /*后移 */
j=j-1; /*继续向前 （ 左 ） 查找 */
}
tab->r[j+1].key=tab->r[0].key; /*插入第 i个元素的副本,即前面设置的哨兵 */
}
}
算法 10.1 直接插入排序算法设待排序的 7记录的排序码为 {312,126,272,226,28,165，
123},直接插入排序算法的执行过程如图 10.2所示 。
哨兵 排序码
[] 312,126,272,226,28,165,123
初始 （） [312],126,272,226,28,165,123
i=2,（ 126） [126,312],272,226,28,165,123
i=3,（ 272） [126,272,312],226,28,165,123
i=4,（ 226） [126,226,272,312],28,165,123
i=5,（ 28） [28,126,226,272,312],165,123
i=6,（ 165） [28,126,165,226,272,312],123
i=7,（ 123） [28,123,126,165,226,272,312]
图 10.2 直接插入排序算法执行过程示意图直接插入排序算法执行时间的分析：
最好的情况,
即初始排序码开始就是有序的情况下，因为当插入第 i个排序码时，该算法内循环 while只进行一次条件判断而不执行循环体，外循环共执行 n-1次，其循环体内不含内循环每次循环要进行 2次移动操作，所以在最好情况下，直接插入排序算法的比较次数为 (n-1)次，
移动次数为 2*(n-1)次。
最坏情况,
即初始排序码开始是逆序的情况下，因为当插入第 i个排序码时，该算法内循环 while要执行 i次条件判断，循环体要执行 i-l次，每次要移动 1个记录，外循环共执行 n-1次，其循环体内不含内循环每次循环要进行 2次移动操作，所以在最坏情况下，比较次数为
(1+2+…+n)*(n -1)，移动次数为
(1+2+2+2+…+n+2)*(n -1)。假设待排序文件中的记录以各种排列出现的概率相同，因为当插入第 i个排序码时，该算法内循环 while平均约要执行 i/2次条件判断，
循环体要执行（ i-l） /2次，外循环共执行 n-1次，所以平均比较次数约为 (2+3+…+n)/2*(n -1)，平均移动次数为 (n-1)*(2+1+3+1+…+n+1)/2,也即直接插入排序算法的时间复杂度为 O(n2)。
10.2.2 二分法插入排序二分法插入排序的思想：
根据插入排序的基本思想，在找第 i个记录的插入位置时，前 i-l个记录已排序，将第 i个记录的排序码
key[i]和已排序的前 i-1个的中间位置记录的排序码进行比较，如果 key[i]小于中间位置记录排序码，则可以在前半部继续使用二分法查找，否则在后半部继续使用二分法查找，直到查找范围为空，即可确定 key[i]的插入位置。
void binarysort(table *tab)
{ int i,j,left,right,mid;
for(i=2;i<=tab->length;i++) /*依次插入从第 2个开始的所有元素 */
{ tab->r[0].key=tab->r[i].key; /*保存待插入的元素 */
left=1;right=i-1; /*设置查找范围的左,右位置值 */
while(left<=right) /*查找第 i个元素的插入位置 */
{ mid=(left+right)/2; /*取中点位置 */
if(tab->r[i].key<tab->r[mid].key) right=mid-1;
else left=mid+1;
} /*插入位置为 left*/
for(j=i-1;j>=left;j--) tab->r[j+1].key=tab->r[j].key; /*后移,空出插入位置 */
tab->r[left].key=tab->r[0].key; /*插入第 i个元素的副本 */
}
} /*算法 10.2 二分法插入排序算法 */
设待排序的 7记录的排序码为 {312,126,272，
226,28,165,123}，在前 6个记录已经排序的情况下，使用二分法插入排序算法插入第 7个记录的排序码
123的执行过程示意如图 10.3所示（见书本）。
二分法插入排序算法，在查找第 i个记录的插入位置时，每执行一次 while循环体，查找范围缩小一半，
和直接插入排序的比较次数对比，二分法插入的比较次数少于直接插入排序的最多比较次数，而一般要多于直接插入排序的最少比较次数。总体上讲，当 n较大时，二分法插入排序的比较次数远少于直接插入排序的平均比较次数，但二者所要进行的移动次数相等，
故二分法插入排序的时间复杂度也是 O(n2)，所需的附加存储空间为一个记录空间。
10.2.3 表插入排序二分法插入排序比较次数通常比直接插入排序的比较次数少，但移动次数相等。表插入排序将在不进行记录移动的情况下，利用存储结构有关信息的改变来达到排序的目的。
给每个记录附设一个所谓的指针域 link，它的类型为整型,表插入排序的思路,在插入第 i个记录 Ri时，
R1,R2,…,Ri-1已经通过各自的指针域 link按排序码不减的次序连接成一个（静态链）表，将记录 Ri的排序码 keyi与表中已经排好序的排序码从表头向右、或称向后依次比较，找到 Ri应插入的位置，将其插入在表中，使表中各记录的排序码仍然有序。
/* 表插入排序定义的头文件,文件名为,table2.h */
#define MAXSIZE 100 /*文件中记录个数的最大值 */
typedef int keytype; /*定义排序码类型为整数类型 */
typedef struct{
keytype key;
int link;
/*此处还可以定义记录中除排序码外的其它域 */
}recordtype; /*记录类型的定义 */
typedef struct{
recordtype r[MAXSIZE+1];
int length; /*待排序文件中记录的个数 */
}table2; /*待排序文件类型 */
表插入排序算法的示意如图 10.4所示（见书本）
对于将一个值为 x的记录，插入到一个已排序（不减）的单链表 head中，使新的单链表的结点值以不减序排列，读者容易给出解决此问题的算法。
表插入排序算法：初始时,r[0].Link用于存放表中第 1个记录的下标,r[0].Link的值为 1，排序结束时，
r[0].Link中存放的是所有排序码中值最小的对应记录的下标，其它的排序码通过各自的指针域 link按不减的次序连接成一个（静态链）表，最大的排序码对应的 link
为 0。
void tableinsertsort(table2 *tab)
{ int i,p,q;
tab->r[0].link=1;tab->r[1].link=0; /*第 1个元素为有序静态表 */
for(i=2;i<=tab->length;i++) /*依次插入从第 2个开始的所有元素 */
{
q=0;p=tab->r[0].link; /*p指向表中第 1个元素,q指向 p的前驱元素位置 */
while(p!=0&&tab->r[i].key>=tab->r[p].key) /*找插入位置 */
{
q=p; p=tab->r[p].link; /*继续查找 */
}
tab->r[i].link=p;tab->r[q].link=i; /*将第 i个元素插入 q和 p所指向的元素之间 */
}
}
算法 10.3 表插入排序算法
10.2.4 Shell插入排序
Shell插入排序：对有 n个记录进行排序，首先取 1
个整数 d<n，将这 n个记录分成 d组，所有位置相差为 d
的倍数的记录分在同一组，在每组中使用直接插入排序进行组内排序，然后缩小 d的值，重复进行分组和组内排序，一直到 d=1结束。
设待排序的 7记录的排序码为 {312,126,272，
226,28,165,123}，初始让 d=7/2=3，以后每次让
d缩小一半，其排序过程如图所示。
void shellinsertsort(table *tab)
{ int i,j,d;
d=tab->length/2;
while(d>=1)
{ for(i=d+1;i<=tab->length;i++) /*从第 d+1个元素开始,将所有元素有序插入相应分组中 */
{ tab->r[0].key=tab->r[i].key; /*保存第 i个元素 */
j=i-d; /*向前找插入位置 */
while(tab->r[0].key<tab->r[j].key&&j>0) /*找插入位置并后移 */
{ tab->r[j+d].key=tab->r[j].key; /*后移 */ j=j-d; /*继续向前查找 */ }
tab->r[j+d].key=tab->r[0].key; /*插入第 i个元素的副本 */
}
d=d/2;
}
}
算法 10.4 Shell插入排序算法
10.3 选择排序选择排序的基本思想是：每次从待排序的文件中选择出排序码最小的记录，将该记录放于已排序文件的最后一个位置，直到已排序文件记录个数等于初始待排序文件的记录个数为止。
10.3.1直接选择排序苜先从所有 n个待排序记录中选择排序码最小的记录，将该记录与第 1个记录交换，再从剩下的 n-l个记录中选出排序码最小的记录和第 2个记录交换。重复这样的操作直到剩下 2个记录时，再从中选出排序码最小的记录和第 n-1个记录交换。剩下的那 1个记录肯定是排序码最大的记录，这样排序即告完成。
void simpleselectsort(table *tab)
{ int i,j,k;
for(i=1;i<=tab->length-1;i++)
{ k=i; /*记下当前最小元素的位置 */
for(j=i+1;j<=tab->length;j++) /*向右查找更小的元素 */
if(tab->r[j].key<tab->r[k].key) k=j; /*修改当前最小元素的位置 */
if(k!=i) /*如果第 i次选到的最小元素位置 k不等于 i,则将第 k,i个元素交换 */
{ tab->r[0].key=tab->r[k].key; /*以第 0个元素作为中间单元进行交换 */
tab->r[k].key=tab->r[i].key;
tab->r[i].key=tab->r[0].key;
}
}
}
算法 10.5 直接选择排序算法直接选择排序算法执行过程如图 10.6所示 （见书本）
10.3.2 树型选择排序 （略）
10.3.3 堆排序为了既要保存中间比较结果，减少后面的比较次数，又不占用大量的附加存储空间，使排序算法具有较好的性能,Willioms和 Floyd在 1964年提出的称为堆排序的算法实现了这一想法。
堆是一个序列 {k1,k2,…,kn},它满足下面的条件：
ki≤k2i并且 ki≤k2i+1，当 i=1,2,…,?n/2?
采用顺序方式存储这个序列，就可以将这个序列的每一个元素 ki看成是一颗有 n个结点的完全二叉树的第 i个结点，其中 k1是该二叉树的根结点。
把堆对应的一维数组 (即该序列的顺序存储结构 )看作一棵完全二叉树的顺序存储，那么堆的特征可解释为，
完全二叉树中任一分支结点的值都小于或等于它的左、
右儿子结点的值。堆的元素序列中的第一个元素 k1，，
即对应的完全二叉树根结点的值是所有元素中值最小的。
堆排序方法就是利用这一点来选择最小元素。
一个序列和相应的完全二叉树,
这个序列不是一个堆。堆排序的关键问题是如何将待排序记录的排序码建成一个堆。
从图可以看到，在 n=9个元素组成的序列和它相对应的完全二叉树中，序号为 9,8,7,6,5的结点没有儿子，以它们为根的子树显然满足堆的条件。
因为在有 n=9个结点的完全二叉树中，第 4=n/2，
3,2,1个结点都有儿子，一般情况下，以它们为根结点的子树不会满足堆的条件，所以，要使该序列变换成一个堆，必须从这些结点处进行调整。
调整是从序号为 1的结点处开始直到 4(=n/2),
还是从序号为 4的结点开始，然后对序号为 3,2，
1的结点依次进行呢？
应该从第 4个结点开始，依次使以第 4个结点为根的子树变成堆，直到以第 1个结点为根的整个完全二叉树具有堆的性质，
则建堆完成。
建堆过程如下图所示
/* 筛选算法 */
void sift(table *tab,int k,int m)
{ int i,j,finished;
i=k;j=2*i;tab->r[0].key=tab->r[k].key;finished=0;
while((j<=m)&&(!finished))
{ if((j<m)&&(tab->r[j+1].key<tab->r[j].key)) j++;
if(tab->r[0].key<=tab->r[j].key) finished=1;
else { tab->r[i].key=tab->r[j].key; i=j;j=2*j; }
}
tab->r[i].key=tab->r[0].key;
}
算法 10.6 筛选算法通过筛选算法，可以将一个任意的排序码序列建成一个堆，堆的第 1个元素，即完全二叉树的根结点的值就是排序码中最小的。将选出的最小排序码从堆中删除，对剩余的部分重新建堆，可以继续选出其中的最小者，直到剩余 1个元素排序即告结束。
/* 堆排序算法 */
void heapsort(table*tab)
{ int i;
for(i=tab->length/2;i>=1;i--)sift(tab,i,tab->length);/*对所有元素建堆 */
for(i=tab->length;i>=2;i--)/*i表示当前堆的大小,即等待排序的元素的个数 */
{ tab->r[0].key=tab->r[i].key;
tab->r[i].key=tab->r[1].key;
tab->r[1].key=tab->r[0].key;
/*上述 3条语句为将堆中最小元素和最后一个元素交换 */
sift(tab,1,i-1);
}
}
算法 10.7 堆排序算法
10.4交换排序交换排序的基本思路：
对待排序记录两两进行排序码比较，若不满足排序顺序则交换这对记录，直到任何两个记录的排序码都满足排序要求为止。
10.4.1 冒泡排序冒泡排序第 1趟，对所有记录从左到右每相邻两个记录的排序码进行比较，如果这两个记录的排序码不符合排序要求，则进行交换，这样一趟做完，将排序码最大者放在最后一个位置；
第 2趟对剩下的 n-l个待排序记录重复上述过程，又将一个排序码放于最终位置，反复进行 n-l次，可将 n-l
个排序码对应的记录放至最终位置，剩下的即为排序码最小的记录，它在第 1的位置处。
如果在某一趟中，没有发生交换，则说明此时所有记录已经按排序要求排列完毕，排序结束。
void bubblesort(table *tab)
{ int i,j,done; i=1;done=1;
while(i<=tab->length&&done)
/*最多进行 tab->length次冒泡,如没有发生交换则结束 */
{ done=0;
for(j=1;j<=tab->length-i;j++)
if(tab->r[j+1].key<tab->r[j].key)
{ tab->r[0].key=tab->r[j].key; tab->r[j].key=tab->r[j+1].key;
tab->r[j+1].key=tab->r[0].key; done=1; }
i++;
}
} /*算法 10.8 冒泡排序算法 */
待排序的 9个记录的排序码序列为 {312,126,272，
226,8,165,123,12,28}，使用冒泡排序算法进行的排序过程如下图所示：
10.4.2 快速排序快速排序算法的基本思路是：
从 n个待排序的记录中任取一个记录 (不妨取第 1个记录 )，设法将该记录放置于排序后它最终应该放的位置，使它前面的记录排序码都不大于它的排序码，而后面的记录排序码都大于它的排序码，然后对前、后两部分待排序记录重复上述过程，可以将所有记录放于排序成功后的相应位置，排序即告完成。
设待排序的 7个记录的排序码序列为
{126,272,8,165，
123,12,28}，一次划分的过程如图所示
void quicksort(table *tab,int left,int right)
{ int i,j;
if(left<right)
{ i=left;j=right; tab->r[0].key=tab->r[i].key;
do { while(tab->r[j].key>tab->r[0].key&&i<j) j--;
if(i<j) { tab->r[i].key=tab->r[j].key;i++;}
while(tab->r[i].key<tab->r[0].key&&i<j) i++;
if(i<j) { tab->r[j].key=tab->r[i].key;j--;}
}while(i!=j);
tab->r[i].key=tab->r[0].key;
quicksort(tab,left,i-1); /*对标准值左边递归调用本函数 */
quicksort(tab,i+1,right); /*对标准值右边递归调用本函数 */
}
}
算法 10.9 快速排序算法归并排序的基本思路是：一个待排序记录构成的文件，可以看作是有多个有序子文件组成的，对有序子文件通过若干次使用归并的方法，得到一个有序文件。归并是指将两个（或多个）有序子表合并成一个有序表的过程。将两个有序子文件归并成一个有序文件的方法简单，只要将两个有序子文件的当前记录的排序码进行比较，较小者放入目标 —— 有序文件，重复这一过程直到两个有序子文件中的记录都放入同一个有序文件为止
10.5 归并排序归并排序需要调用两个操作，一个称之为 一次归并,另一个称之为 一趟归并 。一次归并是指将一个数组中两个相邻的有序数组段归并为一个有序数组段，其结果存储于另一个数组中的操作。
void merge(table *tabs,table *tabg,int u,int m,int v)
{
int i,j,k,t;
i=u; /*i从第 1段的起始位置开始,一直到最终位置 m*/
j=m+1; /*j从第 2段的起始位置开始,一直到最终位置 v*/
k=u; /*k表示的是目标 tabg的起始位置 */
while(i<=m&&j<=v)
{ if(tabs->r[i].key<=tabs->r[j].key) { tabg->r[k].key=tabs->r[i].key; i++; }
else { tabg->r[k].key=tabs->r[j].key; j++; }
k++;
}
if(i<=m) for(t=i;t<=m;t++) tabg->r[k+t-i].key=tabs->r[t].key;
else for(t=j;t<=v;t++) tabg->r[k+t-j].key=tabs->r[t].key;
}
算法 10.10一次归并算法一趟归并的图示,
void mergepass(table *tabs,table*tabg,int len)
{int i,j,n;
n=tabg->length=tabs->length;
i=1;
while(i<=n-2*len+1)
{ merge(tabs,tabg,i,i+len-1,i+2*len-1);/*一次归并 */
i=i+2*len; /*置下一个一次归并的起始位置 */
}
if(i+len-1<n)
merge(tabs,tabg,i,i+len-1,n);
else /*对剩下的 1个长不超过 len,终点为 n的有序段进行处理 */
for(j=i;j<=n;j++)tabg->r[j].key=tabs->r[j].key;
}/* 本算法结束后 tabg中的有序段的长度为 2*len */
算法 10.11一趟归并算法
void mergesort(table*tab)
{
int len;
tabletemp; /*中间变量 */
len=1; /*初始时有序段的长度为 1*/
while(len<tab->length)/*有序段的长度小于待排序元素的个数,继续归并 */
{
mergepass(tab,&temp,len);/*一趟归并,结果在 temp中 */
len=2*len; /*有序段的长度翻倍 */
mergepass(&temp,tab,len);/*一趟归并,结果在 tab中 */
len=2*len; /*有序段的长度翻倍 */
}
}
算法 10.12归并排序算法
10.6基数排序基数排序（又称分配排序）是一种和前述各种方法都不相同的排序方法。前而介绍的排序方法是通过对排序码的比较以及记录的移动来实现排序的，而基数排序没有作这两种操作，它不对排序码进行比较，
是借助于多排序码排序的思想进行单排序码排序的方法。
10.6.1多排序码的排序多排序码排序的思想：一副游戏扑克牌中除大,小王之外的 52张牌面的次序关系如下：
2<?3<…<?A<?2<?3<…<?A<?2<?3<…<?A<?
2<?3<…<?A
每一张牌有两个“排序码”：花色（梅花 <方块 <
红心 <黑桃）和面值（ 2<3<…<A ），且花色的地位高于面值，即面值相等的两张牌，以花色大的为大。在比较两张牌的牌面大小时，先比较花色，若花色相同，
则再比较面值，通常采用下面方法将扑克牌进行上述次序的排序：先将 52张牌以花色分成为四堆，再对每一堆同花色的牌按面值大小整理有序。实际上，还可以用下面的方法对扑克牌排序：首先将 52扑克牌按面值分成 13堆，将这 13堆牌自小至大叠在一起，然后再重新近不同花色分成 4堆，最后将这 4堆牌近自小至大的次序合在一起即可。这就是一个具有 2个排序码的排序过程，其中分成若干堆的过程称为分配，从若干堆中自小到大叠在一起的过程称为收集。扑克牌排序使用了 2次分配和 2次收集操作。
10.6.2 静态链式基数排序将扑克牌排序的第二种方法推广。可以得到对多个排序码排序算法。即若每个记录有 b个排序码，则可采用扑克牌排序相同的思想，从最低位排序码 kb开始进行排序，再对高一位的排序码 kb-1进行排序，重复这一过程，直到对最高位 k1进行排序后便得到一个有序序列。
经常碰到的整数序列，可以把整数的个位数看作是最低位排序码，十位数是次低位排序码，依次类推，
若待排序整数序列中最大整数序列中最大整数的位数为 b，则整数序列的排序问题可用 b个排序码的基数排序方法实现。在对某一位进行排序时，并不要进行比较，而是通过分配与收集来实现。
静态链式基数排序的思想是：
先用静态链表存储待排序文件中的 n个记录，即建立一个静态单链表，表中每一个结点对应于一个记录，
并用表头指针指向该静态单链表的表头结点。第一趟分配对最低位排序码（个位数）进行，修改静态链表的指针域，将 n个结点分配到序号分别为 0~9的 10个链式队列中，其中每个队列中结点对应记录的个位数相同，用
f[i] 和 e[ i ]分别作为第 i个队列的队首和队尾指针；第一趟收集过程将这个 10个队列中非空的队列依次合并在一起产生一个新的静态单链表，对这个新的静态单链表按十位数进行分配和收集，然后再依次对百位数,…,最高位数反复进行这样分配和收集操作，排序即可结束。
设待排序的 9个记录的排序码序列为 {312,126，
272,226,8,165,123,12,28}，使用静态链式基数排序算法进行的排序过程如下图 10.14所示。
10.1 排序的基本概念假设一个文件是由 n个记录 R1,R2,…,Rn组成，
所谓排序就是以记录中某个 (或几个 )字段值不减 (或不增 )的次序将这 n个记录重新排列，称该字段为排序码。能唯一标识一个记录的字段称为关键码，关键码可以作为排序码，但排序码不一定要是关键码。
按排序过程中使用到的存储介质来分，可以将排序分成 两大类,内排序和外排序 。
内排序 是指在排序过程中所有数据均放在内存中处理，不需要使用外存的排序方法。而对于数据量很大的文件，在内存不足的情况下，则还需要使用外存，
这种排序方法称为 外排序 。
排序码相同的记录，若经过排序后，这些记录仍保持原来的相对次序不变，称这个排序算法是 稳定的 。否则，称为 不稳定的排序算法 。
评价排序算法优劣的标准,
首先考虑算法执行所需的时间，这主要是用执行过程中的比较次数和移动次数来度量；
其次考虑算法执行所需要的附加空间。
当然，保证算法的正确性是不言而喻的，可读性等也是要考虑的因素。
排序算法如未作特别的说明，使用的有关定义如下,
/*常见排序算法的头文件,文件名 table.h*/
#define MAXSIZE 100 /*文件中记录个数的最大值 */
typedef int keytype; /*定义排序码类型为整数类型 */
typedef struct{
keytype key;
/*此处还可以定义记录中除排序码外的其它域 */
}recordtype; /*记录类型的定义 */
typedef struct{
recordtype r[MAXSIZE+1];
int length; /*待排序文件中记录的个数 */
}table; /*待排序文件类型 */
为了方便,r[0]一般不用于存放排序码，在一些排序算法中它可以用来作为中间单元存放临时数据。 length
域是待排序的记录个数，它必须不大于 MAXSIZE，这样，
第 1~length个记录的排序码分别存于
r[1].key~r[length].key中
10.2 插入排序插入排序的基本方法是,
将待排序文件中的记录,逐个地按其排序码值的大小插入到目前已经排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。
10.2.1 直接插入排序直接插入排序算法的思路是,初始可认为文件中的第 1个记录己排好序，然后将第 2个到第 n个记录依次插入已排序的记录组成的文件中。在对第 i个记录 Ri进行插入时,R1,R2,…,Ri-1已排序，将记录 Ri的排序码
keyi与已经排好序的排序码从右向左依次比较，找到 Ri
应插入的位置，将该位置以后直到 Ri-1各记录顺序后移，
空出该位置让 Ri插入。
一组记录的排序码分别为,
312,126,272,226,28,165,123
初始时将第 1个排序码作为已经排好序的,把排好序的数据记录放入中括号 []中,表示有序的文件,剩下的在中括号外,如下所示：
[312],126,272,226,28,165,123
设前 3个记录的排序码已重新排列有序,构成一个含有 3个记录的有序文件,
[126,272,312],226,28,165,123
现在要将第 4个排序码 226插入 ！
[126,272,312],226,28,165,123
现在要将第 4个排序码 226插入 ！
将待插入的排序码 226和已经有序的最后一个排序码 312比较，因为待插入的排序码 226小于 312，所以 226肯定要置于 312的前面，至于是否就是置于 312
的前一个位置，此时还不能确定，需要继续向左比较；
将所有大于待插入排序码 226的那两个排序码
312和 272依次后移一个位置，在空出的位置插入待排序的排序码 226，得一含有 4个记录的有序文件：
[126,226,272,312],28,165,123
需要注意的是，当待插入排序码小于所有已排序的排序码时，如在插入第 5个值 28时：
[126,226,272,312],28,165,123
算法设计的时候如处理？
方法之一：设置“哨兵”
void insertsort(table *tab)
{
int i,j;
for(i=2;i<=tab->length;i++)/*依次插入从第 2个开始的所有元素 */
{ j=i-1;
tab->r[0].key=tab->r[i].key;/*设置哨兵,准备找插入位置 */
while(tab->r[0].key<tab->r[j].key) /*找插入位置并后移 */
{ tab->r[j+1].key=tab->r[j].key; /*后移 */
j=j-1; /*继续向前 （ 左 ） 查找 */
}
tab->r[j+1].key=tab->r[0].key; /*插入第 i个元素的副本,即前面设置的哨兵 */
}
}
算法 10.1 直接插入排序算法设待排序的 7记录的排序码为 {312,126,272,226,28,165，
123},直接插入排序算法的执行过程如图 10.2所示 。
哨兵 排序码
[] 312,126,272,226,28,165,123
初始 （） [312],126,272,226,28,165,123
i=2,（ 126） [126,312],272,226,28,165,123
i=3,（ 272） [126,272,312],226,28,165,123
i=4,（ 226） [126,226,272,312],28,165,123
i=5,（ 28） [28,126,226,272,312],165,123
i=6,（ 165） [28,126,165,226,272,312],123
i=7,（ 123） [28,123,126,165,226,272,312]
图 10.2 直接插入排序算法执行过程示意图直接插入排序算法执行时间的分析：
最好的情况,
即初始排序码开始就是有序的情况下，因为当插入第 i个排序码时，该算法内循环 while只进行一次条件判断而不执行循环体，外循环共执行 n-1次，其循环体内不含内循环每次循环要进行 2次移动操作，所以在最好情况下，直接插入排序算法的比较次数为 (n-1)次，
移动次数为 2*(n-1)次。
最坏情况,
即初始排序码开始是逆序的情况下，因为当插入第 i个排序码时，该算法内循环 while要执行 i次条件判断，循环体要执行 i-l次，每次要移动 1个记录，外循环共执行 n-1次，其循环体内不含内循环每次循环要进行 2次移动操作，所以在最坏情况下，比较次数为
(1+2+…+n)*(n -1)，移动次数为
(1+2+2+2+…+n+2)*(n -1)。假设待排序文件中的记录以各种排列出现的概率相同，因为当插入第 i个排序码时，该算法内循环 while平均约要执行 i/2次条件判断，
循环体要执行（ i-l） /2次，外循环共执行 n-1次，所以平均比较次数约为 (2+3+…+n)/2*(n -1)，平均移动次数为 (n-1)*(2+1+3+1+…+n+1)/2,也即直接插入排序算法的时间复杂度为 O(n2)。
10.2.2 二分法插入排序二分法插入排序的思想：
根据插入排序的基本思想，在找第 i个记录的插入位置时，前 i-l个记录已排序，将第 i个记录的排序码
key[i]和已排序的前 i-1个的中间位置记录的排序码进行比较，如果 key[i]小于中间位置记录排序码，则可以在前半部继续使用二分法查找，否则在后半部继续使用二分法查找，直到查找范围为空，即可确定 key[i]的插入位置。
void binarysort(table *tab)
{ int i,j,left,right,mid;
for(i=2;i<=tab->length;i++) /*依次插入从第 2个开始的所有元素 */
{ tab->r[0].key=tab->r[i].key; /*保存待插入的元素 */
left=1;right=i-1; /*设置查找范围的左,右位置值 */
while(left<=right) /*查找第 i个元素的插入位置 */
{ mid=(left+right)/2; /*取中点位置 */
if(tab->r[i].key<tab->r[mid].key) right=mid-1;
else left=mid+1;
} /*插入位置为 left*/
for(j=i-1;j>=left;j--) tab->r[j+1].key=tab->r[j].key; /*后移,空出插入位置 */
tab->r[left].key=tab->r[0].key; /*插入第 i个元素的副本 */
}
} /*算法 10.2 二分法插入排序算法 */
设待排序的 7记录的排序码为 {312,126,272，
226,28,165,123}，在前 6个记录已经排序的情况下，使用二分法插入排序算法插入第 7个记录的排序码
123的执行过程示意如图 10.3所示（见书本）。
二分法插入排序算法，在查找第 i个记录的插入位置时，每执行一次 while循环体，查找范围缩小一半，
和直接插入排序的比较次数对比，二分法插入的比较次数少于直接插入排序的最多比较次数，而一般要多于直接插入排序的最少比较次数。总体上讲，当 n较大时，二分法插入排序的比较次数远少于直接插入排序的平均比较次数，但二者所要进行的移动次数相等，
故二分法插入排序的时间复杂度也是 O(n2)，所需的附加存储空间为一个记录空间。
10.2.3 表插入排序二分法插入排序比较次数通常比直接插入排序的比较次数少，但移动次数相等。表插入排序将在不进行记录移动的情况下，利用存储结构有关信息的改变来达到排序的目的。
给每个记录附设一个所谓的指针域 link，它的类型为整型,表插入排序的思路,在插入第 i个记录 Ri时，
R1,R2,…,Ri-1已经通过各自的指针域 link按排序码不减的次序连接成一个（静态链）表，将记录 Ri的排序码 keyi与表中已经排好序的排序码从表头向右、或称向后依次比较，找到 Ri应插入的位置，将其插入在表中，使表中各记录的排序码仍然有序。
/* 表插入排序定义的头文件,文件名为,table2.h */
#define MAXSIZE 100 /*文件中记录个数的最大值 */
typedef int keytype; /*定义排序码类型为整数类型 */
typedef struct{
keytype key;
int link;
/*此处还可以定义记录中除排序码外的其它域 */
}recordtype; /*记录类型的定义 */
typedef struct{
recordtype r[MAXSIZE+1];
int length; /*待排序文件中记录的个数 */
}table2; /*待排序文件类型 */
表插入排序算法的示意如图 10.4所示（见书本）
对于将一个值为 x的记录，插入到一个已排序（不减）的单链表 head中，使新的单链表的结点值以不减序排列，读者容易给出解决此问题的算法。
表插入排序算法：初始时,r[0].Link用于存放表中第 1个记录的下标,r[0].Link的值为 1，排序结束时，
r[0].Link中存放的是所有排序码中值最小的对应记录的下标，其它的排序码通过各自的指针域 link按不减的次序连接成一个（静态链）表，最大的排序码对应的 link
为 0。
void tableinsertsort(table2 *tab)
{ int i,p,q;
tab->r[0].link=1;tab->r[1].link=0; /*第 1个元素为有序静态表 */
for(i=2;i<=tab->length;i++) /*依次插入从第 2个开始的所有元素 */
{
q=0;p=tab->r[0].link; /*p指向表中第 1个元素,q指向 p的前驱元素位置 */
while(p!=0&&tab->r[i].key>=tab->r[p].key) /*找插入位置 */
{
q=p; p=tab->r[p].link; /*继续查找 */
}
tab->r[i].link=p;tab->r[q].link=i; /*将第 i个元素插入 q和 p所指向的元素之间 */
}
}
算法 10.3 表插入排序算法
10.2.4 Shell插入排序
Shell插入排序：对有 n个记录进行排序，首先取 1
个整数 d<n，将这 n个记录分成 d组，所有位置相差为 d
的倍数的记录分在同一组，在每组中使用直接插入排序进行组内排序，然后缩小 d的值，重复进行分组和组内排序，一直到 d=1结束。
设待排序的 7记录的排序码为 {312,126,272，
226,28,165,123}，初始让 d=7/2=3，以后每次让
d缩小一半，其排序过程如图所示。
void shellinsertsort(table *tab)
{ int i,j,d;
d=tab->length/2;
while(d>=1)
{ for(i=d+1;i<=tab->length;i++) /*从第 d+1个元素开始,将所有元素有序插入相应分组中 */
{ tab->r[0].key=tab->r[i].key; /*保存第 i个元素 */
j=i-d; /*向前找插入位置 */
while(tab->r[0].key<tab->r[j].key&&j>0) /*找插入位置并后移 */
{ tab->r[j+d].key=tab->r[j].key; /*后移 */ j=j-d; /*继续向前查找 */ }
tab->r[j+d].key=tab->r[0].key; /*插入第 i个元素的副本 */
}
d=d/2;
}
}
算法 10.4 Shell插入排序算法
10.3 选择排序选择排序的基本思想是：每次从待排序的文件中选择出排序码最小的记录，将该记录放于已排序文件的最后一个位置，直到已排序文件记录个数等于初始待排序文件的记录个数为止。
10.3.1直接选择排序苜先从所有 n个待排序记录中选择排序码最小的记录，将该记录与第 1个记录交换，再从剩下的 n-l个记录中选出排序码最小的记录和第 2个记录交换。重复这样的操作直到剩下 2个记录时，再从中选出排序码最小的记录和第 n-1个记录交换。剩下的那 1个记录肯定是排序码最大的记录，这样排序即告完成。
void simpleselectsort(table *tab)
{ int i,j,k;
for(i=1;i<=tab->length-1;i++)
{ k=i; /*记下当前最小元素的位置 */
for(j=i+1;j<=tab->length;j++) /*向右查找更小的元素 */
if(tab->r[j].key<tab->r[k].key) k=j; /*修改当前最小元素的位置 */
if(k!=i) /*如果第 i次选到的最小元素位置 k不等于 i,则将第 k,i个元素交换 */
{ tab->r[0].key=tab->r[k].key; /*以第 0个元素作为中间单元进行交换 */
tab->r[k].key=tab->r[i].key;
tab->r[i].key=tab->r[0].key;
}
}
}
算法 10.5 直接选择排序算法直接选择排序算法执行过程如图 10.6所示 （见书本）
10.3.2 树型选择排序 （略）
10.3.3 堆排序为了既要保存中间比较结果，减少后面的比较次数，又不占用大量的附加存储空间，使排序算法具有较好的性能,Willioms和 Floyd在 1964年提出的称为堆排序的算法实现了这一想法。
堆是一个序列 {k1,k2,…,kn},它满足下面的条件：
ki≤k2i并且 ki≤k2i+1，当 i=1,2,…,?n/2?
采用顺序方式存储这个序列，就可以将这个序列的每一个元素 ki看成是一颗有 n个结点的完全二叉树的第 i个结点，其中 k1是该二叉树的根结点。
把堆对应的一维数组 (即该序列的顺序存储结构 )看作一棵完全二叉树的顺序存储，那么堆的特征可解释为，
完全二叉树中任一分支结点的值都小于或等于它的左、
右儿子结点的值。堆的元素序列中的第一个元素 k1，，
即对应的完全二叉树根结点的值是所有元素中值最小的。
堆排序方法就是利用这一点来选择最小元素。
一个序列和相应的完全二叉树,
这个序列不是一个堆。堆排序的关键问题是如何将待排序记录的排序码建成一个堆。
从图可以看到，在 n=9个元素组成的序列和它相对应的完全二叉树中，序号为 9,8,7,6,5的结点没有儿子，以它们为根的子树显然满足堆的条件。
因为在有 n=9个结点的完全二叉树中，第 4=n/2，
3,2,1个结点都有儿子，一般情况下，以它们为根结点的子树不会满足堆的条件，所以，要使该序列变换成一个堆，必须从这些结点处进行调整。
调整是从序号为 1的结点处开始直到 4(=n/2),
还是从序号为 4的结点开始，然后对序号为 3,2，
1的结点依次进行呢？
应该从第 4个结点开始，依次使以第 4个结点为根的子树变成堆，直到以第 1个结点为根的整个完全二叉树具有堆的性质，
则建堆完成。
建堆过程如下图所示
/* 筛选算法 */
void sift(table *tab,int k,int m)
{ int i,j,finished;
i=k;j=2*i;tab->r[0].key=tab->r[k].key;finished=0;
while((j<=m)&&(!finished))
{ if((j<m)&&(tab->r[j+1].key<tab->r[j].key)) j++;
if(tab->r[0].key<=tab->r[j].key) finished=1;
else { tab->r[i].key=tab->r[j].key; i=j;j=2*j; }
}
tab->r[i].key=tab->r[0].key;
}
算法 10.6 筛选算法通过筛选算法，可以将一个任意的排序码序列建成一个堆，堆的第 1个元素，即完全二叉树的根结点的值就是排序码中最小的。将选出的最小排序码从堆中删除，对剩余的部分重新建堆，可以继续选出其中的最小者，直到剩余 1个元素排序即告结束。
/* 堆排序算法 */
void heapsort(table*tab)
{ int i;
for(i=tab->length/2;i>=1;i--)sift(tab,i,tab->length);/*对所有元素建堆 */
for(i=tab->length;i>=2;i--)/*i表示当前堆的大小,即等待排序的元素的个数 */
{ tab->r[0].key=tab->r[i].key;
tab->r[i].key=tab->r[1].key;
tab->r[1].key=tab->r[0].key;
/*上述 3条语句为将堆中最小元素和最后一个元素交换 */
sift(tab,1,i-1);
}
}
算法 10.7 堆排序算法
10.4交换排序交换排序的基本思路：
对待排序记录两两进行排序码比较，若不满足排序顺序则交换这对记录，直到任何两个记录的排序码都满足排序要求为止。
10.4.1 冒泡排序冒泡排序第 1趟，对所有记录从左到右每相邻两个记录的排序码进行比较，如果这两个记录的排序码不符合排序要求，则进行交换，这样一趟做完，将排序码最大者放在最后一个位置；
第 2趟对剩下的 n-l个待排序记录重复上述过程，又将一个排序码放于最终位置，反复进行 n-l次，可将 n-l
个排序码对应的记录放至最终位置，剩下的即为排序码最小的记录，它在第 1的位置处。
如果在某一趟中，没有发生交换，则说明此时所有记录已经按排序要求排列完毕，排序结束。
void bubblesort(table *tab)
{ int i,j,done; i=1;done=1;
while(i<=tab->length&&done)
/*最多进行 tab->length次冒泡,如没有发生交换则结束 */
{ done=0;
for(j=1;j<=tab->length-i;j++)
if(tab->r[j+1].key<tab->r[j].key)
{ tab->r[0].key=tab->r[j].key; tab->r[j].key=tab->r[j+1].key;
tab->r[j+1].key=tab->r[0].key; done=1; }
i++;
}
} /*算法 10.8 冒泡排序算法 */
待排序的 9个记录的排序码序列为 {312,126,272，
226,8,165,123,12,28}，使用冒泡排序算法进行的排序过程如下图所示：
10.4.2 快速排序快速排序算法的基本思路是：
从 n个待排序的记录中任取一个记录 (不妨取第 1个记录 )，设法将该记录放置于排序后它最终应该放的位置，使它前面的记录排序码都不大于它的排序码，而后面的记录排序码都大于它的排序码，然后对前、后两部分待排序记录重复上述过程，可以将所有记录放于排序成功后的相应位置，排序即告完成。
设待排序的 7个记录的排序码序列为
{126,272,8,165，
123,12,28}，一次划分的过程如图所示
void quicksort(table *tab,int left,int right)
{ int i,j;
if(left<right)
{ i=left;j=right; tab->r[0].key=tab->r[i].key;
do { while(tab->r[j].key>tab->r[0].key&&i<j) j--;
if(i<j) { tab->r[i].key=tab->r[j].key;i++;}
while(tab->r[i].key<tab->r[0].key&&i<j) i++;
if(i<j) { tab->r[j].key=tab->r[i].key;j--;}
}while(i!=j);
tab->r[i].key=tab->r[0].key;
quicksort(tab,left,i-1); /*对标准值左边递归调用本函数 */
quicksort(tab,i+1,right); /*对标准值右边递归调用本函数 */
}
}
算法 10.9 快速排序算法归并排序的基本思路是：一个待排序记录构成的文件，可以看作是有多个有序子文件组成的，对有序子文件通过若干次使用归并的方法，得到一个有序文件。归并是指将两个（或多个）有序子表合并成一个有序表的过程。将两个有序子文件归并成一个有序文件的方法简单，只要将两个有序子文件的当前记录的排序码进行比较，较小者放入目标 —— 有序文件，重复这一过程直到两个有序子文件中的记录都放入同一个有序文件为止
10.5 归并排序归并排序需要调用两个操作，一个称之为 一次归并,另一个称之为 一趟归并 。一次归并是指将一个数组中两个相邻的有序数组段归并为一个有序数组段，其结果存储于另一个数组中的操作。
void merge(table *tabs,table *tabg,int u,int m,int v)
{
int i,j,k,t;
i=u; /*i从第 1段的起始位置开始,一直到最终位置 m*/
j=m+1; /*j从第 2段的起始位置开始,一直到最终位置 v*/
k=u; /*k表示的是目标 tabg的起始位置 */
while(i<=m&&j<=v)
{ if(tabs->r[i].key<=tabs->r[j].key) { tabg->r[k].key=tabs->r[i].key; i++; }
else { tabg->r[k].key=tabs->r[j].key; j++; }
k++;
}
if(i<=m) for(t=i;t<=m;t++) tabg->r[k+t-i].key=tabs->r[t].key;
else for(t=j;t<=v;t++) tabg->r[k+t-j].key=tabs->r[t].key;
}
算法 10.10一次归并算法一趟归并的图示,
void mergepass(table *tabs,table*tabg,int len)
{int i,j,n;
n=tabg->length=tabs->length;
i=1;
while(i<=n-2*len+1)
{ merge(tabs,tabg,i,i+len-1,i+2*len-1);/*一次归并 */
i=i+2*len; /*置下一个一次归并的起始位置 */
}
if(i+len-1<n)
merge(tabs,tabg,i,i+len-1,n);
else /*对剩下的 1个长不超过 len,终点为 n的有序段进行处理 */
for(j=i;j<=n;j++)tabg->r[j].key=tabs->r[j].key;
}/* 本算法结束后 tabg中的有序段的长度为 2*len */
算法 10.11一趟归并算法
void mergesort(table*tab)
{
int len;
tabletemp; /*中间变量 */
len=1; /*初始时有序段的长度为 1*/
while(len<tab->length)/*有序段的长度小于待排序元素的个数,继续归并 */
{
mergepass(tab,&temp,len);/*一趟归并,结果在 temp中 */
len=2*len; /*有序段的长度翻倍 */
mergepass(&temp,tab,len);/*一趟归并,结果在 tab中 */
len=2*len; /*有序段的长度翻倍 */
}
}
算法 10.12归并排序算法
10.6基数排序基数排序（又称分配排序）是一种和前述各种方法都不相同的排序方法。前而介绍的排序方法是通过对排序码的比较以及记录的移动来实现排序的，而基数排序没有作这两种操作，它不对排序码进行比较，
是借助于多排序码排序的思想进行单排序码排序的方法。
10.6.1多排序码的排序多排序码排序的思想：一副游戏扑克牌中除大,小王之外的 52张牌面的次序关系如下：
2<?3<…<?A<?2<?3<…<?A<?2<?3<…<?A<?
2<?3<…<?A
每一张牌有两个“排序码”：花色（梅花 <方块 <
红心 <黑桃）和面值（ 2<3<…<A ），且花色的地位高于面值，即面值相等的两张牌，以花色大的为大。在比较两张牌的牌面大小时，先比较花色，若花色相同，
则再比较面值，通常采用下面方法将扑克牌进行上述次序的排序：先将 52张牌以花色分成为四堆，再对每一堆同花色的牌按面值大小整理有序。实际上，还可以用下面的方法对扑克牌排序：首先将 52扑克牌按面值分成 13堆，将这 13堆牌自小至大叠在一起，然后再重新近不同花色分成 4堆，最后将这 4堆牌近自小至大的次序合在一起即可。这就是一个具有 2个排序码的排序过程，其中分成若干堆的过程称为分配，从若干堆中自小到大叠在一起的过程称为收集。扑克牌排序使用了 2次分配和 2次收集操作。
10.6.2 静态链式基数排序将扑克牌排序的第二种方法推广。可以得到对多个排序码排序算法。即若每个记录有 b个排序码，则可采用扑克牌排序相同的思想，从最低位排序码 kb开始进行排序，再对高一位的排序码 kb-1进行排序，重复这一过程，直到对最高位 k1进行排序后便得到一个有序序列。
经常碰到的整数序列，可以把整数的个位数看作是最低位排序码，十位数是次低位排序码，依次类推，
若待排序整数序列中最大整数序列中最大整数的位数为 b，则整数序列的排序问题可用 b个排序码的基数排序方法实现。在对某一位进行排序时，并不要进行比较，而是通过分配与收集来实现。
静态链式基数排序的思想是：
先用静态链表存储待排序文件中的 n个记录，即建立一个静态单链表，表中每一个结点对应于一个记录，
并用表头指针指向该静态单链表的表头结点。第一趟分配对最低位排序码（个位数）进行，修改静态链表的指针域，将 n个结点分配到序号分别为 0~9的 10个链式队列中，其中每个队列中结点对应记录的个位数相同，用
f[i] 和 e[ i ]分别作为第 i个队列的队首和队尾指针；第一趟收集过程将这个 10个队列中非空的队列依次合并在一起产生一个新的静态单链表，对这个新的静态单链表按十位数进行分配和收集，然后再依次对百位数,…,最高位数反复进行这样分配和收集操作，排序即可结束。
设待排序的 9个记录的排序码序列为 {312,126，
272,226,8,165,123,12,28}，使用静态链式基数排序算法进行的排序过程如下图 10.14所示。
