后面根据各种排序算法，给出了C语言的实现，大家在复习的时候可以做下参考。

　　u 选择排序

　　void ss_sort(int e[], int n)

　　{ int i, j, k, t;

　　for(i=0; i< n-1; i++) {

　　for(k=i, j=i+1; j

　　if(e[k]>e[j]) k=j;

　　if(k!=i) {

　　t=e[i]; e[i]=e[k]; e[k]=t;

　　}

　　}

　　}

　　u 直接插入排序

　　void si_sort(int e[], int n)

　　{ int i, j, t;

　　for(i=0; i< n; i++) {

　　for(t=e[i], j=i-1; j>=0&&t

　　e[j+1]=e[j];

　　e[j+1]=t;

　　}

　　}

　　u 冒泡排序

　　void sb_sort(int e[], int n)

　　{ int j, p, h, t;

　　for(h=n-1; h>0; h=p) {

　　for(p=j=0; j

　　if(e[j]>e[j+1]) {

　　t=e[j]; e[j]=e[j+1]; e[j+1]=t;

　　p=j;

　　}

　　}

　　}

　　u 希尔排序

　　void shell(int e[], int n)

　　{ int j, k, h, y;

　　for(h=n/2; h>0; h=h/2)

　　for(j=h; j

　　y=e[j];

　　for(k=j-h; k>0&&y

　　e[k+h]=e[k];

　　e[k+h]=y;

　　}

　　}

　　u 堆排序

　　void sift(e, n, s)

　　int e[];

　　int n;

　　int s;

　　{ int t, k, j;

　　t=e[s];

　　k=s; j=2*k+1;

　　while(j

　　if(j

　　j++;

　　if(t

　　e[k]=e[j];

　　k=j;

　　j=2*k+1;

　　}else break;

　　}

　　e[k]=t;

　　}

　　void heapsorp (int e[], int n)

　　{ int i, k, t;

　　for(i=n/2-1; i>=0; i--)

　　sift(e, n, i);

　　for(k=n-1; k>=1; k--) {

　　t=e[0]; e[0]=e[k]; e[k]=t;

　　sift(e, k, 0);

　　}

　　}

　　u 快速排序

　　void r_quick(int e[], int low, int high)

　　{ int i, j, t;

　　if(low

　　i=low; j=high; t=e[low];

　　while(i

　　while (it) j--;

　　if(i

　　while (i

　　if(I

　　}

　　e[i]=t;

　　r_quick(e,low,i-1);

　　r_quick(w,i+1,high);

　　}

　　}

　　另外，外排序是对大型文件的排序，待排序的记录存储在外存中，在排序过程中，内存只存储文件的一部分记录，整个排序过程需进行多次的内外存间的交换。

　　直接插入排序算法分析：

　　设有n个记录，存放在数组r中，重新安排记录在数组中的存放顺序，使得按关键码有序。即r[1].key≤r[2].key≤……≤r[n].key

　　先来看看向有序表中插入一个记录的方法：

　　设1

　　【算法10.1】

　　① r[0]=r[j]; //r[j]送r[0]中，使r[j]为待插入记录空位

　　i=j-1; //从第i个记录向前测试插入位置，用r[0]为辅助单元， 可免去测试i<1。

　　② 若r[0].key≥r[i].key，转④。 //插入位置确定

　　③ 若r[0].key < r[i].key时，

　　r[i+1]=r[i];i=i-1;转②。 //调整待插入位置

　　④ r[i+1]=r[0];结束。 //存放待插入记录

　　直接插入排序方法：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。

　　【算法10.2】

　　void InsertSort(S_TBL &p)

　　{ for(i=2;i<=p->length;i++)

　　if(p->elem[i].key < p->elem[i-1].key) /*小于时，需将elem[i]插入有序表*/

　　{ p->elem[0].key=p->elem[i].key; /*为统一算法设置监测*/

　　for(j=i-1;p->elem[0].key < p->elem[j].key;j--)

　　p->elem[j+1].key=p->elem[j].key; /*记录后移*/

　　p->elem[j+1].key=p->elem[0].key; /*插入到正确位置*/

　　}

　　}

　　【效率分析】

　　空间效率：仅用了一个辅助单元。

　　时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。

　　最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较2次移动。

　　总比较次数=n-1次

　　总移动次数=2(n-1)次

　　最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。

　　平均情况下：即第j趟操作，插入记录大约同前面的j/2个记录进行关键码比较，移动记录的次数为j/2+2次。

　　由此，直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法。

　　折半插入排序算法分析：

　　直接插入排序的基本操作是向有序表中插入一个记录，插入位置的确定通过对有序表中记录按关键码逐个比较得到的。平均情况下总比较次数约为n2/4。既然是在有序表中确定插入位置，可以不断二分有序表来确定插入位置，即一次比较，通过待插入记录与有序表居中的记录按关键码比较，将有序表一分为二，下次比较在其中一个有序子表中进行，将子表又一分为二。这样继续下去，直到要比较的子表中只有一个记录时，比较一次便确定了插入位置。

　　二分判定有序表插入位置方法：

　　① low=1;high=j-1;r[0]=r[j]; // 有序表长度为j-1，第j个记录为待插入记录

　　//设置有序表区间，待插入记录送辅助单元

　　② 若low>high，得到插入位置，转⑤

　　③ low≤high，m=(low+high)/2; // 取表的中点，并将表一分为二，确定待插入区间*/

　　④ 若r[0].key

　　否则，low=m+1; // 插入位置在高半区

　　转②

　　⑤ high+1即为待插入位置，从j-1到high+1的记录，逐个后移，r[high+1]=r[0];放置待插入记录。

　　【算法10.3】

　　void InsertSort(S_TBL *s)

　　{ /* 对顺序表s作折半插入排序 */

　　for(i=2;i<=s->length;i++)

　　{ s->elem[0]=s->elem[i]; /* 保存待插入元素 */

　　low=i;high=i-1; /* 设置初始区间 */

　　while(low<=high) /* 该循环语句完成确定插入位置 */

　　{ mid=(low+high)/2;

　　if(s->elem[0].key>s->elem[mid].key)

　　low=mid+1; /* 插入位置在高半区中 */

　　else high=mid-1; /* 插入位置在低半区中 */

　　}/* while */

　　for(j=i-1;j>=high+1;j--) /* high+1为插入位置 */

　　s->elem[j+1]=s->elem[j]; /* 后移元素，留出插入空位 */

　　s->elem[high+1]=s->elem[0]; /* 将元素插入 */

　　}/* for */

　　}/* InsertSort */

　　【时间效率】

　　确定插入位置所进行的折半查找，关键码的比较次数至多为 ，次，移动记录的次数和直接插入排序相同，故时间复杂度仍为O(n2)。是一个稳定的排序方法。

　　表插入排序算法分析：

　　直接插入排序、折半插入排序均要大量移动记录，时间开销大。若要不移动记录完成排序，需要改变存储结构，进行表插入排序。所谓表插入排序，就是通过链接指针，按关键码的大小，实现从小到大的链接过程，为此需增设一个指针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针。用静态链表来说明。

　　#define SIZE 200

　　typedef struct{

　　ElemType elem; /*元素类型*/

　　int next; /*指针项*/

　　}NodeType; /*表结点类型*/

　　typedef struct{

　　NodeType r[SIZE]; /*静态链表*/

　　int length; /*表长度*/

　　}L_TBL; /*静态链表类型*/

　　假设数据元素已存储在链表中，且0号单元作为头结点，不移动记录而只是改变链指针域，将记录按关键码建为一个有序链表。首先，设置空的循环链表，即头结点指针域置0，并在头结点数据域中存放比所有记录关键码都大的整数。接下来，逐个结点向链表中插入即可。

　　表插入排序得到一个有序的链表，查找则只能进行顺序查找，而不能进行随机查找，如折半查找。为此，还需要对记录进行重排。

　　重排记录方法：按链表顺序扫描各结点，将第i个结点中的数据元素调整到数组的第i个分量数据域。因为第i个结点可能是数组的第j个分量，数据元素调整仅需将两个数组分量中数据元素交换即可，但为了能对所有数据元素进行正常调整，指针域也需处理。

　　【算法10.3】

　　1. j=l->r[0].next;i=1; //指向第一个记录位置，从第一个记录开始调整

　　2. 若i=l->length时，调整结束;否则，

　　a. 若i=j，j=l->r[j].next;i++;转(2) //数据元素应在这分量中，不用调整，处理下一个结点

　　b. 若j>i，l->r[i].elem<-->l->r[j].elem; //交换数据元素

　　p=l->r[j].next; // 保存下一个结点地址

　　l->r[j].next=l->[i].next;l->[i].next=j; // 保持后续链表不被中断

　　j=p;i++;转(2) // 指向下一个处理的结点

　　c. 若jr[j].next;//j分量中原记录已移走，沿j的指针域找寻原记录的位置

　　转到(a)

　　【时效分析】

　　表插入排序的基本操作是将一个记录插入到已排好序的有序链表中，设有序表长度为i，则需要比较至多i+1次，修改指针两次。因此，总比较次数与直接插入排序相同，修改指针总次数为2n次。所以，时间复杂度仍为O(n2)

　　希尔排序(Shell’s Sort)算法分析：

　　希尔排序又称缩小增量排序，是1959年由D.L.Shell提出来的，较前述几种插入排序方法有较大的改进。

　　直接插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高，其时间效率可提高到O(n)。希尔排序即是从这两点出发，给出插入排序的改进方法。

　　希尔排序方法：

　　1. 选择一个步长序列t1，t2，…，tk，其中ti>tj，tk=1;

　　2. 按步长序列个数k，对序列进行k趟排序;

　　3. 每趟排序，根据对应的步长ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

　　

　　【算法10.5】

　　void ShellInsert(S_TBL &p，int dk)

　　{ /*一趟增量为dk的插入排序，dk为步长因子*/

　　for(i=dk+1;i<=p->length;i++)

　　if(p->elem[i].key < p->elem[i-dk].key) /*小于时，需elem[i]将插入有序表*/

　　{ p->elem[0]=p->elem[i]; /*为统一算法设置监测*/

　　for(j=i-dk;j>0&&p->elem[0].key < p->elem[j].key;j=j-dk)

　　p->elem[j+dk]=p->elem[j]; /*记录后移*/

　　p->elem[j+dk]=p->elem[0]; /*插入到正确位置*/

　　}

　　}

　　void ShellSort(S_TBL *p，int dlta[]，int t)

　　{ /*按增量序列dlta[0，1…，t-1]对顺序表*p作希尔排序*/

　　for(k=0;k

　　ShellSort(p，dlta[k]); /*一趟增量为dlta[k]的插入排序*/

　　}

　　【时效分析】

　　希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的步长因子序列的方法。步长因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：步长因子中除1外没有公因子，且最后一个步长因子必须为1。希尔排序方法是一个不稳定的排序方法。

　　冒泡排序(Bubble Sort)算法分析：

　　先来看看待排序列一趟冒泡的过程：设1

　　通过两两比较、交换，重新安排存放顺序，使得r[j]是序列中关键码最大的记录。一趟冒泡方法为：

　　① i=1; //设置从第一个记录开始进行两两比较

　　② 若i≥j，一趟冒泡结束。

　　③ 比较r[i].key与r[i+1].key，若r[i].key≤r[i+1].key，不交换，转⑤

　　④ 当r[i].key>r[i+1].key时， r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];

　　将r[i]与r[i+1]交换

　　⑤ i=i+1; 调整对下两个记录进行两两比较，转②

　　冒泡排序方法：对n个记录的表，第一趟冒泡得到一个关键码最大的记录r[n]，第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录r[n-1]，如此重复，直到n个记录按关键码有序的表。

　　【算法10.6】

　　① j=n; //从n记录的表开始

　　② 若j<2，排序结束

　　③ i=1; //一趟冒泡，设置从第一个记录开始进行两两比较，

　　④ 若i≥j，一趟冒泡结束，j=j-1;冒泡表的记录数-1，转②

　　⑤ 比较r[i].key与r[i+1].key，若r[i].key≤r[i+1].key，不交换，转⑤

　　⑥ 当r[i].key>r[i+1].key时， r[i]<-->r[i+1]; 将r[i]与r[i+1]交换

　　⑦ i=i+1; 调整对下两个记录进行两两比较，转④

　　【效率分析】

　　空间效率：仅用了一个辅助单元。

　　时间效率：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。

　　移动次数：

　　最好情况下：待排序列已有序，不需移动。

　　快速排序：

　　快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。

　　【算法10.8】

　　void QSort(S_TBL *tbl,int low,int high) /*递归形式的快排序*/

　　{ /*对顺序表tbl中的子序列tbl->[low…high]作快排序*/

　　if(low

　　{ pivotloc=partition(tbl,low,high); /*将表一分为二*/

　　QSort(tbl,low,pivotloc-1); /*对低子表递归排序*/

　　QSort(tbl,pivotloc+1,high); /*对高子表递归排序*/

　　}

　　}

　　【效率分析】

　　空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度;在最坏情况下，即二叉树是一个单链，为O(n)。

　　时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。

　　理想情况下：每次划分，正好将分成两个等长的子序列，则

　　T(n)≤cn+2T(n/2) c是一个常数

　　≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)

　　≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)

　　······

　　≤cnlog2n+nT(1)=O(nlog2n)

　　最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)。

　　快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

　　选择排序

　　选择排序主要是每一趟从待排序列中选取一个关键码最小的记录，也即第一趟从n个记录中选取关键码最小的记录，第二趟从剩下的n-1个记录中选取关键码最小的记录，直到整个序列的记录选完。这样，由选取记录的顺序，便得到按关键码有序的序列。

　　简单选择排序：

　　操作方法：第一趟，从n个记录中找出关键码最小的记录与第一个记录交换;第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换;如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。

　　【算法10.9】

　　void SelectSort(S_TBL *s)

　　{ for(i=1;ilength;i++)

　　{ /* 作length-1趟选取 */

　　for(j=i+1，t=i;j<=s->length;j++)

　　{ /* 在i开始的length-n+1个记录中选关键码最小的记录 */

　　if(s->elem[t].key>s->elem[j].key)

　　t=j; /* t中存放关键码最小记录的下标 */

　　}

　　s->elem[t]<-->s->elem[i]; /* 关键码最小的记录与第i个记录交换 */

　　}

　　}

　　从程序中可看出，简单选择排序移动记录的次数较少，但关键码的比较次数依然是

　　堆排序(Heap Sort)：设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。

　　若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点的值是最小(或最大)的。

　　设有n个元素，将其按关键码排序。首先将这n个元素按关键码建成堆，将堆顶元素输出，得到n个元素中关键码最小(或最大)的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键码次小(或次大)的元素。如此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。

　　因此，实现堆排序需解决两个问题：

　　1. 如何将n个元素的序列按关键码建成堆;

　　2. 输出堆顶元素后，怎样调整剩余n-1个元素，使其按关键码成为一个新堆。

　　首先，讨论输出堆顶元素后，对剩余元素重新建成堆的调整过程。

　　调整方法：设有m个元素的堆，输出堆顶元素后，剩下m-1个元素。将堆底元素送入堆顶，堆被破坏，其原因仅是根结点不满足堆的性质。将根结点与左、右子女中较小(或小大)的进行交换。若与左子女交换，则左子树堆被破坏，且仅左子树的根结点不满足堆的性质;若与右子女交换，则右子树堆被破坏，且仅右子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。称这个自根结点到叶子结点的调整过程为筛选。

　　再讨论对n个元素初始建堆的过程。

　　建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。n个结点的完全

　　子树成为堆，之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

　　堆排序：对n个元素的序列进行堆排序，先将其建成堆，以根结点与第n个结点交换;调整前n-1个结点成为堆，再以根结点与第n-1个结点交换;重复上述操作，直到整个序列有序。

　　【算法10.10】

　　void HeapAdjust(S_TBL *h，int s，int m)

　　{/*r[s…m]中的记录关键码除r[s]外均满足堆的定义，本函数将对第s个结点为根的子树筛选，使其成为大顶堆*/

　　rc=h->r[s];

　　for(j=2*s;j<=m;j=j*2) /* 沿关键码较大的子女结点向下筛选 */

　　{ if(jr[j].keyr[j+1].key)

　　j=j+1; /* 为关键码较大的元素下标*/

　　if(rc.keyr[j].key) break; /* rc应插入在位置s上*/

　　h->r[s]=h->r[j]; s=j; /* 使s结点满足堆定义 */

　　}

　　h->r[s]=rc; /* 插入 */

　　}

　　void HeapSort(S_TBL *h)

　　{ for(i=h->length/2;i>0;i--) /* 将r[1..length]建成堆 */

　　HeapAdjust(h，i，h->length);

　　for(i=h->length;i>1;i--)

　　{ h->r[1]<-->h->r[i]; /* 堆顶与堆低元素交换 */

　　HeapAdjust(h，1，i-1); /*将r[1..i-1]重新调整为堆*/

　　}

　　}

　　交换记录至多k次。所以，在建好堆后，排序过程中的筛选次数不超过下式：

　　+û1)-log2(në( 2 )û + … + log22û2)-log2(në < nlog2n2

　　而建堆时的比较次数不超过4n次，因此堆排序最坏情况下，时间复杂度也为O(nlog2n)。

　　二路归并排序

　　二路归并排序的基本操作是将两个有序表合并为一个有序表。

　　设r[u…t]由两个有序子表r[u…v-1]和r[v…t]组成，两个子表长度分别为v-u、t-v+1。合并方法为：

　　⑴ i=u;j=v;k=u; //置两个子表的起始下标及辅助数组的起始下标

　　⑵ 若i>v 或 j>t，转⑷ //其中一个子表已合并完，比较选取结束

　　⑶ //选取r[i]和r[j]关键码较小的存入辅助数组rf

　　如果r[i].key

　　否则，rf[k]=r[j]; j++; k++; 转⑵

　　⑷ //将尚未处理完的子表中元素存入rf

　　如果i

　　如果j<=t，将r[i…v]存入rf[k…t] //后一子表非空

　　⑸ 合并结束。

　　【算法10.11】

　　void Merge(ElemType *r，ElemType *rf，int u，int v，int t)

　　{

　　for(i=u，j=v，k=u;i

　　{ if(r[i].key

　　{ rf[k]=r[i];i++;}

　　else

　　{ rf[k]=r[j];j++;}

　　}

　　if(i

　　if(j<=t) rf[k…t]=r[j…t];

　　}

　　两路归并的迭代算法：1个元素的表总是有序的。所以对n个元素的待排序列，每个元素可看成1个有序子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。

　　【算法10.12】

　　void MergeSort(S_TBL *p，ElemType *rf)

　　{ /*对*p表归并排序，*rf为与*p表等长的辅助数组*/

　　ElemType *q1，*q2;

　　q1=rf;q2=p->elem;

　　for(len=1;lenlength;len=2*len) /*从q2归并到q1*/

　　{ for(i=1;i+2*len-1<=p->length;i=i+2*len)

　　Merge(q2，q1，i，i+len，i+2*len-1); /*对等长的两个子表合并*/

　　if(i+len-1length)

　　Merge(q2，q1，i，i+len，p->length); /*对不等长的两个子表合并*/

　　else if(i<=p->length)

　　while(i<=p->length) /*若还剩下一个子表，则直接传入*/

　　q1[i]=q2[i];

　　q1<-->q2; /*交换，以保证下一趟归并时，仍从q2归并到q1*/

　　if(q1!=p->elem) /*若最终结果不在*p表中，则传入之*/

　　for(i=1;i<=p->length;i++)

　　p->elem[i]=q1[i];

　　}

　　}

　　两路归并的递归算法：

　　【算法10.13】

　　void MSort(ElemType *p，ElemType *p1，int s，int t)

　　{ /*将p[s…t]归并排序为p1[s…t]*/

　　if(s==t) p1[s]=p[s]

　　else

　　{ m=(s+t)/2; /*平分*p表*/

　　MSort(p，p2，s，m); /*递归地将p[s…m]归并为有序的p2[s…m]*/

　　MSort(p，p2，m+1，t); /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/

　　Merge(p2，p1，s，m+1，t); /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/

　　}

　　}

　　void MergeSort(S_TBL *p)

　　{ /*对顺序表*p作归并排序*/

　　MSort(p->elem，p->elem，1，p->length);

　　}

　　【效率分析】

　　需要一个与表等长的辅助元素数组空间，所以空间复杂度为O(n)。

　　对n个元素的表，将这n个元素看作叶结点，若将两两归并生成的子表看作它们的父结点，则归并过程对应由叶向根生成一棵二叉树的过程。所以归并趟数约等于二叉树的高度-1，即log2n，每趟归并需移动记录n次，故时间复杂度为O(nlog2n)。

　　基数排序：

　　基数排序是一种借助于多关键码排序的思想，是将单关键码按基数分成“多关键码”进行排序的方法。

　　多关键码排序：

　　设n个元素的待排序列包含d个关键码{k1，k2，…，kd}，则称序列对关键码{k1，k2，…，kd}有序是指：对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系：

　　其中k1称为最主位关键码，kd称为最次位关键码。

　　多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

　　最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD法。

　　最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法二即是LSD法。

　　链式基数排序：

　　将关键码拆分为若干项，每项作为一个“关键码”，则对单关键码的排序可按多关键码排序方法进行。比如，关键码为4位的整数，可以每位对应一项，拆分成4项;又如，关键码由5个字符组成的字符串，可以每个字符作为一个关键码。由于这样拆分后，每个关键码都在相同的范围内(对数字是0～9，字符是'a'～'z')，称这样的关键码可能出现的符号个数为“基”，记作RADIX。上述取数字为关键码的“基”为10;取字符为关键码的“基”为26。基于这一特性，用LSD法排序较为方便。

　　基数排序：从最低位关键码起，按关键码的不同值将序列中的记录“分配”到RADIX个队列中，然后再“收集”之。如此重复d次即可。链式基数排序是用RADIX个链队列作为分配队列，关键码相同的记录存入同一个链队列中，收集则是将各链队列按关键码大小顺序链接起来。

　　【算法10.14】

　　#define MAX_KEY_NUM 8 /*关键码项数最大值*/

　　#define RADIX 10 /*关键码基数，此时为十进制整数的基数*/

　　#define MAX_SPACE 1000 /*分配的最大可利用存储空间*/

　　typedef struct{

　　KeyType keys[MAX_KEY_NUM]; /*关键码字段*/

　　InfoType otheritems; /*其它字段*/

　　int next; /*指针字段*/

　　}NodeType; /*表结点类型*/

　　typedef struct{

　　NodeType r[MAX_SPACE]; /*静态链表，r[0]为头结点*/

　　int keynum; /*关键码个数*/

　　int length; /*当前表中记录数*/

　　}L_TBL; /*链表类型*/

　　typedef int ArrayPtr[radix]; /*数组指针，分别指向各队列*/

　　void Distribute(NodeType *s，int i，ArrayPtr *f，ArrayPtr *e)

　　{ /*静态链表ltbl的r域中记录已按(kye[0]，keys[1]，…，keys[i-1])有序)*/

　　/*本算法按第i个关键码keys[i]建立RADIX个子表，使同一子表中的记录的keys[i]相同*/

　　/*f[0…RADIX-1]和e[0…RADIX-1]分别指向各子表的第一个和最后一个记录*/

　　for(j=0;j

　　for(p=r[0].next;p;p=r[p].next)

　　{ j=ord(r[p].keys[i]); /*ord将记录中第i个关键码映射到[0…RADIX-1]*/

　　if(!f[j]) f[j]=p;

　　else r[e[j]].next=p;

　　e[j]=p; /* 将p所指的结点插入到第j个子表中*/

　　}

　　}

　　void Collect(NodeType *r，int i，ArrayPtr f，ArrayPtr e)

　　{/*本算法按keys[i]自小到大地将f[0…RADIX-1]所指各子表依次链接成一个链表*e[0…RADIX-1]为各子表的尾指针*/

　　for(j=0;!f[j];j=succ(j)); /*找第一个非空子表，succ为求后继函数*/

　　r[0].next=f[j];t=e[j]; /*r[0].next指向第一个非空子表中第一个结点*/

　　while(j

　　{ for(j=succ(j);j

　　if(f[j]) {r[t].next=f[j];t=e[j];} /*链接两个非空子表*/

　　}

　　r[t].next=0; /*t指向最后一个非空子表中的最后一个结点*/

　　}

　　void RadixSort(L_TBL *ltbl)

　　{ /*对ltbl作基数排序，使其成为按关键码升序的静态链表，ltbl->r[0]为头结点*/

　　for(i=0;ilength;i++) ltbl->r[i].next=i+1;

　　ltbl->r[ltbl->length].next=0; /*将ltbl改为静态链表*/

　　for(i=0;ikeynum;i++) /*按最低位优先依次对各关键码进行分配和收集*/

　　{ Distribute(ltbl->r，i，f，e); /*第i趟分配*/

　　Collect(ltbl->r，i，f，e); /*第i趟收集*/

　　}

　　}

　　【效率分析】

　　时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。

　　空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

　　外排序

　　外部排序的方法

　　外部排序基本上由两个相互独立的阶段组成。首先，按可用内存大小，将外存上含n个记录的文件分成若干长度为k的子文件或段(segment)，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存。通常称这些有序子文件为归并段或顺串;然后，对这些归并段进行逐趟归并，使归并段(有序子文件)逐渐由小到大，直至得到整个有序文件为止。

　　显然，第一阶段的工作已经讨论过。以下主要讨论第二阶段即归并的过程。先从一个例子来看外排序中的归并是如何进行的?

　　假设有一个含 10000 个记录的文件，首先通过10次内部排序得到10个初始归并段 R1～R10 ，其中每一段都含1000个记录。然后对它们作如图10.11所示的两两归并，直至

　　得到一个有序文件为止。

　　将两个有序段归并成一个有序段的过程，若在内存中进行，则很简单，前面讨论的2-路归并排序中的Merge函数便可实现此归并。但是，在外部排序中实现两两归并时，不仅要调用Merge函数，而且要进行外存的读/写，这是由于我们不可能将两个有序段及归并结果同时放在内存中的缘故。对外存上信息的读/写是以“物理块”为单位。假设在上例中每个物理块可以容纳200个记录，则每一趟归并需进行50次“读”和50次“写”，四趟归并加上内部排序时所需进行的读/写，使得在外排序中总共需进行500次的读/写。

　　一般情况下，外部排序所需总时间=内部排序(产生初始归并段)所需时间 m*tis+外存信息读写的时间 d*tio +内部归并排序所需时间 s*utmg

　　其中：tis是为得到一个初始归并段进行的内部排序所需时间的均值;tio是进行一次外存读/写时间的均值;utmg是对u个记录进行内部归并所需时间;m为经过内部排序之后得到的初始归并段的个数;s为归并的趟数;d为总的读/写次数。由此，上例10000个记录利用2-路归并进行排序所需总的时间为：

　　10*tis+500*tio+4*10000tmg

　　其中tio取决于所用的外存设备，显然，tio较tmg要大的多。因此，提高排序效率应主要着眼于减少外存信息读写的次数d。

　　3.2查找算法

　　查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的结点。

　　按查找的条件分类：

　　u 有按结点的关键码查找;

　　u 关键码以外的其他数据项查找;

　　u 其他数据项的组合查找;

　　按查找数据在内存或外存：分内存查找和外存查找。

　　按查找目的：

　　u 查找如果只是为了确定指定条件的结点存在与否，成为静态查找;

　　u 查找是为确定结点的插入位置或为了删除找到的结点，称为动态查找。

　　这里简单介绍几种常见的查找方法。

　　u 顺序存储线性表的查找

　　这是最常见的查找方式。结点集合按线性表组织，采用顺序存储方式，结点只含关键码，并且是整数。如果线性表无序，则采用顺序查找，即从线性表的一端开始逐一查找。而如果线性表有序，则可以使用顺序查找、二分法查找或插值查找。

　　u 分块查找

　　分块查找的过程分两步，先用二分法在索引表中查索引项，确定要查的结点在哪一块。然后，再在相应块内顺序查找。

　　u 链接存储线性表的查找

　　对于链接存储线性表的查找只能从链表的首结点开始顺序查找。同样对于无序的链表和有序的链表查找方法不同。

　　动态查找表的不同表示方法：

　　二叉排序树(二叉查找树)：或者是一棵空树，或者是具有下列性质的一棵树：

　　u 若左子树不空，则左子树上的所有节点的值都小于根节点的值;

　　u 若右子树不空，则右子树上的所有节点的值都大于根节点的值;

　　u 它的左右子树也分别是二叉排序树;

　　二叉排序树的查找分析：在随机的情况下，其平均查找长度为1+4logn;

　　平衡二叉树：或者是棵空树，或者是具有下列性质的二叉树：

　　u 它的左子树和右子树都是平衡二叉树;

　　u 左子树和右子树的深度之差不会超过1;

　　平衡二叉树的查找分析：在查找过程中和给定值进行比较的关键字个数不超过树的深度，，因此其平均查找的时间复杂度是O(logn);

　　u 散列表的查找

　　散列表又称杂凑表，是一种非常实用的查找技术。它的原理是在结点的存储位置和它的关键码间建立一个确定的关系，从而让查找码直接利用这个关系确定结点的位置。其技术的关键在于解决两个问题。

　　I. 找一个好的散列函数

　　II. 设计有效解决冲突的方法

　　常见的散列函数有：

　　I. 质数除取余法

　　II. 基数转换法

　　III. 平方取中法

　　IV. 折叠法

　　V. 移位法

　　常见的解决冲突的方法有：

　　I. 线性探查法

　　II. 双散列函数法

　　III. 拉链法

　　假设HASH表的地址集为0-n-1，冲突是指由关键字得到的HASH地址的位置上已经存在记录，则处理冲突就是为该关键字的记录找到另一个空的HASH地址用于存放。

　　处理冲突的方法：

　　开放地址法(线性探查法)：二次地址=(一次地址+增量序列) MOD 散列表长度M

　　再HASH法(双散列函数法)：使用不同的散列函数计算，互相作为补偿;

　　二次地址=RH(key) R和H都是散列函数

　　拉链法(链地址法)：设立一个指针数组，初始状态是空指针，HASH地址为i的记录都插入到指针数组中第i项所指向的链表中，保持关键字有序。

　　建立一个公共的溢出区：将所有冲突的关键字和记录都添入到溢出区。

　　HASH查找分析： HASH的查找长度与查找表的长度无关，只与装添因子有关

　　装添因子=表中添入的记录数/HASH的长度

　　4. 重点、难点解析

　　数据结构的相关知识点在软考中是经常出现的，无论是上午的客观题，还是下午的程序填空，都会涉及，而且考试的题型除了一般的概念和常识以外，还涉及各种算法，出题十分灵活。因此对这部分的复习一定要非常重视。这里我们总结了数据结构部分的一些比较重要的要点。

　　n 链式存储结构

　　不管是线性表、栈，还是队列，都会使用链式存储结构。对于链式存储结构的操作与顺序存储结构不一样，因此我们需要熟悉它们的相关算法。如：

　　u 对于链式存储的线性表，它的插入、删除和查找算法。

　　u 对于链接存储栈，它的进栈、出栈算法

　　u 对于链接存储队列，它的进队、出队算法

　　另外，对于栈和队列的一些实际应用的算法也需要关心，特别在下午的程序填空的考试中，经常会碰到类似的算法。

　　关于图的概念和相关算法很多，这对高程软考来说，也是一个重点。

　　除了我们前面罗列的一些关于的图的基本概念以外，首先我们必须对图的几种存储结构要十分的清楚，因为这实际上是研究图的相关问题和算法的基础。包括：

　　u 邻接矩阵

　　u 邻接表

　　u 十字链表

　　u 邻接多重表

　　对于图的两种遍历算法(深度优先和广度优先)实际可以参考树的有关遍历算法，这样理解起来相对简单。

　　而对于图的有关算法，如求最小代价生成树、求最短路径、拓扑排序和求关键路径等，这是数据结构中的难点。不过一般来说，软考中很难直接考到。因此，大家在复习的时候主要抓住涉及算法的相关概念、算法的基本原理以及算法的复杂度这几个方面。当然，有时间最好参看一下相关资料，对它的具体实现仔细看看，这对理解其算法的核心思想当然会事半功倍。

　　二叉树

　　二叉树永远都是数据结构中考查的重点，包括二叉树的基本概念、性质以及各种不同的遍历方法。而且，它的相关算法也是树和森林的算法的基础。因此对这部分知识要十分的重视。

　　另外，有时候还会涉及到二叉查找树的一些概念和算法。

　　查找树便于链式存储，还能实现快速查找。作为一种特殊的二叉树，它或者为空，或者满足以下3个条件：

　　I. 若该树根结点的左子树非空，其左子树所有结点的键值都小于该树根结点的键值

　　II. 若该树根结点的右子树非空，其右子树所有结点的键值都大于该树根结点的键值

　　III. 该树根的左子树和右子树均为查找树

　　根据以上定义可以知道，如果进行中序遍历，即可得到一个从小到大的结点序列。

　　排序

　　排序对于数据结构来说是一个特别重要的重点和难点，这也是体现一个高级程序员基本素质的地方。我们除了要掌握各种排序算法的基本思想，还必须要掌握其具体实现(用C语言或者Pascal语言均可)，这反过来对我们更深刻领会其算法的本质也很有裨益。另外，对于它们之间的各种差异比较，如稳定性、时间复杂度、空间复杂度也要有所了解。这可以见前面知识要点部分的相关内容。

　　HASH表的处理过程和解决冲突的方法!!!