算法课件-第9章(内排序)

第九章内排序★基本概念★插入排序★冒泡排序★选择排序★计数排序★希尔排序★堆排序★快速排序★合并排序★基数排序第九章内排序★基本概念★插入排序★冒泡排序★选择设含有n个记录的文件{R1,R2,…，Rn

},其相应的关键字为{K1,K2,…，Kn

}，需确定一种排列P(1),P(2),…,P(n),使其相应的关键字满足如下的递增(或递减)关系：KP(1)≤KP(2)≤KP(3)≤…≤KP(n)即，使上述文件成为一个按其关键字线性有序的文件{RP(1),RP(2),…，RP(n)},这样一种运算称为排序。9.1基本概念如果在排序期间具有相同关键字的记录的相对位置不变，则称此方法是稳定的。排序：排序的稳定性：设含有n个记录的文件{R1,R2,…，R即，1)K(i)≤K(i+1)(1≤i≤n-1)2)若在输入文件中i<j,且Ki=Kj,则在经过排序后的文件中仍Ri先于Rj排序内排序：整个排序过程都在内存进行的排序。外排序：当文件很大以至于内存不足以存放全部记录，在排序过程中需要对外存进行存取访问。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97即，1)K(i)≤K(i+1)(1≤i≤n-内部排序的方法

在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。

内部排序的过程是一个逐步扩大记录的有序序列长度的过程。使有序区中记录的数目增加一个或几个的操作称为一趟排序。存放待排序数据的数据结构：typedefstruct{intkey;datatypeotheritem;//其他域}records;typedefstructrecordsList[n+1];内部排序的方法使有序区中记录的数目增加一个或几个的逐步扩大记录有序序列长度的方法大致有下列几类：1.插入类:将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；2.交换类:通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；3.选择类:从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；4.归并类:通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度；5.其它方法。逐步扩大记录有序序列长度的方法大致有下列几类：1.插入类:内排序插入类排序直接插入排序折半插入排序希尔排序交换类排序冒泡排序快速排序选择类排序选择排序堆排序归并类排序归并排序其他排序计数排序基数排序内插入类排序直接插入排序折半插入排序希尔排序交换类排序冒泡排9.2计数排序对每个记录计算文件中有多少个其它记录的关键字大于该记录的关键字值，从而找到该记录的正确排序位置。keyinfocount设一个记录有三个域：关键字域该记录的其他信息域计数域排序算法的思想：9.2计数排序对每个记录计算文件中有多少个其它记录的关键字for(i=1;i<n;i++)for(j=i+1;j<=n;j++)if(R[i].key)<R[j].key)R[i].count=R[i].count+1;elseR[j].count=R[j].count+1;}voidcountsort(ListR,intn){for(i=1;i<=n;i++)R[i].count=1;//对所有元素的count域置1；算法如下：for(i=1;i<n;i++)voi设文件有n个记录，则外循环：i=1时，内循环要做n-1次比较；i=2时，内循环要做n-2次比较；…i=n-1时，内循环要做1次比较；总的比较次数为(n-1)+(n-2)+…+1=n(n-1)/2算法性能分析：所以，算法所需时间为O(n2)，由于不需要记录移动和额外空间，同时算法简单，当n较小时，可采用本算法。设文件有n个记录，则外循环：算法性能分析：所以，算法例关键字序列{46，55，13，42，44，17，05，70}关键字4655134244170570初始化11111111i=131222221i=232333331i=332733341i=432753451i=532754561i=632754671i=732754681例关键字序列{46，55，13，42，44，17，05，79.3直接插入排序假设在排序过程中，记录序列R[1..n]的状态为：

则一趟插入排序的基本思想为：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。显然，完成这个“插入”需分三步进行：1．查找R[i]的插入位置j+1；2．将R[j+1..i-1]中的记录后移一个位置；3．将R[i]复制到R[j+1]的位置上。9.3直接插入排序假设在排序过程中，记录序列R[1..n]直接插入排序：利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三个要点：

1.从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i]；{设置“哨兵”}j=i-1;while(R[0].key<R[j].key)j=j-1;{//从后往前找}Return(j+1);{返回R[i]的插入位置为j+1}2.对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；while(R[0].key<R[j].key){R[j+1]=R[j];j=j-1;}3.i=2，3，…,n,实现整个序列的排序。直接插入排序：利用顺序查找实现“在R[1..i-1]中查找R排序算法如下：voidinsort(Listr,intn){//r为给定的表，其记录为r[i]，i=0，1，…，n，x为暂存单元。for(i=2;i<=n;i++){r[0]=r[i];//r[0]作为标志位j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j--;}//j从i-1至0，r[j].key与r[i].key进行比较r[j+1]=r[0];}}//insort排序算法如下：排序的时间分析：

实现排序的基本操作有两个：（1）“比较”序列中两个关键字的大小；（2）“移动”记录。对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：“移动”的次数：

总的说来，直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2/4，所以直接插入排序的时间复杂度为O(n2)。“比较”的次数：“移动”的次数：

2(n-1)排序的时间分析：

最坏的情况（关键字在记录序列中逆序有序9.4折半插入排序排序算法的思想：由于直接插入排序的内循环(从1到i-1)的查找(或说是比较)是在(部分)有序表的环境下进行的，所以内循环用“折半查找法”，比用顺序查找法快。9.4折半插入排序排序算法的思想：由于直接插入排序算法描述如下：voidbinsort(Listr,intn){for(i=2;i<=n;i++){r[0]=r[i];low=1;high=i-1;while(low<=high){m=(low+high)/2;ifr[0].key<r[m].keyhigh=m-1;elselow=m+1;}for(j=i-1;j<=low;j--)r[j+1]=r[j];//把从第low起到第i-1各记录后移r[low]=r[0];//将第i个记录插入}}//binsort算法描述如下：9.5冒泡排序排序算法的思想：比较k1和k2,如果这些关键字的值不符合排序顺序,就交换k1和k2；然后对记录k2和k3,k3和k4等等进行相同的工作。直到kn-1和kn为止,到此得到一个最大(或最小)关键字值存在kn的位置上(通常将此过程叫做一趟)。重复这个过程,就得到在位置kn-1,kn-2等处的适当记录,使得所有记录最终被排好序。

例如:将5个记录的关键字7,4,8,3,9进行冒泡排序。排序后k1≤k2≤…≤kn(n=5)。7443347344837773888899999①②③④

因为到第四趟就没有交换的偶对了,所以整个排序结束。9.5冒泡排序排序算法的思想：比较k1和k2,如果这些关算法描述如下:voidbubblesort(Listr,intn){for(m=1;m<=n;m++)scanf(“%d”,r[m]);k=n;do{all=〝T〞;//all=T,标志没有交换的;all=F,标志有交换的for(m=1;m<=k-1;m++){i=m+1;if(r[m]>r[i]){max=r[m];r[m]=r[i];r[i]=max;all=〝F〞;}}k--;}while((all==〝F〞)&&(k!=1)}冒泡排序的结束条件为：最后一趟没有进行“交换”。冒泡排序是一种稳定的排序算法。算法描述如下:冒泡排序的结束条件为：最后一趟没有进行“交换”时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：“移动”的次数：n-10

最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：“移动”的次数：

时间分析:“比较”的次数：“移动”的次数：最坏的情况（关键9.6希尔排序基本思想：对待排序记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序,待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。假设将n个记录分成d个子序列，则这d个子序列分别为：{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]}其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。9.6希尔排序基本思想：对待排序记录序列先作“宏观例如：

第二趟希尔排序，设增量d=3

第三趟希尔排序，设增量d=1例如：

第二趟希尔排序，设增量d=3

希尔排序的算法描述如下:voidShellInsert(Listr,intd)//本算法对直接插入算法作了以下修改：//1.前后记录位置的增量是d，而不是1；//2.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。{for(i=d+1;i<=n;i++)if(r[i]<r[i-d])//需将r[i]插入有序增量子表{r[0]=r[i];//暂存在R[0]j=i-d;while((j>0)and(r[0]<r[j])){r[j+d]=r[j];//记录后移，查找插入位置j=j-d;}r[j+d]=r[0];//插入}}for(i=2;i<=n;i++){r[0]=r[i];j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j=j-1;}r[j+1]=r[0];}希尔排序的算法描述如下:for(i=2;i<=n;iVoidShell_sort(Listr,intdlta,intt);{//按增量序列dlta[0..t-1]对顺序表r作希尔排序for(k=0;k<=t;k++)ShellInsert(r,dlta[k]);}VoidShell_sort(Listr,intd

先取定一个两项之间的距离d1(≤n,其中n为整个表的长度),反复比较每两个相距d1的项,直到以d1为距离划分的组排序好为止(至此一趟排序完成);然后取d2<d1,再继续以d2为距离反复比较每两个相距为d2的项,…,依此类推.取每个di+1<di,直到dt=1为止。例如,假设文件中8个记录的关键字,我们不采用顺序比较,而是先从第一个关键字开始每隔4个关键字进行比较;同理第二个也从隔4个关键字进行比较,第三个…,第四个…,依次做下去.题中选d1=4,从小到大排序:例先取定一个两项之间的距离d1(≤n,其中n为整个表的初始d1=44655134294170570

55与1713与05第一趟后结果4617054294551370

46与0594与1346与13第二趟后结果d2=20517134246559470

13,46分别交换两次0513174246557094

第三趟后结果d3=113与1794与70初始d1=446551342NorthChinaElectricPowerUniversity9.7选择排序基本思想：首先在n个记录中选择一个具有最小或最大关键字的记录，将选出的记录与记录集合中的第一个记录交换位置。然后在r[2]至r[n]中选择一个最小或最大的值与r[2]交换位置，…，依此类推，直至r[n-1]和r[n]比较完毕。voidslsort(Listr,intn)//每次从r[j](j=i+1,…n)中选了最小值，与r[i](i=1,2,…,n-1)交换，进行分类{for(i=1;i<=n-1;i++)//共进行n-1趟排序{m=i;for(j=i+1;j<=n;j++)if(r[j].key<r[m].key)m=j;//m指示关键字最小的记录的序号if(m!=i){x=r[i];r[i]=r[m];r[m]=x;}}}NorthChinaElectricPowerUni例关键字序列{055，55，60，13，05，94，17，70},利用选择排序算法进行排序。关键字r[1]055r[2]55r[3]60r[4]13r[5]05r[6]94r[7]17r[8]70i=1,m=505556013055941770i=2,m=405136055055941770i=3,m=705131755055946070i=4,m=405131755055946070i=5,m=505131755055946070i=6,m=705131755055609470i=7,m=805131755055607094不稳定例关键字序列{055，55，60，13，05，94，17，算法的复杂性分析：当选则第一个最小值时需进行n-1次比较，选第二个最小值时需进行n-2次比较，…，选n-1个最小值时需进行n-(n-1)次比较，所以总的比较次数为(n-1)+(n-2)+…+2+1=n(n-1)/2故排序n个记录需要时间为O(n2)。由于执行一次交换，需三次移动记录，最多交换n-1次，故最多移动次数为3(n-1)算法的复杂性分析：由于执行一次交换，需三次移动记录，最多交换NorthChinaElectricPowerUniversity9.8堆排序1.定义：堆是由n个记录的线性序列{R1,R2,…，Rn};其关键字序列{k1,k2,…，kn},满足下列特性时，称之为堆。或若将此数列看成是一棵完全二叉树的顺序存储表示，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于(或大于)左、右子树根结点的值。下列两个序列为堆，对应的完全二叉树如下图{96，83，27，38，11，09}9683273811091236248547305391ki≤k2iki≤k2i+1ki≥k2iki≥k2i+1大根堆小根堆{12，36，24，85，47，30，53，91}NorthChinaElectricPowerUni1)首先将一个关键字集合用完全二叉树的形式排列;如给定关键字集合为{46,55,13,42,94,17,05,70}组成的完全二叉树如下：46551342941705702.建堆的过程：1)首先将一个关键字集合用完全二叉树的形式排列;465512)开始建堆：采用筛选法，逐步将大的关键字筛到堆底。筛选法的思想是这样的：

►假设集合r有m个结点，从某个结点i（第一次i=[m/2]）开始筛选;

►先看第i个结点的左右子树，设第i个结点的左子树为kj,右子树为kj+1。若kj<kj+1则沿左分支筛，否则沿右分支筛选，即（j=j+1）。将ki与kj进行比较，若ki>kj则对调，小的上来大的下去。

►

然后kj作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。2)开始建堆：采用筛选法，逐步将大的关键字筛到堆底。第一次调用筛选法：m=8,i=[m/2]=4,从i=4开始，看k4的左右子树，仅有左子树，因此42与70比较，42<70，所以不变。j=i*2=8，i=j，再向下看，此时的i无左右子树,所以返回，如右图所示。4655134294170570第二次调用筛选法：i=3,k3=13,13的左右子树为17和05，因17>05,故沿右子树比较，13>05,进行对调，此时13无左右子树，所以返回。4655134294170570NorthChinaElectricPowerUniversity0513{46,55,13,42,94,17,05,70}{46,55,05,42,94,17,13,70}

►先看第i个结点的左右子树，设第i个结点的左子树为kj,右子树为kj+1。若kj<kj+1则沿左分支筛，否则沿右分支筛选，即（j=j+1）。将ki与kj进行比较，若ki>kj则对调，小的上来大的下去。

►然后kj作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。第一次调用筛选法：m=8,i=[m/2]=4,从i=4开始，第三次调用筛选法：i=2,k2=55,因为42<94，所以沿左子树筛选，42<55,进行对调，此时55还有左子树70，因55<70，所以不变，再向下70无左右子树，所以返回，此时二叉树如右图所示。4655054294171370第四次调用筛选法：i=1,k1=46,因为05<42，所以沿右子树筛选，05<46,进行对调，此时46还有左右子树17,13，因13<17，所以再沿右子树筛选，13<46,所以对调，46无左右子树，所以返回，此时二叉树如右图所示。4642055594171370NorthChinaElectricPowerUniversity554246054613{46,42,05,55,94,17,13,70}{05,42,13,55,94,17,46,70}

►先看第i个结点的左右子树，设第i个结点的左子树为kj,右子树为kj+1。若kj<kj+1则沿左分支筛，否则沿右分支筛选，即（j=j+1）。将ki与kj进行比较，若ki>kj则对调，小的上来大的下去。

►然后kj作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。第三次调用筛选法：i=2,k2=55,因为42<94，所以3.建堆的算法voidsift(Listr,intk,intm)//对m个结点的集合r从某个结点i=k开始筛选，如果r[j]>r[j+1](j=2i)，则沿右//分支筛，否则沿左分支筛。把关键字大的筛到堆底。{i=k;j=2*i;x=r[i];r[i]=x;//将x放在适当的位置}//siftNorthChinaElectricPowerUniversitywhile(j<=m){if((j<m)&&(r[j].key>r[j+1].key))//左子树>右子树j++;//沿右筛}if(x.key>r[j].key){r[i]=r[j];i=j;j=2*i;

}//将关键字小的换到i位置，x.key再准备与下一层的比较elsej=m+1;//强制跳出while循环3.建堆的算法NorthChinaElectricP以上面建的堆为例,说明重建堆的执行过程。输出0570r[1]0542135594174670704213559417460513421755947046重建堆输出1346r[1]46421755947005重建堆050570X{05,42,13,55,94,17,46,70}{13,42,17,55,94,70,46,05}134613704.堆排序过程以上面建的堆为例,说明重建堆的执行过程。输出0570r[1]1317424655947005输出1770r[1]13704246559405重建堆1713425546709405输出4294r[1]17139455467005重建堆{17,42,46,55,94,70,13,05}X177017{42,55,46,70,94,17,13,05}429442701317424655947005输出1770r[1]13704217134655947005输出4670r[1]42171370559405重建堆4642171355709405输出5594r[1]46421713947005重建堆{46,55,94,70,42,17,13,05}467046X{55,70,94,46,42,17,13,05}55945570704217134655947005输出4670r[1]42177094554642171305输出7094r[1]94554642171305退出K循环打印949470554642171305{70,94,55,46,42,17,13,05}709470{94,70,55,46,42,17,13,05}7094554642171305输出7094r[1]9455堆排序的过程：用拔尖的方法将堆顶输出,把最后一个元素送到树根上,然后从i=1开始,调用筛选算法重新建堆,再将堆顶输出将最后一个送到树根,再重新建堆。如此反复,直到得到最后全部排序好的关键字序列。算法描述如下：voidheapsort(Listr,intn)//对n个结点的集合r进行堆排序{for(i=n/2;i>=1;i--)sift(r,i,n);//从第[n/2]个结点开始进行筛选建初始堆}//headsortfor(k=n;k>=2;k--){t=r[k];r[k]=r[1];r[1]=t;printf(“%d”,r[k]);sift(r,1,k-1);}//重建堆printf(“%d”,r[1]);//输出最后一个元素即最大元素堆排序的过程：用拔尖的方法将堆顶输出,把最后一个元素送到树根NorthChinaElectricPowerUniversity1）对深度为h的堆，“筛选”所需进行的关键字比较的次数至多为2(h-1);5.堆排序的时间复杂度分析2）对n个关键字，建成深度为

的堆，所需进行的关键字比较的次数不超过：h=(log2n」+1)NorthChinaElectricPowerUni2（log2(n-1)」+log2(n-2)」+…+log22）<2n(log2n」)共n-2项相加因此，堆排序的时间复杂度为O(nlogn)3）调整“堆顶”n-1次，总共进行的关键字比较的次数不超过：2（log2(n-1)」+log2(n-2)」+例：关键字序列{3，27，36，027}32736027已为初始堆输出3027r[1]02727363输出027此时为堆36r[1]36273027输出2736r[1]重建堆2736302736302727退出K循环打印3636302727输出序列为：3，027，27，36不稳定6.堆排序的稳定性分析例：关键字序列{3，27，36，027}32736027已NorthChinaElectricPowerUniversity9.9快速排序快速排序又称分划交换排序，设输入文件有n个记录R1,R2,…,Rn,它们对应的关键字是k1,k2,…,kn。该方法先取序列中任一关键字K(通常取第一个)，然后用K从两头到中间进行比较/交换，就能形成一个分划：凡是小于等于K的被移到左边，凡是大于K的被移到右边。1.快速排序的定义NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity2.快速排序步骤2)从最末项kn开始起指针j倒向前找到第一个kj<x.key或i≥j时，则判i<j?是，kj送ki，i=i+1；1)选定k1为起点，且将k1送x；3)从ki项起指针i向前扫描，找到第一个ki>x.key或i≥j时，则判i<j?是，ki送kj，j=j-1；4)上述过程进行到i=j时停止，将x送ki，同时i=i+1；j=j-1,即x在正确位置上,并分K为K1和K2两个子集合；5)重复调用上述过程，直到将整个集合排序好为止。NorthChinaElectricPowerUni例:初始关键字[4655134294051770]将46→xij第一次交换后[

55134294051770]ji第二次交换后[17551342940570]ji第三次交换后[17

134294055570]j第四次交换后[1705134294

5570]jii至此，完成第一趟排序1755059446例:初始关键字[46551342940第五趟排序后0513174246557094第一趟排序后[17051342]46[945570]第二趟排序后[1305]17[42]46[945570]第三趟排序后[05]1317[42]46[945570]第四趟排序后0513174246[7055]94

例:初始关键字[4655134294051770]接上例第一趟排序后[170513voidqksort(Listr,intL,intP)//将r[L]至r[P]进行排序{}//qksort3.快速排序算法do{while((r[j].key>=x.key)&&(j>i))j--;//从表尾一端开始比较if(i<j){r[i]=r[j];i++;while((r[i].key<=x.key)&&(i<j))i++;//再从表的始端起进行比较if(i<j){r[j]=r[i];j--;}}}while(i!=j);i=L;j=P;x=r[i];//置初值r[i]=x;i++;j--;//一趟快排结束，将x移至正确位置

if(L<j)qksort(r,L,j);

//反复排序前一部分if(i<P)qksort(r,i,P);

//反复排序后一部分voidqksort(Listr,intL,inNorthChinaElectricPowerUniversity快速排序是目前内部排序中最快的方法。若关键字的分布式均匀的，可以粗略的认为每次划分都把文件分成长度相等的两个文件。4.快速排序算法的性能分析但如果原来的文件是有次序的，时间复杂性为O(n2)。因此，快速排序偏爱一个无次序的文件。令T(n)为分类n个记录所需之比较次数,设n=2k，则k=log2n，有：T(n)≤cn+2T(n/2)(其中cn为进行一趟排序所需的时间)T(n)≤cn+2(cn/2+2T(n/4))≤2cn+4T(n/4)……≤kcn+2kT(1)=O(nlog2n)NorthChinaElectricPowerUni5.快速排序算法的稳定性分析例：关键字序列{5，2，02}ij第一次交换后[02202]5→xj第二次交换后[022]02

j至此，完成排序，序列为{02,2,5}第一次交换[022]5ji02→x第一趟无交换25第二趟5不稳定i025.快速排序算法的稳定性分析例：关键字序列{5，2，02例K={46,79,56,38,40,84}

（1）它的初始堆是：

（2）快速排序第一趟结果：（1）467956384084384056794684（2）40，38，46，56，79，84例K={46,79,56,38,40,84}

（1）它的初NorthChinaElectricPowerUniversity归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列

归并为一个有序序列。

9.10归并排序NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity2-路归并排序算法voidmerge(intL,intm,intn,Listr,Listr2)//表r可看成两个文件首尾相接的两个文件，即需合并的两个文件为r，合并到第三个表r2上{i=L;k=L;j=m+1;//从L开始while(i<=m)&&(j<=n)//当两个表都有内容未排完时{if(r[i].key<=r[j].key){r2[k]=r[i];i++;}else{r2[k]=r[j];j++;}k++;}if(i>m)COPY(r,j,n,r2);//将r[j]至r[n]照抄至r2上，即表1完照抄第2个表elseCOPY(r,i,m,r2);//将r[i]至r[m]照抄至r2上}//mergeNorthChinaElectricPowerUniNorthChinaElectricPowerUniversity采用2-路归并算法进行排序的思想：先将初始文件分成长度为１的n个子文件并且合并到相邻的子文件。则可以得到大约n/2个长度为2的子文件，重复上述过程，直到仅剩下一个长度为n的文件。

下面的例子显示了这个排序过程(直接合并排序),每个子文件用方括号括起来。初始文件2557483712928633n=8个子文件[25][57][48][37][12][92][86][33]第一趟[2557][3748][1292][3386]

第二趟[25374857][12338692]

第三趟[1225333748578692]NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity设一个辅助数组aux,被用于保存合并x的两个子数组所得的结果。变量size用于控制被合并的子文件的大小。因为每次被合并的两个子文件总是x的两个子数组,所以必须用变量来指出子数组的上下界。ib1和ub1分别表示待合并的第一个子文件的下界与上界,ib2和ub2分别表示待合并的第二个子文件的下界和上界.变量i和j用来指示待合并的两个子文件(即源文件)的元素,变量k用于指示合并得到的目标子文件的元素。归并排序算法：voidmergsort(Listx,intn)//x数组用来存放待合并的文件，n为待合并子文件的个数{size=1;//置被合并的文件长度为1;while(size<n){ib1=1;//为第一个文件初始化下界k=1;//k是辅助数组的标号NorthChinaElectricPowerUniNorthChinaElectricPowerUniversitywhile(ib1+size<=n)//checkiftherearetwofilestomerge{ib2=ib1+size;ub1=ib2-1;if(ib2+size-1>n)ub2=n;elseub2=ib2+size-1;merge(ib1,ub1,ub2,x,aux);ib1=ub2+1;}//复制最后一个文件i=ib1;while(k<=n){aux[x]=x[i];k++;i++;}NorthChinaElectricPowerUni//调整x和问题规模for(k=1;k<=n;k++)x[k]=aux[k];size=2*size;}//whilesize<ndo}//mergsort从上面的算法可以看出size变量的取值不超过log2n个，对size的每一个取值都扫描n个记录,所以归并排序的时间复杂性为O(nlog2n)//调整x和问题规模从上面的算法可以看出size变量的取值不NorthChinaElectricPowerUniversity9.11基数排序借助“多关键字排序”的思想来实现“单关键字排序”的算法。1.多关键字的排序假设有n个记录的序列{R1,R2,…Rn},每个记录Ri中含有d个关键字(Ki0,Ki1,…,Kid-1),则称上述记录序列对关键字(Ki0,Ki1,…,Kid-1)有序是指:对于序列中任意两个记录Ri和Rj(1≤i<j≤n)都满足下列(词典)有序关系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0被称为“最主”位关键字，Kd-1被称为“最次”位关键字。实现多关键字排序通常有两种作法:最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序,…，依次类推,直至最后对最次位关键字排序完成为止。1.多关键字的排序NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。对K2排序1,2,152,3,183,1,202,1,203,2,30对K1排序3,1,202,1,201,2,153,2,302,3,18对K0排序1,2,152,1,202,3,183,1,203,2,30无序序列3,2,301,2,153,1,202,3,182,1,20例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity2.链式基数排序

假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时,可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。例如：对下列这组关键字{209,386,768,185,247,606,230,834,539}首先按其“个位数”取值分别为0,1,…，9,“分配”成10组之后按从0至9的顺序将它们“收集”在一起;然后按其“十位数”取值分别为0,1,…，9“分配”成10组，之后再按从0至9的顺序将它们“收集”在一起;最后按其“百位数”重复一遍上述操作，便可得到这组关键字的有序序列。2.链式基数排序NorthChinaElectricPowerUni4)对每个关键字位均重复2)和3)两步。在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：待排序记录以指针相链，构成一个链表；

2)“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；3)“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;3.基数排序步骤在计算机上实现基数排序时，为减少所需辅助存储空间，应例如,有一组关键字｛179,208,306,093,859,984,055,009,271,033｝这些关键字是10进制数,基数rd=10,位数d=3.文件的初始状态是一个单链表,表头指针指向第一个记录:179984093009005306859271208033例如,有一组关键字｛179,208,306,093,859,

第一趟分配对最低位关键字(个位数)进行,改变记录的指针值将文件中的记录分配至10个队列(桶)中去,每个队列中的记录关键字的个位数均相等，如图(a)所示,其中f[i]和e[i]分别为第i个队列的头指针和尾指针;第一趟收集是改变所有非空队尾记录的指针域,令其指向下一个非空队列的队头记录,重新将10个队列中的记录链成一个链表文件:E(9)E(8)E(7)E(6)E(5)E(4)E(3)E(2)E(1)E(0)末尾指针前沿指针009859179(a)第一趟分配之后F(9)F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F(8)208306055984093271033(b)第一趟收集后的链式271306984179208033055859093009179984093009005306859271208033第一趟分配对最低位关键字(个位数)进行,改变记录的指306859033179271009055984208093(d)第二趟收集后的链式

第二趟分配,第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的,其过程和个位数相同,如图(c)所示,至此,排序完毕。若想从大到小排序,分配的过程与上述相同,收集的过程是从第e[9]队列向第e[0]方向收集。E(9)E(8)E(7)E(6)E(5)E(4)E(3)E(2)E(1)E(0)末尾指针009208306前沿指针F(9)(c)第二趟分配之后F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F(8)984093055033859271179271306984179208033055859093009306859033179271009055984208093E(9)E(8)E(7)E(6)E(5)E(4)E(3)E(2)E(1)E(0)末尾指针093055033(e)第三趟分配之后前沿指针F(9)F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F(8)208179271009306984859009208093306271055179859033984(f)第三趟收集后的有序文件306859033179271009055984208093E(9)E(8)E(7)E(6)E(5)E(4)E(3)E(提醒注意：１．“分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；２．为查找使用，该链表尚需应用算法Arrange将它调整为有序表。提醒注意：NorthChinaElectricPowerUniversity基数排序的算法简单描述如下：数据类型定义如下：#defineMAX_NUM_OF_KEY8//关键字项数（位数）的最大值#defineRADIX10#defineMAX_SPACE10000typedefstruct{KeysTypekeys[MAX_NUM_OF_KEY];//关键字InfoTypeotheritems;//其他数据项intnext;}SLCell;//静态链表的结点类型typedefstruct{SLCellr[MAX_SPACE];//静态链表的可利用空间，r[0]为头结点intkeynum;//记录的当前关键字个数intrecnum;//静态链表的当前长度}SLList;//静态链表的类型typedefintArrType[RADIX];//指针数组类型NorthChinaElectricPowerUniNorthChinaElectricPowerUniversityvoidDistribute(SLCell&r,inti,ArrType&f,ArrType&e){/*静态链表L的r域中记录已按（keys[0],…,keys[i-1]）有序。本算法按第i个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同。f[0‥RADIX-1]和e[0‥RADIX-1]分别指向各子表中第一个和最后一个记录。*/for(j=0;j<RADIX-1;j++)f[j]=0;//各子表初始化为空表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;elser[e[j]].next=p;e[j]=p;//将p所