数据结构-第10章-内排序

数据结构李云清杨庆红揭安全人民邮电出版社高等学校精品课程（省级）国家十二五规划教材高等学校精品课程（省级）国家十二五规划教材揭安全jieanquan@163.com江西师范大学计算机信息工程学院第10章内排序交换排序

冒泡排序快速排序直接选择排序堆排序第十章内排序插入排序直接插入排序二分插入排序希尔排序选择排序归并排序基数排序排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内排序的各种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。10.1排序的基本概念

假设一个文件是由n个记录R1，R2，…，Rn组成，所谓排序就是以记录中某个(或几个)字段值不减(或不增)的次序将这n个记录重新排列，称该字段为排序码。能唯一标识一个记录的字段称为关键码，关键码可以作为排序码，但排序码不一定要是关键码。

按排序过程中使用到的存储介质来分，可以将排序分成两大类:内排序和外排序。

内排序是指在排序过程中所有数据均放在内存中处理，不需要使用外存的排序方法。而对于数据量很大的文件，在内存不足的情况下，则还需要使用外存，这种排序方法称为外排序。

排序码相同的记录，若经过排序后，这些记录仍保持原来的相对次序不变，称这个排序算法是稳定的。否则，称为不稳定的排序算法。评价排序算法优劣的标准：首先考虑算法执行所需的时间，这主要是用执行过程中的比较次数和移动次数来度量；其次考虑算法执行所需要的附加空间。当然，保证算法的正确性是不言而喻的，可读性等也是要考虑的因素。/****************************************//*常见排序算法的头文件，文件名table.h*//***************************************/#defineMAXSIZE100 /*文件中记录个数的最大值*/typedefintkeytype; /*定义排序码类型为整数类型*/typedefstruct{keytypekey;intother; /*此处还可以定义记录中除排序码外的其他域*/}recordtype; /*记录类型的定义*/typedefstruct{recordtyper[MAXSIZE+1];intlength; /*待排序文件中记录的个数*/}table; /*待排序文件类型*/voidinit(table*L)/*顺序表初始化函数*/{inti;srand(time(NULL)); L->length=10; for(i=1;i<=10;i++) L->r[i].key=rand(i)%100;}voidprint(tableL)/*顺序表输出函数*/{inti,k=0;for(i=1;i<=L.length;i++){printf("%4d",L.r[i].key);if(++k%10==0)printf("\n");}printf("\n");}/*顺序表文件输入函数*/voidinput(table*L,char*f){inti;FILE*fp;fp=fopen(f,"r");if(fp){fscanf(fp,"%d",&L->length);for(i=1;i<=L->length;i++)fscanf(fp,"%d",&L->r[i].key);}elseL->length=0;}10503020901070804060100一个输入文件的例子10.2插入排序插入排序的基本方法是:将待排序文件中的记录，逐个地按其排序码值的大小插入到目前已经排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。10.2.1直接插入排序直接插入排序算法的思路是:初始可认为文件中的第1个记录己排好序，然后将第2个到第n个记录依次插入已排序的记录组成的文件中。在对第i个记录Ri进行插入时，R1，R2，…，Ri-1已排序，将记录Ri的排序码keyi与已经排好序的排序码从右向左依次比较，找到Ri应插入的位置，将该位置以后直到Ri-1各记录顺序后移，空出该位置让Ri插入。直接插入排序演示012345621254925*1608i=321254925*16080123456初态490123456212525*1608i=249250123456i=6i=52125080123456214925*160801234564925*1621254925*1608i=425*160825214925*1608完成25习题：给出初始数列{47，28，32，15，94，33，14，16}在直接插入排序下的状态变化过程。4728321594331416初态：i=2i=3i=4i=5i=6i=72847321594331416283247159433141615283247943314161528324794331416152832334794141614152832334797161415162832334797i=8voidinsertsort(table*L)/*直接插入排序*/{inti,j;for(i=2;i<=L->length;i++){j=i-1;L->r[0]=L->r[i];/*放置哨兵*/while(L->r[j].key>L->r[0].key){ L->r[j+1]=L->r[j]; j--;}L->r[j+1]=L->r[0];}}算法10.1直接插入排序算法直接插入排序算法执行时间的分析：最好的情况：即初始排序码开始就是有序的情况下，直接插入排序算法的比较次数为(n-1)次，移动次数为2*(n-1)次。最坏情况：即初始排序码开始是逆序的情况下，因为当插入第i个排序码时，该算法内循环while要执行i次条件判断，循环体要执行i-l次，每次要移动1个记录，外循环共执行n-1次，其循环体内不含内循环每次循环要进行2次移动操作，所以在最坏情况下，比较次数为(1+2+…+n)。直接插入排序算法的时间复杂度为O(n2)。10.2.2二分法插入排序二分法插入排序的思想：根据插入排序的基本思想，在找第i个记录的插入位置时，前i-l个记录已排序，将第i个记录的排序码key[i]和已排序的前i-1个的中间位置记录的排序码进行比较，如果key[i]小于中间位置记录排序码，则可以在前半部继续使用二分法查找，否则在后半部继续使用二分法查找，直到查找范围为空，即可确定key[i]的插入位置。voidbinarysort(table*L)/*折半插入排序*/{intleft,right,mid,i,j;for(i=2;i<=L->length;i++){L->r[0]=L->r[i];/*保存待插入的元素*/left=1;right=i-1;/*设置查找范围的左、右位置值*/while(left<=right)/*查找第i个元素的插入位置*/{mid=(left+right)/2;/*取中点位置*/if(L->r[i].key<L->r[mid].key)right=mid-1;elseleft=mid+1;}/*插入位置为left*/for(j=i-1;j>=left;j--)/*后移留空*/L->r[j+1]=L->r[j];L->r[left]=L->r[0];/*插入第i个元素的副本*/}}算法10.2二分法插入排序算法二分法插入排序算法，在查找第i个记录的插入位置时，每执行一次while循环体，查找范围缩小一半，和直接插入排序的比较次数对比，二分法插入的比较次数少于直接插入排序的最多比较次数，而一般要多于直接插入排序的最少比较次数。总体上讲，当n较大时，二分法插入排序的比较次数远少于直接插入排序的平均比较次数，但二者所要进行的移动次数相等，故二分法插入排序的时间复杂度也是O(n2)，所需的附加存储空间为一个记录空间。10.2.3表插入排序二分法插入排序比较次数通常比直接插入排序的比较次数少，但移动次数相等。表插入排序将在不进行记录移动的情况下，利用存储结构有关信息的改变来达到排序的目的。给每个记录附设一个所谓的指针域link，它的类型为整型，表插入排序的思路：在插入第i个记录Ri时，R1，R2，…，Ri-1已经通过各自的指针域link按排序码不减的次序连接成一个（静态链）表，将记录Ri的排序码keyi与表中已经排好序的排序码从表头向右、或称向后依次比较，找到Ri应插入的位置，将其插入在表中，使表中各记录的排序码仍然有序。/*表插入排序定义的头文件，文件名为：table2.h*/#defineMAXSIZE100/*文件中记录个数的最大值*/typedefintkeytype;/*定义排序码类型为整数类型*/typedefstruct{keytypekey;intlink;}recordtype;/*记录类型的定义*/typedefstruct{recordtyper[MAXSIZE+1];intlength;/*待排序文件中记录的个数*/}table2;/*待排序文件类型*/表插入排序算法的示意如图10.4所示keylink

31212627222628165123

下标

01234567（a）初始存储状态下标

01234567（b）由第1个记录构成的有序表下标

01234567（c）插入第2个记录构成的有序表keylink

31212627222628165123

1

0

keylink

31212627222628165123

2

0

1

表插入排序算法：初始时，r[0].Link用于存放表中第1个记录的下标，r[0].Link的值为1，排序结束时，r[0].Link中存放的是所有排序码中值最小的对应记录的下标，其它的排序码通过各自的指针域link按不减的次序连接成一个（静态链）表，最大的排序码对应的link为0。keylink

31212627222628165123

5

0

6

1

3

7

4

2下标

01234567（d）所有记录都插入后的结束状态（下标为5的记录的key值最小）图10.4表插入排序算法示意图voidtableinsertsort(table2*tab){inti,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;}}算法10.3表插入排序算法基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整，它是由D.L.shell在1959年提出来的。所谓“宏观”调整，指的是，“跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序。关键是，这种子序列不是由相邻的记录构成的。假设将n个记录分成d个子序列，则这d个子序列分别为：10.2.4Shell插入排序{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}10.2.4Shell插入排序21254925*16080123456i=1d=32125*2516084949d=208162125*25组内排序得：组内排序得：210825164925*jj+d21254925*1608

12345621254925*1608012345d=1210825164925*开始时d的值较大，子序列中的对象较少，排序速度较快；随着排序进展，d值逐渐变小(一般可以按d=d/2的规律变化)，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。设待排序的7记录的排序码为{312，126，272，226，28，165，123}，初始让d=7/2=3，以后每次让d缩小一半，其排序过程如图所示。31228123126165226272

01234567(c)完成31212328165226126272

01234567(b)d=112331212627222628165

01234567(a)初始状态d=3习题：给出初始数列{47，28，32，15，94，33，14，16}在shell排序下的状态变化过程。d=44728321594331416472814159433321614153216472894331415162832334794d=2d=1结果voidshellsort(table*L)/*希尔排序*/{inti,j,d;d=L->length/2;while(d>=1){for(i=d+1;i<=L->length;i++)/*从第d+1个元素开始,将所有元素依次有序插入到相应的分组中*/{L->r[0]=L->r[i]; /*保存第i个元素*/

j=i-d; /*向前找插入位置*/while(j>0&&L->r[0].key<L->r[j].key)/*找插入位置并后移*/

{L->r[j+d]=L->r[j];/*后移*/

j=j-d;/*继续向前查找*/

}L->r[j+d]=L->r[0];/*插入第i个元素的副本*/}

d=d/2;}}算法10.4Shell插入排序算法10.3选择排序选择排序的基本思想是：每次从待排序的文件中选择出排序码最小的记录，将该记录放于已排序文件的最后一个位置，直到已排序文件记录个数等于初始待排序文件的记录个数为止。10.3.1直接选择排序

首先从所有n个待排序记录中选择排序码最小的记录，将该记录与第1个记录交换，再从剩下的n-l个记录中选出排序码最小的记录和第2个记录交换。重复这样的操作直到剩下2个记录时，再从中选出排序码最小的记录和第n-1个记录交换。剩下的那1个记录肯定是排序码最大的记录，这样排序即告完成。直接选择排序演示2125*i=12516490825160825*4921i=221254925*1608

123456初始最小者

08交换21,08最小者

16交换25,1625160825*4921结果4925*i=408162521最小者

25*无交换最小者

25无交换25*i=54925211608

12345649i=3081625*2521最小者

21交换49,21voidselectsort(table*L)/*简单选择排序算法*/{int

i,j,k;for(i=1;i<L->length;i++){k=i;for(j=i+1;j<=L->length;j++)/*找最小元素所在位置*/if(L->r[j].key<L->r[k].key)k=j;if(k!=i){L->r[0]=L->r[i];/*将第i次找到的最小元素放到第i个位置*/L->r[i]=L->r[k];L->r[k]=L->r[0];}}}直接选择排序算法执行过程如图10.6所示（见书本）10.3.3堆排序为了既要保存中间比较结果，减少后面的比较次数，又不占用大量的附加存储空间，使排序算法具有较好的性能，Willioms和Floyd在1964年提出的称为堆排序的算法实现了这一想法。堆是一个序列{k1,k2,…,kn}，它满足下面的条件：

ki≤k2i并且ki≤k2i+1，当i=1,2,…,

n/2

采用顺序方式存储这个序列，就可以将这个序列的每一个元素ki看成是一颗有n个结点的完全二叉树的第i个结点，其中k1是该二叉树的根结点。堆形：元素序列{a1,a2,…,an}的如下层次关系：a1a2a4a3a5a6123456堆关系：若j=2i或j=2i+1则称<ai,aj>有堆关系，这时称ai为此堆关系的顶，aj为此堆关系的基。堆：满足以下条件的堆形：对堆形中的所有堆关系<ai,aj>均有ai<=aj或ai>=aj

。把堆对应的一维数组(即该序列的顺序存储结构)看作一棵完全二叉树的顺序存储，那么堆的特征可解释为，完全二叉树中任一分支结点的值都小于或等于它的左、右儿子结点的值。堆的元素序列中的第一个元素k1，，即对应的完全二叉树根结点的值是所有元素中值最小的。堆排序方法就是利用这一点来选择最小元素。在堆中结点序号>n/2的结点没有基，实际上堆关系满足完全二叉树的结构特征。34752012123456152778（a）一个最小堆的例子91882342241612345651378（b）一个最大堆的例子一个序列和相应的完全二叉树：312272

165

123126

28

226

8

12

12812316528226272126312下标0123456789123456789以下我们讨论最大堆：最大堆的重要性质：1）堆顶元为堆中最大元2）堆具有部分有序性。即具有存储比较结果的功能，遭受破坏时易于调整成新的堆。堆的存储实现——一维数组。

918842232416513

12345678a0层1层2层3层堆排序的基本思想：——基本操作1）建堆（将待排序部分调整成堆）2）取最大元（堆顶元）3）并入（将最大元并入已排序部分）建堆算法（R.W.Floyd）1964年提出---筛选法1）将待排序的数组随意地组成一个堆形2）沿堆形自下向上，自右向左依次进行筛选。设当前要筛选ai，这时：若ai>=max(a2i,a2i+1)，即满足堆条件，则对ai的筛选结束；若ai<max(a2i,a2i+1)，则ai与大者交换，即沿大基下降。42132391241612345658878(a)i=4,23筛下一层i42138891241612345652378i(b)i=3,91>16不调整42138891241612345652378i(c)i=2,13下沉两级42882391241612345651378i(d)i=1,42筛下一层91882342241612345651378

918842232416513

12345678a（e）建成的堆最大元在堆顶建堆的关键一步：筛选L[k]若r[low]的右孩子存在且大于左兄弟，则令j指向它，让它沿大基下沉voidsift(table*L,intk,intm){int

i,j,finished;

/*初始化*/i=k;j=2*i;L->r[0]=L->r[k];finished=0;

/*确定下沉位置*/

while((j<=m)&&(!finished)){if((j<m)&&(L->r[j+1].key>L->r[j].key))j++;

if(L->r[0]>=L->r[j])finished=1;

else{L->r[i]=L->r[j];i=j;j=2*j;}}

/*被筛数下沉*/L->r[i]=L->r[0];}建堆总体控制：

for(i=L->length/2;i>=1;i--)sift(L,i,L->length);/*对所有元素建堆*/堆排序过程：1）建初始堆（大根堆）2）重复以下工作，一直到排序结束交换截尾重新建堆

for(i=L->length;i>=2;i--)voidheapsort(table*L){}

inti;

for(i=L->length/2;i>=1;i--)

sift(L,i,L->length); /*对所有元素建堆*/for(i=L->length;i>=2;i--)/*i表示当前堆的大小，即等待排序的元素的个数*/{}

L->r[0]=L->r[i];L->r[i]=L->r[1];L->r[1]=L->r[0];/*上述3条语句为将堆中最小元素和最后一个元素交换*/

sift(L,1,i-1);若设堆中有n个结点，且2k-1

n

2k，则对应的完全二叉树有k层。在第i层上的结点数

2i(i=0,1,…,k-1)。在第一个形成初始堆的for循环中对每一个非叶结点调用了一次堆调整算法sift()，因此该循环所用的计算时间为：算法分析：其中，i是层序号，2i是第i层的最大结点数，(k-i-1)是第i层结点能够移动的最大距离。在第二个for循环中，调用了n-1次sift()算法，该循环的计算时间为O(nlog2n)。因此，堆排序的时间复杂性为O(nlog2n)。该算法的附加存储主要是在第二个for循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。堆排序是一个不稳定的排序方法。练习：1、给出初始数列{47、28、32、15、94、33、14、16}在堆排序下的建堆过程及示意图。2、下列四个选项中，哪一个序列组成一个最小堆？a）20、76、35、23、80、54b）20、54、23、80、35、76c）80、23、35、76、20、54d）20、35、23、80、54、76答案：d算法设计题：1、写一个Heapinsert(r,key)算法，将关键字插入到堆r中，并保证插入后r后仍是堆。2、写一个建堆算法：从空堆开始，依次读入元素调用上题中堆插入算法将其插入堆中。3、写一个堆删除算法heapdelete(r,i)，将r[i]从堆r中删去。10.4交换排序交换排序的基本思路：对待排序记录两两进行排序码比较，若不满足排序顺序则交换这对记录，直到任何两个记录的排序码都满足排序要求为止。快速排序冒泡排序第1趟，对所有记录从左到右每相邻两个记录的排序码进行比较，如果这两个记录的排序码不符合排序要求，则进行交换，这样一趟做完，将排序码最大者放在最后一个位置；第2趟对剩下的n-l个待排序记录重复上述过程，又将一个排序码放于最终位置，反复进行n-l次，可将n-l个排序码对应的记录放至最终位置，剩下的即为排序码最小的记录，它在第1的位置处。如果在某一趟中，没有发生交换，则说明此时所有记录已经按排序要求排列完毕，排序结束。10.4.1冒泡排序一趟冒泡：对数列中指定的起点到终点间的数据进行连续冒泡。4728321594331416例：2847321594331416324728159433141615472832943314161547283294331416339415472832141614941547283233161694154728323314voidbubblesort(table*L)/*冒泡排序*/{inti,j,flag;

i=L->length;/*变量i记录参与冒泡排序的元素个数＊/while(i>1){flag=0;for(j=0;j<i;j++)if(L->r[j].key>L->r[j+1].key)/＊逆序则交换＊／

{L->r[0]=L->r[j];L->r[j]=L->r[j+1];L->r[j+1]=L->r[0];

flag=1;}

if(flag==0)break;

i--;

/＊元素个数减１＊/}}/*算法10.8冒泡排序算法*/二、快速排序基本思想：1）找一个记录，以它的关键字作为“枢轴”，（通常为第一个数t）2）划分——其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。3）对上步分成的两个无序数组段重复1）、2）操作直到段长为1。t<t>=tpivot2125*i=125164908pivot21254925*16080123456pivot例：211608i=225*pivot4925i=3081621254925*关键问题：如何划分？事实：划分过程也是当前选出数t的最后定位过程。方法：从外向内来回比较法。1）将当前选择的数保存到t中，以空出左端。2）从右向左依次比较，放过那些大于t的数，一直找到第一个小于等于t的数；将此数放入空左端，并令其空出的位置为新右端，原左端的右邻为新左端。3）从左向右依次地放过那些<=t的各数，直找到第一个>=t的数；将此数放入空右端，并令其空出的位置为新左端，原右端的左邻为新右端。4）重复2）3）步，直至t进入最终位置。例：

123456t=a[1]初始序列如下：21254925*1608从右向左找第一个小于t的数21rightleft例：

123456t=a[1]初始序列如下：254925*1608rightleft例：

123456t=a[1]初始序列如下：254925*1608rightleft21例：

123456t=a[1]初始序列如下：254925*1608rightleft从左向右找第一个大于t的数例：

123456t=a[1]初始序列如下：254925*1608rightleft例：

123456t=a[1]初始序列如下：254925*1608rightleft21从右向左扫描例：

123456t=a[1]初始序列如下：254925*1608leftright21例：

123456t=a[1]初始序列如下：254925*1608leftright例：

123456t=a[1]初始序列如下：254925*1608leftright从左向右扫描21例：

123456t=a[1]初始序列如下：254925*1608rightleft例：

123456t=a[1]初始序列如下：254925*1608rightleft一次划分结束条件：left=right21快速排序就是不断地对原始数据段及划分中分出的新数据段作划分。关键一步：对L->r[left..right]作一次来回比较。1）从右向左找第一个不大于t的数。

while(left<right&&t.key<L->r[right].key)right--;2）将r[right]填入空左端，并设置新左端。

if(left<right){}3）从左向右找第一个大于t的数。

while()left++;4）将r[left]填入空右端，并设置新右端。if(left<right){L->r[right]=L->r[left];right--;}L->r[left]=L->r[right];left++;left<right&&t.key>L->r[left].keyright快速排序的总体控制：quicksort(&L,low,high)1）初始化：left=low;right=high;t=r[left];2）对当前数据段作划分：

do{一次来回比较；}while(left!=right);3）将t填入最终位置:L->r[]=t;4）递归地对L[low..left-1]，L[left+1..high]作快速排序。

quicksort();leftquicksort();L,low,left-1L,left+1,highvoidquicksort(table*L,intlow,inthigh){intleft,right;recordtypet;if(low<high){/*初始化*/left=low;right=high;t=L->r[left];do{while(left<right&&t.key<L->r[right].key)right--;/*从右往左找第一个小于等于t的元素*/if(left<right){L->r[left]=L->r[right];left++;}/*将r[right]的值填入左端，并设新左端*/while(left<right&&t.key>L->r[left].key)left++;/*从左往右找第一个大于t的元素*/快速排序递归出口条件一次划分初始化工作来回比较进行一次划分

if(left<right){L->r[right]=L->r[left];right--;}/*将r[left]的值填入右端，并设新右端*/}while(left!=right);

L->r[left]=t;/*t存入相应位置*/

/*递归对左段和右段进行快速排序*/

quicksort(L,low,left-1);quicksort(L,left+1,high);}}一次划分结束条件划分元放最终位置递归地对左、右区间进行快速排序算法分析：快速排序被认为是在所有同数量级O(nlogn)的排序方法中，其平均性能是最好的。例但是，若待排记录的初始状态为按关键字有序时，快速排序将蜕化为冒泡排序，其时间复杂度为O(n2)。初始序列：2030405060708090100什么样的初始序列具有最佳的快速排序时间效率？

？练习：1、给定初始序列{31，68，45，90，23，39，54，12、87、76}，请写出以31为枢轴的划分结果。2、试设计一个算法，使得在O(n)的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。思考题：采用链式存储的线性表如何进行快速排序。

？（一）双链表∧∧head4010608020（二）单链表（带头结点）∧head

4010806030tail=NULLpqpresp指示当前用于划分的枢轴q指示当前与p结点进行比较的结点；pre指示q的前驱结点；s用于指示被移动的结点。（二）单链表（带头结点）∧head

4010806030tail=NULLpqpres将s指示的结点取下插入到当前的链首由以下步骤完成：pre->next=q;（二）单链表（带头结点）∧head

4010806030tail=NULLpqpres将s指示的结点取下插入到当前的链首由以下步骤完成：pre->next=q;s->next=head->next;（二）单链表（带头结点）∧head

4010806030tail=NULLpqpres将s指示的结点取下插入到当前的链首由以下步骤完成：pre->next=q;s->next=head->next;head->next=s;（二）单链表（带头结点）∧head

4010806030tail=NULLpqpres将s指示的结点取下插入到当前的链首由以下步骤完成：pre->next=q;s->next=head->next;head->next=s;（二）单链表（带头结点）将s指示的结点取下插入到当前的链首由以下步骤完成：pre->next=q;s->next=head->next;head->next=s;∧head

1040806030tail=NULLpqpres（二）单链表（带头结点）若q指示的结点值比p指示的结点值大，则该结点的位置保留不动，处理下一个结点。即：∧head

1040806030tail=NULLpqprespre=q;q=q->next;（二）单链表（带头结点）若q指示的结点值比p指示的结点值大，则该结点的位置保留不动，处理下一个结点。即：∧head

1040806030tail=NULLpqprespre=q;q=q->next;（二）单链表（带头结点）若q指示的结点值比p指示的结点值大，则该结点的位置保留不动，处理下一个结点。即：∧head

1040806030tail=NULLpqprespre=q;q=q->next;（二）单链表（带头结点）∧head

1040806030tail=NULLpqpres（二）单链表（带头结点）∧head

3010804060tail=NULLpqpres（二）单链表（带头结点）∧head

3010804060tail=NULLpq=NULLpres划分结束条件：q==tail;递归地对前半部分和后半部分进行快速链式排序：quicksort(head,p)quicksort(&p,tail)归并排序的基本思路是：一个待排序记录构成的文件，可以看作是有多个有序子文件组成的，对有序子文件通过若干次使用归并的方法，得到一个有序文件。归并是指将两个（或多个）有序子表合并成一个有序表的过程。将两个有序子文件归并成一个有序文件的方法简单，只要将两个有序子文件的当前记录的排序码进行比较，较小者放入目标——有序文件，重复这一过程直到两个有序子文件中的记录都放入同一个有序文件为止。10.5归并排序归并排序最常用的方法是两两进行归并，称为二路归并。二路归并基本思想：1）将n个数看成n个长度为1的有序表。2）将两两相邻的表依次进行归并3）重复2），直到归并成单个有序表归并排序需要调用两个操作，一个称之为一次归并，另一个称之为一趟归并。一次归并是指将一个数组中两个相邻的有序数组段归并为一个有序数组段，其结果存储于另一个数组中的操作。77771948例如：初始序列如下：265771611159154819ab52617711661559a1526771115596619481948b151115265966a1511151926485966关键操作：1）一次归并：把首尾相接的两个有序表l1->r[u..m]、l1->r[m+1..v]归并成为有序表l2.r[u..v]。2）一趟归并：把一些相互邻接的有序表（在数组a中）依次两两归并成一些更大的有序表。一次归并可按以下步骤进行：1）初始化：i=u;j=m+1;k=u;i指向数组段l1->r[u..m]的当前位置；j指向l1->r[m+1..v]的当前位置；K指向l2.r[u..v]的当前数组元素（空位）2）数组段l1->r[i..m]与l1->r[j..v]均为非空时的处理

while(i<=m&&j<=v){if(l1->r[i].key<=l1->r[j].key){l2.r[k]=l1->r[i];i++;}else{l2.r[k]=l1->r[j];j++;}k++;}3）数组段r[i..m]与r[j..v]之一为空时的处理//将剩余部分直接复制到l2->r[k..v]if(i>m)for(t=j;t<=v;t++)l2.r[k+t-j]=l1->r[t];elsefor(t=i;t<=m;t++)l2.r[k+t-i]=l1->r[t];//本语句执行后，数组段l2.r[u..v]为合并结果。voidmerge(table*l1,intu,intm,intv){inti,j,k,t; tablel2;

i=u;j=m+1;k=u;while(i<=m&&j<=v){if(l1->r[i].key<=l1->r[j].key){l2.r[k]=l1->r[i];i++;}else{ l2.r[k]=l1->r[j]; j++;}k++;}if(i>m)for(t=j;t<=v;t++)l2.r[k+t-j]=l1->r[t];elsefor(t=i;t<=m;t++)l2.r[k+t-i]=l1->r[t];

/*将l2表中的内容拷贝回表l1*/

for(i=u;i<=v;i++) l1->r[i]=l2.r[i];}一趟归并（mergepass(&l1,n,len)）的实现1）初始化：i=1;//i是第一对有序表的起点2）依次对各相邻的有序表对进行一次归并

while(i<=n-2*len+1)//剩余部分有2len长

{merge(l1,i,i+len-1,i+2*len-1);i=i+2*len;//i指向下一对待归并表起点

}

if(i+len-1<n)//剩余部分大于len小于2len

merge(l1,i,i+len-1,n);3）对长度不足2len的剩余部分和处理一趟归并算法如下：

voidmergepass(table*l1,intn,intlen){inti,t;i=1;while(i<=n-2*len+1){ merge(l1,i,i+len-1,i+2*len-1); i=i+2*len;}if(i+len-1<n) merge(l1,i,i+len-1,n);}二路归并总体控制：mergesort.cvoidmergesort(table*l1){intlen,n;tablel2;n=l1->length;len=1;while(len<n){mergepass(l1,n,len);len=len*2;}}二路归并递归算法：mergesort.cvoidmergesortdc(table*l1,intlow,inthigh){intmid;if(low<high){mid=(low+high)/2;mergesortdc(l1,low,mid);mergesortdc(l1,mid+1,high);merge(l1,low,mid,high);}}算法分析在迭代的归并排序算法中，函数MergePass()做一趟两路归并排序，要调用merge()函数

n/(2*len)

O(n/len)次，函数MergeSort()调用MergePass()正好

log2n

次，而每次merge()要执行比较O(len)次，所以算法总的时间复杂度为O(nlog2n)。归并排序占用附加存储较多，需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。归并排序是一个稳定的排序方法。10.6基数排序(RadixSort)基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。多关键码排序以扑克牌排序为例。每张扑克牌有两个“关键码”：花色和面值。其有序关系为：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A如果我们把所有扑克牌排成以下次序：

2,…,

A,

2,…,

A,

2,…,

A,

2,…,

A这就是多关键码排序。排序后形成的有序序列叫做词典有序序列。对于上例两关键码的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情况下，假定有一个n个对象的序列{V0,V1,…,Vn-1}，且每个对象Vi中含有d个关键码。如果对于序列中任意两个对象Vi

和Vj(0

i<j

n-1)都满足：则称序列对关键码(K1,K2,…,Kd)有序。其中，K1称为最高位关键码，Kd

称为最低位关键码。如果关键码是由多个数据项组成的数据项组，则依据它进行排序时就需要利用多关键码排序。实现多关键码排序有两种常用的方法最高位优先MSD(MostSignificantDigitfirst)最低位优先LSD(LeastSignificantDigitfirst)最高位优先法通常是一个递归的过程：先根据最高位关键码K1排序,得到若干对象组，对象组中每个对象都有相同关键码K1。

再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。依此重复，直到对关键码Kd完成排序为止。最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组都参加排序。LSD和MSD方法也可应用于对一个关键码进行的排序。此时可将单关键码Ki看作是一个子关键码组：链式基数排序基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。在这种方法中，把单关键码Ki

看成是一个d元组：其中的每一个分量(1

j

d)也可看成是一个关键码。分量(1

j

d)有radix种取值，则称radix为基数。例如，关键码984可以看成是一个3元组(9,8,4)，每一位有0,1,…,9等10种取值，基数radix=10。关键码‘data’可以看成是一个4元组(d,a,t,a)，每一位有‘a’,‘b’,…,‘z’等26种取值，radix=26。针对d元组中的每一位分量，把对象序列中的所有对象,按的取值，先“分配”到rd个队列中去。然后再按各队列的顺序，依次把对象从队列中“收集”起来，这样所有对象按取值排序完成。如果对于所有对象的关键码K0,K1,…,Kn-1，依次对各位的分量，让j=d,d-1,…,1，分别用这种“分配”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“收集”完成后，所有对象就按其关键码的值从小到大排好序了。各队列采用链式队列结构，分配到同一队列的关键码用链接指针链接起来。每一队列设置两个队列指针：intfront[radix]指示队头，intrear[radix]指向队尾。为了有效地存储和重排

n

个待排序对象，以静态链表作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。基数排序的“分配”与“收集”过程第一趟614921485637738101215530790306第一趟分配（按最低位i=3）re[0]re[1]re[2]re[3]re[4]re[5]re[6]re[7]re[8]re[9]614738921485637101215530790306fr[0]fr[1]fr[2]fr[3]fr[4]fr[5]fr[6]fr[7]fr[8]fr[9]第一趟收集530790921101614485215306637738基数排序的“分配”与“收集”过程第二趟614921485637738101215530790306第二趟分配（按次低位i=2）re[0]re[1]re[2]re[3]re[4]re[5]re[6]re[7]re[8]re[9]614738921485637101215530790306fr[0]fr[1]fr[2]fr[3]fr[4]fr[5]fr[6]fr[7]fr[8]fr[9]第二趟收集530790921101614485215306637738基数排序的“分配”与“收集”过程第三趟614921485637738101215530790306第三趟分配（按最高位i=1）re[0]re[1]re[2]re[3]re[4]re[5]re[6]re[7]re[8]re[9]614738921485637101215530790306fr[0]fr[1]fr[2]fr[3]fr[4]fr