数据结构课程讲义8ppt课件省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件

第八章排序概述插入排序交换排序选择排序归并排序分配排序

外排序

1/106§1内排序(Sorting)？简单地说，排序就是将一组杂乱无章数据按一定规律排列起来（递增或递减）。排序是计算机中经常碰到操作，通常称为分类或整序。2/106排序几个基本概念数据表(DataList)

待排序数据对象有限集合。关键字(Key)作为排序依据数据对象中属性域。主关键字不一样数据对象若关键字互不相同，则这种关键字称为主关键字。排序确实切定义使一组任意排列对象变成一组按关键字线性有序对象。用于排序测度关键字通常称为排序码。3/106排序几个基本概念排序算法稳定性判断标准：排序码相同数据对象在排序过程中是否保持前后次序不变。如2,2*,1，排序后若为1,2*,2则该排序方法是不稳定。内排序与外排序区分标准：排序过程是否全部在内存进行。排序时间开销

它是衡量算法好坏最主要标志。通惯用算法执行中数据比较次数和数据移动次数来衡量。

4/106排序方法有很多，但简单地判断那一个算法最好，方便能够普遍选取则是困难。评价排序算法好坏标准主要有两条：算法执行所需要时间和所需要附加空间。另外，算法本身复杂程度也是需要考虑一个原因。排序算法所需要附加空间普通都不大，矛盾并不突出。而排序是一个经常执行一种运算，往往属于系统关键部分，所以排序时间开销是算法好坏最主要标志。5/106排序亦称分类，是计算机进行数据处理一个基本运算，其功效是将一个数据元素无序序列调整为一个有序序列。目标是到达当计算机中数据经过排序后，提升工作效率和质量。是在线性表上施加操作。

排序码就是指作为排序依据数据项。数据元素能够有多个排序码。

排序准确定义：

有n个统计（元素）：{R1，R2，R3，………，Rn}及其对应排序码序列：{K1，K2，K3，…………Kn}6/106所确定1，2，………….n一个排列p1,p2,p3,……,pn，使得对应排序码满足非递减（或非递增）关系：Kp1≤Kp2≤Kp3≤……≤Kpn或Kp1≥Kp2≥Kp3≥……≥Kpn即成为：{Rp1,Rp2,Rp3,……,Rpn}自然，不一样排序策略就得到不一样排序过程；

策略相同但排序所采取排序方法不一样，都会有不一样排序算法。常见排序策略和方法有：7/106直接插入排序shell插入排序（缩小增量排序）

插入策略二分插入排序表插入排序直接交换排序（冒泡排序）

交换策略快速排序直接选择排序

选择策略堆排序

归并策略

分配策略基数排序8/106为简单起见，数据存放结构采取统计数组形式。统计数组类型说明以下：typedefstruct{keytypekey;datatypeother;}rectype;

rectypeR[n];

其中n为统计总数加19/106§2插入排序基本原理，每步将一个待排序对象，按其关键字大小，插入到前面已经排好序一组对象适当位置上，直到对象全部插入为止。直接插入排序(InsertSort)希尔排序(ShellSort)10/1062.1直接插入排序(InsertSort)

基本思想：当插入第i个对象时，前面V[0],V[1],…,V[i-1]已经排好序，此时，用v[i]关键字与V[i-1],V[i-2],…关键字次序进行比较，找到插入位置即将V[i]插入，原来位置上对象向后顺移。11/106直接插入排序举例i(0)(1)(2)(3)(4)(5)temp[21]254925*1608251[2125]4925*1608492[212549]25*160825*3[212525*49]1608164[16212525*49]08085[0816212525*49]12/106直接插入排序算法INSERTSORT(rectypeR[]){inti,j;for(i=1;i<n;i++){temp＝R[i];j＝i-1;while(j>=0&&temp.key<R[j].key){R[j+1]＝R[j];j++;}R[j+1]＝temp;}}13/106算法中引入附加统计temp作用：是进入查找循环之前，它保留了R[i]副本，使得不至于因统计后移而丢失R[i]中内容。14/106算法分析直接插入排序算法由两重循环组成，对于有n个统计排序，内循环表明完成一趟排序所需进行统计关键字间比较和统计后移。若初始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字比较，所以总比较次数为n-1。在while循环之前和之中，最少要移动统计两次，所以总比较次数为2(n-1)。若初始时关键字递减有序，这是最坏情况。这时统计比较和移动次数分别为：15/106直接插入排序稳定性直接插入排序是一个稳定排序方法。原理：关键字相同两个对象，在整个排序过程中，不会经过比较而相互交换。16/1062.2希尔(shell)排序1959年由D.L.Shell提出，又称缩小增量排序(Diminishing-incrementsort)。基本思想：在插入排序中，只比较相邻结点，一次比较最多把结点移动一个位置。假如对位置间隔较大距离结点进行比较，使得结点在比较以后能够一次跨过较大距离，这么就能够提升排序速度。17/106希尔排序基本过程

设待排序对象序列有n个对象，首先取一个整数gap<n作为间隔，将全部对象分为gap个子序列，全部距离为gap对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然后缩小间隔gap，如取gap=gap/2，重复上述子序列划分和排序工作，直到最终取gap为1为止。18/106希尔排序示例i(0)(1)(2)(3)(4)(5)gap21254925*1608121--25*325--1649--0821160825*2549221-08-25216-25*-4908162125*2549308162125*2549108162125*254919/106希尔排序算法rectypeR[n+d1];intd[t];

SHELLSORT(rectypeR[],intd[]){inti,j,k,h;rectypetemp;k＝0;dl=1;

do{h＝d[k];for(i=h+dl;i<n+dl;i++){temp＝R[i];j＝i-h;while(temp.key<R[j].key){p[j+h]＝R[j];j＝j-h;}R[j+h]＝temp;}k++;}while(h!=1);}20/106为什么shell排序时间性能优于直接插入排序呢？因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所需比较和移动次数均较少。其次，当n值较小时，n和n2差别也较小，即直接插入排序最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开始时增量较大，分组较多，每组记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐降低，而各组记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新一趟排序过程也较块。21/106希尔排序中gap取法Shell最初方案是gap=n/2,gap=gap/2，直到gap=1.Knuth方案是gap=gap/3+1其它方案有：都取奇数为好；或gap互质为好等等。22/106希尔排序时间复杂度对希尔排序复杂度分析很困难，在特定情况下能够准确地估算关键字比较和对象移动次数，不过考虑到与增量之间依赖关系，并要给出完整数学分析，当前还做不到。Knuth统计结论是，平均比较次数和对象平均移动次数在n1.25与1.6n1.25之间。23/106希尔排序稳定性希尔排序是一个不稳定排序方法。如序列322*524/106§3交换排序两种常见交换排序冒泡排序(BubbleSort)快速排序(QuickSort)基本原理：每一次两两比较待排序统计排序码，只要是逆序统计对，则进行交换，直到全部逆序对都交换完为止。25/106冒泡排序基本思想首先依序比较n个待排序统计一端开始，依次两两比较排序码，只要是逆序，则交换，这么完成一趟交换排序，结果就是将最大（或最小）统计交换到最终面（或最前面）；然后其余统计同法进行两两比较，每一趟都将较大（小）元素交换到最终（前）面，一直进行下去，直到最终一个统计排完或没有要交换元素时候为止。3.1冒泡排序26/106冒泡排序基本过程首先从R[0]到R[n-1]对n个元素比较其排序码，对逆序元素进行交换，完成一趟排序时，将排序码值最到元素几交换到最终一个位置，即R[n-1]，该过程相当于一趟冒泡；然后，又从R[0]到R[n-2]中又进行一趟交换冒泡，这么一直进行下去，直到最终一个元素R[0]或某一趟没有交换元素为止。3.1，冒泡排序27/106冒泡排序示例i(0)(1)(2)(3)(4)(5)21254925*160810821254925*162081621254925*30816212525*4940816212525*4928/106冒泡排序算法voidbubblesort(R[]){for(i=0;i<n-2;i++){flag=1;for(j=n-1;j>=i;j++)if(R[j+1].key<R[j].key){t=R[j+1];R[j+1]=R[j];R[j]=t;Flag=0;}if(flag)break;}29/106冒泡排序时间复杂度考虑关键字比较次数和对象移动次数1、在最好情况下，初始状态是递增有序，一趟扫描就可完成排序，关键字比较次数为n-1，没有统计移动。2、若初始状态是反序，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字比较，且每次需要移动统计三次，所以，最大比较次数和移动次数分别为：冒泡排序方法是稳定。30/106快速排序基本思想在当前无序区R[l]到R[h]任意取出一个元素作为比较“基准”，以此为基准将当前无序序列划分为两个部分：一部分元素中全部元素排序码都小于基准元素；另一部分元素中全部元素排序码都大于基准元素，则基准元素所在位置就是该元素排序最终位置；然后同法依次对两部分元素进行分划，继续进行下去，直到得到一个有序序列为止。3.2快速排序31/106快速排序过程设置两个指示器i和j,其初值分别为i=l,j=h.不妨取第一个元素R[i](=R[l])为基准，并将其保留于变量x中。令j从h开始往前扫描，直到找到第一个排序码值小于x排序码值时候统计R[j],则将其移动到I位置上（即相当于将比基准小元素移动到左边）；然后，令i自i+1起往后扫描，直到找到第一个排序码值大于x排序码值时候统计R[i],则将其移动到j位置上（即相当于将比基准大元素移动到右边）；接着，又令j从j-1开始往前扫描、重复上述交替改变扫描方向，从两端各自向中间靠拢，直到i=j时，便是基准x最终位置，将其放在此位置上就完成了一次划分。3.2快速排序32/106快速排序示例4938659776132749’

38659776132749’273865977613

49’4938

9776136549’4938139776

6549’493813

76976549’4938134976496549’49temp33/106快速排序算法intPARTITION(rectypeR[],intl,inth){inti,j;rectypetemp;i=l;j=h;temp=R[i];do{while((R[j].key>=temp.key)&&(i<j))j--;if(i<j)R[i++]=R[j];while((R[i].key<=temp.key)&&(i<j))i++;if(i<j)R[j--]=R[i];}while(i!=j);R[i]=temp;returni;}

34/106QUICKSORT(rectypeR[],ints1,intt1){inti;if(s1<t1){i=PARTITION(R,s1,t1);QUICKSORT(R,s1,i-1);QUICKSORT(R,i+1,t1);}}35/106快速排序时间复杂度2、最好情况是每次所取基准都是当前无序区“中值”统计，划分结果是基准左右两个无序子区长度大致相等。考虑关键字比较次数和对象移动次数1、最坏情况是每次划分选取基准都是当前无序区中关键字最小（或最大）统计，划分结果是基准左边（或右边）为空，划分前后无序区元素个数降低一个，所以，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为36/106设C(n)表示对长度为n序列进行快速排序所需比较次数，显然，它应该等于对长度为n无序区进行划分所需比较次数n-1，加上递归地对划分所得左右两个无序子区进行快速排序所需比较次数。假设文件长度n=2k，k=log2n，所以有：37/106

快速排序统计移动次数不会大于比较次数，所以，快速排序最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。能够证实，快速排序平均时间复杂度也是O(nlog2n)。快速排序是不稳定排序方法。38/106§4选择排序两种常见选择排序直接选择排序堆排序基本原理:将待排序结点分为已排序(初始为空)和为未排序两组，依次将未排序结点中值最小结点插入已排序组中。39/106直接选择排序基本思想在全部统计中选择出排序码最小统计，将其与第一个元素交换；然后其余统计中选择出次小统计与第二个元素交换，一直进行下去；直到最终一个统计排完为止。4.1直接选择排序40/106直接选择排序过程首先从R[0]到R[n-1]中选择出最小统计，将其与R[0]交换；然后，又从R[1]到R[n-1]中选择出最小统计与R[1]交换；这么，当第i趟时从R[0]到R[i-1]就是已经排好序，直到最终一个元素R[n-1]排好为止。4.1直接选择排序41/106直

接

选择

排序

示

例4938659776132749’1338659776492749’1327659776493849’1327389776496549’1327384976976549’1327384949’9765761327384949’6597761327384949’65769742/106直接选择排序算法SELECTSORT(rectypeR[]){inti,j,k;rectypetemp;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(R[j].key<R[k].key)k=j;if(k!=i){temp=R[i];R[i]=R[k];R[k]=temp;}}}43/106直接选择排序时间复杂度2.当文件为正序时，移动次数为0，文件初态为反序时，每趟排序均要执行交换操作，总移动次数取最大值3(n-1)。直接选择排序是不稳定排序方法。1、不论初始状态怎样，在第i趟排序中选择最小关键字统计，需做n-i次比较，所以总比较次数为：44/1064.2堆排序因为直接选择排序过程中，每趟选择过程中所进行比较，都没有进行保留，从而造成了排序效率低下。于是引入树形结构排序。

堆排序引入45/1064.2堆排序就是树形结构排序。也就是体育比赛中锦标赛方式。其排序方法以下：

首先对

n个统计排序码进行两两比较，得到[n/2]个较小元素，然后再将其进行两两比较，得到[n/4]个较小元素，依此进行下去，直到找到最小排序码元素为止，则即完成一趟选择，同法，每趟选择都选择出最小元素，直到最终一个元素时为止，即完成了排序。

1、锦标赛排序46/1064.2堆排序显然，为了保留每次比较结果，都不得不需要大量辅助存放空间，于是为了填补这个缺点，1964年由Willioms提出了只需要一个辅助存放空间即可完成堆排序。

1、锦标赛排序47/1064.2堆排序堆定义：n个元素序列所对应排序码序列{K1,K2,K3,……,Kn},当且仅当Ki≤K2iKi≤K2i+1或Ki≥K2iKi≥K2i+12、堆排序48/1064.2堆排序称为小根堆（大根堆）。由此，若序列{K1,K2,K3,……,Kn}是小根堆，则堆顶元素（即为完全二叉树根）必为序列中全部元素最小（最大）值。2、堆排序49/1064.2堆排序每次在得到一个堆之后，输出堆顶元素后，使得剩下n-1个元素序列再建成一个堆，则得到n个元素次小元素。继续进行下去，直到得到一个有序序列为止。由此可见：实现堆排序需要处理两个问题：堆排序基本思想50/1064.2堆排序（1）怎样由一个无序序列建立一个堆；（2）怎样在输出堆顶元素之后，调整剩下元素成为一个新堆。

堆排序基本思想51/1064.2堆排序对于第二个问题，在堆一个堆输出堆顶元素之后，而且用最终一个元素代替后，就会破坏堆特征，故需要进行适当调整。依据堆定义，只需要依次与左右孩子进行比较，将左右孩子中较小者与其根结点进行交换，也就相当于将根结点往下“筛”，直到每一棵子树都是小根堆为止。

堆排序基本思想52/1064.2堆排序

对于第一个问题，从一个无序序列建立成堆过程是一个重复“筛选”过程。

若将此序列组织成为一棵完全二叉树，则最终一个非叶子结点就是第[n/2]个元素。所以我们筛选建堆过程只需要从第[n/2]处开始。循环到根结点时，调整之后二叉树就是全部元素组成小根堆。

堆排序基本思想53/106101556253070101556253070小根堆示例54/106705630251510705630251510大根堆示例55/106可见：堆排序第一个工作是建堆，即把整个统计数组R[1]到R[n]调整为一个堆。显然,只有一个结点树是堆，而在完全二叉树中，全部序号i>=low(n/2)结点都是叶子，所以以这些结点为根子树都已是堆。这么，我们只需依次将序号为low(n/2)，low(n/2)-1，...，1结点作为根子树都调整为堆即可。我们以大根堆为例进行说明56/106

若已知结点R[i]左右子树已是堆，怎样将以R[i]为根完全二叉树也调整为堆？处理这一问题可采取“筛选法”，其基本思想是：因为R[i]左右子树已是堆，这两棵子树根分别是各自子树中关键字最大结点，所以我们必须在R[i]和它左右孩子中选取关键字最大结点放到R[i]位置上。若R[i]关键字已是三者中最大者，则无须做任何调整，以R[i]为根子树已组成堆，不然必须将R[i]和含有最大关键字左孩子R[2i]或右孩子R[2i+1]进行交换。假定R[2i]关键字最大，将R[i]和R[2i]交换位置，交换之后有可能造成R[2i]为根子树不再是堆，但因为R[2i]左右子树依然是堆，于是能够重复上述过程，将以R[2i]为根子树调整为堆，...，如此逐层递推下去，最多可能调整到树叶。57/106例子：关键字序列为42，13，91，23，24，16，05，88，n=8，故从第四个结点开始调整4213912324160588421391232416058858/10642139188241605234213918824160523不调整59/1064213918824160523421391882416052360/1064288912324160513428891232416051361/10691884223241605139188422324160513建成堆62/106筛选算法SIFT(rectypeR[],inti;intm){intj;rectypetemp;temp=R[i];j=2*i;while(j<=m){if((j<m)&&(R[j].key<R[j+1].key))j++;if(temp.key<R[j].key){R[i]=R[j];i=j;j=2*i;}elsebreak;}R[i]=temp;}63/106

上述算法只是对一个指定结点进行调整。有了这个算法，则将初始无序区R[1]到R[n]建成一个大根堆，可用以下语句实现：for(i=n/2;i>=1;i--)SIFT(R,i,n)

因为建堆结果把关键字最大统计选到了堆顶位置，而排序结果应是升序，所以，应该将R[1]和R[n]交换，这就得到了第一趟排序结果。第二趟排序操作首先是将无序区R[1]到R[n-1]调整为堆。这时对于当前堆来说，它左右子树依然是堆，所以，能够调用SIFT函数将R[1]到R[n-1]调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区最终一个统计R[n-1]交换，如此重复进行下去。64/10691884223241605139188422324160513（a）初始堆R[1]到R[8]65/10613884223241605911388422324160591（b）第一趟排序之后66/106（c）重建堆R[1]到R[7]8824422313160591882442231316059167/10605244223131688910524422313168891（d）第二趟排序之后68/106（e）重建堆R[1]到R[6]4224162313058891422416231305889169/106（f）第三趟排序之后0524162313428891052416231342889170/106（g）重建堆R[1]到R[5]2423160513428891242316051342889171/106（h）第四趟排序之后1323160524428891132316052442889172/106（i）重建堆R[1]到R[4]2313160524428891231316052442889173/106（j）第五趟排序之后0513162324428891051316232442889174/106（k）重建堆R[1]到R[3]1613052324428891161305232442889175/106（l）第六趟排序之后0513162324428891051316232442889176/106（m）重建堆R[1]到R[2]1305162324428891130516232442889177/106（n）第七趟排序之后0513162324428891051316232442889178/106堆排序算法HEAPSORT(rectypeR[]){inti;rectypetemp;for(i=n/2;i>=1;i--)SIFT(R,i,n);for(i=n;i>=1;i--){temp=R[1];R[1]=R[i];R[i]=temp;SIFT(R,1,i-1);}}79/106堆排序时间复杂度堆排序时间复杂性为O(nlog2n)空间复杂性为O(1)堆排序是不稳定排序方法。80/106§5归并排序基本原理，经过对两个有序结点序列合并来实现排序。所谓归并是指将若干个已排好序部分合并成一个有序部分。81/106两路归并基本思想归并排序是利用“归并”技术来进行排序，所谓归并是指将若干个已经排序子序列合并为一个有序序列。其算法比较简单，能够直接给出。82/106两路归并示例25

57

48

37

12

92

862557

3748

9212

8625374857

1286921225374857869283/106归并算法voidmerge(R[],R1[],low,mid,hign)//R[low]到R[mid]与R[mid+1]到R[high]是两个有序序列，结果是合并为一个有序序列R1[low]到R1[high]//{i=low;j<=mid+1;k=low;while(i<=mid&&j<=high)if(R[i].key<=R[j].key)R1[k++]=R[i++];elseR1[k++]=R[j++];while(i<=mid)R1[k++]=R[i++];while(j<=high)R1[k++]=R[j++];}84/106

归并排序就是利用上述归并操作实现排序。其基本思想是：将待排序列R[0]到R[n-1]看成n个长度为1有序子序列，把这些子序列两两归并，便得到high(n/2)个有序子序列。然后再把这high(n/2)个有序子序列两两归并，如此重复，直到最终得到一个长度为n有序序列。上述每次归并操作，都是将两个子序列归并为一个子序列，这就是“二路归并”，类似地还能够有“三路归并”或“多路归并”。85/106归并过程示例(25)(57)(48)(37)(12)(92)(86)(2557)(3748)(1292)(86)(25374857)(128692)(12253748578692)86/106一趟归并算法归并排序就是利用上述归并操作实现排序。

其基本思想是：将待排序统计序列R[0]到R[n-1]看成为n个长度为1有序序列，将其进行两两归并，则得到[n/2]个（n为基数时候则为[（n+1）/2]个）长度为2有序序列，然后继续进行，直到最终得到一个长度为n有序序列为止。这就是2-路归并排序。其中，最关键是将两个长度为l有序序列归并为长度为2l有序序列。87/106一趟归并算法MERGEPASS(rectypeR[],rectypeR1[],intlength){inti,j;i=0;while(i+2*length-1<n){MERGE(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;}if(i+length-1<n-1)MERGE(R,R1,i,i+length-1,n-1);elsefor(j=i;j<n;j++)R1[j]=R[j];}88/106

在上述一趟归并过程中，假如恰好配成对时候，即可正常完成，不然最终一次归并时，可能有两种情况：（1）(2k+1)*len<n<2(k+1)*len表示有两个有序序列，但后一个长度不足len，此时归并方法与前相同，仅仅是参数不一样而已。（2）2k*len<n<2(k+1)*len表示只有一个有序序列，此时已经是有序，故只需要复制到R1中即可。归并排序就是从长度为1有序序列逐步归并为长度为2，4，…,n循环过程。89/106归并排序算法MERGESORT(rectypeR[]){intlength=1;while(length<n){MERGEPASS(R,R1,length);length=2*length;MERGEPASS(R1,R,length);length=2*length;}}

90/106算法复杂性分析归并排序是稳定排序方法。归并排序在第i趟归并后，有序子文件长度为2i，所以，所以，对于含有n个统计序列来说，必须做high(log2n)趟归并，每趟归并所花时间为O(n)。所以，二路归并排序算法时间复杂度为O(nlog2n)，辅助数组所需空间为O(n)。91/106§6基数排序基本原理，采取“分配”和“搜集”方法，用对多关键字进行排序思想实现对单关键字进行排序方法。下面先介绍多关键字排序92/106多关键字排序方法示例如对扑克牌排序每张扑克牌有两个“关键字”：花色和面值它们之间有次序优先。对以上排序，能够先对花色排序，或先对面值排序。93/106多关键字有序概念考虑对象序列{V0,V1,...,Vn-1}，每个对象Vi含d个关键字(Ki1,Ki2,...,Kid)。若对序列中任意两个对象Vi和Vj都有(Ki1,Ki2,...,Kid)<(Kj1,Kj2,...,Kjd)则称序列对关键字(Ki1,Ki2,...,Kid)有序，且K1称为最高位关键字，Kd称为最低位关键字。94/106多关键字排序原理：依据组成关键字各位值进行排序。实现基数排序两种方法：1最高位优先(MSD)排序：从关键字高位到低位2最低位优先(LSD)排序：从关键字低位到高位MSD方法通常是一个递归过程。95/106多关键字排序（续）LSD和MSD方法也可应用于对一个关键字进行排序。此时可将单关键字Ki看成是一个子关键字组：(Ki1,Ki2,...,Kid)如对关键字取值范围为0到999一组对象，可看成是(K1,K2,K3)组合。MSD方法按K1,K2,K3次序对全部对象排序；LSD方法按K3,K2,K1次序对全部对象排序。96/106链式基数排序基数排序是一个经典LSD排序方法，它利用“分配”和“搜集”两种运算对单关键字进行排序。此时可将单关键字K看成是一个子关键字组：(Ki1,Ki2,...,Kid)排序过程：设关键字共有d位，让j=d,d-1,...,1,依次执行d次“分配”与“搜集”。97/1061792083069385998455927133B[0].fB[1].fB[2].fB[3].fB[4].fB[5].fB[6].fB[7].fB[8].fB[9].fB[0].eB[1].eB[2].eB[3].eB[4].eB[5].eB[6].eB[7].eB[8].eB[9].e271933398455306208179859998/1062719333984553062081798599B[0].fB[1].fB[