数据结构chapter_10.ppt

1、数据结构,第十章 排序,第十章 内部排序,10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.2 其它插入排序 10.2.3 希尔排序 10.3 快速排序 10.4 选择排序 10.4.1 简单选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.6.1 多关键字的排序 10.6.2 链式基数排序 10.7 各种内部排序方法的比较讨论,10.1 概述,排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。,有序表与无序表：一组记录按关键字的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。,内部排序

2、和外部排序： 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序,正序表与逆序表：若有序表是按关键字升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。不失普遍性，一般只讨论正序表。,内部排序的方法：,插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序其它排序: 多关键字排序、基数排序,排序基本操作：比较两个关键字大小将记录从一个位置移动到另一个位置,排序算法的稳定性: 考虑有多个数据元素具有相同关键字的情况。 稳定：具有相同关键字的数据元素的相对位置关系在排序前后保持不变。 不稳定：

3、具有相同关键字的数据元素的相对位置关系在排序前后发生了改变。,待排序记录在内存中怎样存储和处理？,顺序排序排序时直接移动记录； 链表排序排序时只移动指针； 地址排序排序时先移动地址，最后再移动记录。,注：地址排序中可以增设一维数组来专门存放记录的地址。,注：大多数排序算法都是针对顺序表结构的(便于直接移动元素),顺序存储（顺序表）的抽象数据类型如何表示？,typedef struct /定义每个记录（数据元素）的结构 KeyType key ; /关键字 InfoType otherinfo; /其它数据项 RedType; /记录类型,typedef struct /定义顺序表L的结构 Re

4、cordType r MAXSIZE +1 ; /存储顺序表的向量 /r0一般作哨兵或缓冲区 int length ; /顺序表的长度 SqList; /顺序表类型,# define MAXSIZE 20 /设上课举例的记录数均不超过20个 typedef int KeyType ; /设关键字为整型量（int型）,内部排序的算法有哪些？,按排序的规则不同，可分为5类： 插入排序 交换排序（重点是快速排序） 选择排序 归并排序 基数排序,d关键字的位数(长度),按排序算法的时间复杂度不同，可分为3类： 简单的排序算法：时间效率低，O(n2) 先进的排序算法: 时间效率高，O( nlog2n )

5、 基 数 排 序 算法：时间效率高，O( dn),例:,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3 65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27,i=6 13 (13 38 49 65 76 97) 27,i=1 ( ),i=7 (13 38 49 65 76 97) 27,27,97,76,65,49,38,27,10.2 插入排序,10.2.1 直接插入排序,排序过程：整个排序过程为n-1趟插入，即先

6、将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。,算法参见P265,直接插入排序算法的实现：,void InsertSort ( SqList /直到子表元素小于哨兵，将哨兵值送入 /当前要插入的位置（包括插入到表首） /if / InsertSort,（参见教材P265）,例1：关键字序列T= （21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。,*表示后一个25,i=1,21,i=2,i=3,i=5,i=4,i=6,25,49,25*,49,16,16,08,49,解：假设该序列已存入一维数组r7中，将r0作为哨兵（Te

7、mp）。则程序执行过程为：,初态：,16,25,21,16,完成!,时间效率： 因为在最坏情况下，所有元素的比较次数总和为（01n-1)O(n2)。其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2) 空间效率：仅占用1个缓冲单元O（1） 算法的稳定性：因为25*排序后仍然在25的后面稳定,若待排序记录按关键字从小到大排列(正序)，则 关键字比较次数：,记录移动次数：0,若待排序记录按关键字从大到小排列(逆序)，则 关键字比较次数：,记录移动次数：,若待排序记录是随机的，取平均值，则 关键字比较次数约：,记录移动次数约：,时间复杂度：T(n)=O(n)空间复杂度：S(n)=O(1),直

8、接插入排序是一种稳定的排序方法。,算法评价,折半插入排序：用折半查找方法确定插入位置。,例：,i=1 (30) 13 70 85 39 42 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,i=8 20 (6 13 20 30 39 42 70 85 ),10.2.2 其它插入排序,算法参见P267,时间复杂度：T(n)=O(n) 空间复杂度：S(n)=O(1),折半插入排序过程中的折半查找的目的是查询插入点，因此不论是否存在和给定值相同的关键字，结束查找过程的条件都是highlow，并且插入位置为low

9、指示的地方。,void BInsertSort (SqList / 插入 / BInsertSort,折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间，因此折半插入排序的时间复杂度仍为O (n2)。,10.2.3 希尔排序,希尔排序（Shells Sort）又称为“缩小增量排序”。 排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。,38,例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体

10、实现过程。,初态：,第1趟 (dk=5),第2趟 (dk=3),第3趟 (dk=1),49,13,13,49,38,27,65,49*,97,55,76,04,27,38,65,49*,97,55,13,55,76,04,55,13,27,04,27,04,49,49*,49,49*,76,38,76,65,65,97,97,13,27,04,49*,76,97,算法分析：开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。,ri,由于C语言的数组没有负数的下标，因此，

11、在dk1时需对j循环中以防出界另作j0的判别，即L.r0 不再起到监视哨的作用，而仅仅作为一个暂存记录的空间。,void ShellInsert ( SqList / 插入到正确位置 / if / ShellInsert,void ShellSort (SqList / 一趟增量为 dltak 的插入排序 / ShellSort,dk值依次装在dltat中,时间效率：,空间效率：O（1）因为仅占用1个缓冲单元 算法的稳定性：不稳定因为49*排序后却到了49的前面,O(n1.25）O（1.6n1.25）由经验公式得到,1. 欲将序列（Q, H, C, Y, P, A, M, S, R, D, F

12、, X）中的关键码按字母升序重排，则初始步长为4的希尔排序一趟的结果是？ 答：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后：,课堂练习：,原始序列： 256，301，751，129，937，863，742，694，076，438,希尔排序,(取dk=5, 3, 1),256，301，751，129，937，863，742，694，076，438,256，301，751，129，937，863，742，694，076，438,256，301，694，129，937，863，742，751，076，438,256，301，694，076，937

13、，863，742，751，129，438,256，301，694，076，438，863，742，751，129，937,第1趟 dk=5 第2趟 dk=3 第3趟 dk=1,256，301，694，076，438，863，742，751，129，937,256，301，694，076，438，863，742，751，129，937,076，301，694，256，438，863，742，751，129，937,076，301，694，256，438，863，742，751，129，937,076，301，694，256，438，863，742，751，129，937,076，301，129，

14、256，438，694，742，751，863，937,076，301，129，256，438，694，742，751，863，937,076，301，129，256，438，694，742，751，863，937,076，129，256，301，438，694，742，751，863，937,2. 以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行希尔排序（取dk=5,3,1）算法的各趟排序结束时，关键字序列的状态。,希尔排序特点,子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列。关键字较小的记录跳跃式前移，

15、在进行最后一趟增量为1的插入排序时，序列已基本有序。希尔排序的时间复杂度在O（nlog2n）和O（n2 ）之间，大致为O（n 1.3）。,由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。增量序列取法:希尔排序的增量序列 dlta 可以有多种取法，但必须是， (1) dlta中各值没有除1之外的公因子； (2) dltat-1必须为1。 例如，dlta=,9,5,3,2,1 或 dlta=, 31,15,7,3,1 或 dlta=,40,13,4,1等。,10.3 快速排序,冒泡排序,排序过程：将第一个记录的关键字与第二个记录的

16、关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被放在最后。,对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被放在第n-1个位置。重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。,算法参见P16算法。,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,排序后序列为：13 27 30

17、38 49 65 76 97,void BubbleSort(SqList / for i / BubbleSort,算法中设立了一个标志一趟起泡中是否进行了交换记录操作的布尔型变量change，在每一趟起泡之前均将它设为FALSE，一旦进行记录交换，则将它改为TRUE，因此 change=TRUE 是进行下一趟起泡的必要条件。,算法评价 最好情况（正序）时： 比较次数：n-1 移动次数：0 最坏情况（逆序）时： 比较次数：,移动次数：,时间复杂度：T(n)=O(n),冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表尾），还可以对前面的元素作一些整理，所以比一般

18、的排序要快。,空间复杂度：S(n)=O(1),快速排序,从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表； 然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。,基本思想：,优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！ 前提：顺序存储结构,完成一趟排序： ( 27 38 13) 49 (76 97 65 50),分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97),快速排序结束： 13 27 38 49 50 65 76

19、97,49,27,49,65,13,49,49,97,算法参见P274,P275,x=49,如何编程实现？ 分析： 每一趟子表的形成是采用从两头向中间交替式逼近法； 由于每趟中对各子表的操作都相似，主程序可采用递归算法。,int Partition ( RcdType R, int low, int high) / 对记录子序列 Rlow.high 进行一趟快速排序，并返回枢轴记录 / 所在位置，使得在它之前的记录的关键字均不大于它的关键字， / 而在它之后的记录的关键字均不小于它的关键字 R0 = Rlow;/ 将枢轴记录移至数组的闲置分量 pivotkey = Rlow.key; / 枢轴

20、记录关键字 while (low=pivotkey)-high; Rlow = Rhigh;/ 将比枢轴记录小的记录移到低端 while (lowhigh / 返回枢轴位置 / Partition,void QSort (RcdType R, int s, int t ) / 对记录序列 Rs.t 进行快速排序 if (s t) / 长度大于1 pivotloc = Partition(R, s, t); / 对 Rs.t 进行一趟快排，并返回枢轴位置 QSort(R, s, pivotloc-1); / 对低子序列递归进行排序 QSort(R, pivotloc+1, t); / 对高子序列

21、递归进行排序 / if / Qsort void QuickSort( SqList / QuickSort,快速排序的算法是一个递归函数，因此算法中必须引入一对参数 s 和 t 作为待排序区域的上下界。在算法的递归调用过程执行中，这两个参数随着 区域的划分而不断变化。对顺序表L进行快速排序调用算法时，s 和 t 的初值应分别置为1和 L.length 。,时间复杂度：最好情况（每次总是选到中间值作枢轴）：T(n)=O(nlog2n)。最坏情况（每次总是选到最小或最大元素作枢轴）：T(n)=O(n)。 快速排序不适于对原本有序或基本有序的记录序列进行排序。为避免出现枢轴记录关键字为最大或最小的

22、情况，通常进行的快速排序采用三者取中的改进方案，即以 Rs、Rt 和 R(s+t)/2 三者中关键字介于中值者为枢轴。只要将它和 Rs 互换，一次划分的算法仍不变。,算法评价,10.4 选择排序,10.4.1 简单选择排序,首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行n-1趟排序后，排序结束。,算法参见P277,排序过程：,例：,初始： 49 38 65 97 76 13 27 ,i=1,13,49,13 27 38 49 65 76 97 ,排序结

23、束： 13 27 38 49 65 76 97,二趟： 13 38 65 97 76 49 27 ,i=2,27,38,void SelectSort(SqList ,时间复杂度： T(n)=O(n),算法评价,比较次数：,记录移动次数,最好情况：0,最坏情况：3(n-1),讨论：能否利用（或记忆）首趟的n-1次比较所得信息，从而尽量减少后续比较次数呢？ 答：能！请看,锦标赛排序和堆排序,10.4.2 锦标赛排序 (又称树形选择排序),基本思想：与体育比赛时的淘汰赛类似。 首先对 n 个记录的关键字进行两两比较，得到 n/2 个优胜者(关键字小者)，作为第一步比较的结果保留下来。然后在这 n/

24、2 个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。 优点：减少比较次数，加快排序速度 缺点：空间效率低,例：关键字序列T= （21，25，49，25*，16，08，63），请给出锦标赛排序的具体实现过程。,Winner (胜者),r1,注：为便于自动处理，建议每个记录多开两个特殊分量：,初态：,补足2k( k=log2n )个叶子结点,胜者树,第一趟：,第二趟：,16,16,16,r2,Winner (胜者),求次小值16时,只需比较2次，即只比较log2n -1次,令其Tag0,不参与比较,令其Tag0,不参与比较,第三趟：,r3,Winner (胜者),63,21,第

25、四趟：,r4,Winner (胜者),25,25,25,左右结点相同时左边“小”,第五趟：,r5,Winner (胜者),25*,25*,第六趟：,r6,Winner (胜者),49,49,49,第七趟：,r7,Winner (胜者),63,算法分析：,锦标赛排序构成的树是完全(满）二叉树，其深度为 log2n +1，其中 n 为待排序元素个数。 时间复杂度：O(nlog2n) n个记录各自比较约log2n次 空间效率： O(n） 胜者树的附加内结点共有n0-1个！ 稳定性：稳定 可事先约定左结点“小”,讨论：锦标赛排序巧妙利用了第一次和前若干次扫描的结果，加快了排序速度。还有没有同类方法？

26、答：有！请看,n0 =2k = 叶子总数,堆排序,或,( i=1,2,.n/2 ),例：（96，83，27，38，11，9）,例： （13，38，27，50，76，65，49，97）,可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值,10.4.3 堆排序,堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆。,例如: 12, 39, 20, 65, 47, 34, 98, 81, 73, 56为“小顶堆”； 98, 81, 34, 73, 56, 12, 20, 39, 65, 47为“大顶堆”。,利用堆的特性进行的排序方法即为

27、堆排序，其排序过程如下： 假设待排关键字序列为： 34, 39, 20, 65, 47, 12, 98, 73, 81, 56 1）先将它调整为大顶堆： 98, 81, 34, 73, 56, 12, 20, 39, 65, 47 2）互换“堆顶”和待排序列中的最后的关键字： 47, 81, 34, 73, 56, 12, 20, 39, 65, 98 3）在待排序列中舍去最大关键字，将其余部 分重新调整为堆： 81, 73, 34, 65, 56, 12, 20, 39, 47 98 4）重复2）和3）直至待排序列中只剩一个关键字为止。,例：,（大根堆）,例：,有序列T1=（08, 25,

28、49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否 “堆”？,（小根堆）,（小顶堆） （最小堆）,（大顶堆） （最大堆）,1. 什么是堆？,终端结点（即叶子）没有任何子女，无需单独调整,步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。,例：关键字序列T= (21，25，49，25*，16，08），请建大根堆。,2. 怎样建堆？,解：为便于理解，先将原始序列画成完全二叉树的形式： 这样可以很清晰地从n/2开始调整。,完全二叉树的第一个非终端结点编号必为n/2 ！(性质5),21,i=3:,49

29、,而且21还应当向下比较！,49大于08，不必调整； i=2: 25大于25*和16，也不必调整； i=1: 21小于25和49，要调整！,例： 含8个元素的无序序列（49，38，65，97，76，13，27，50）,第一个问题的解决方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。,算法参见P282,void HeapSort ( SqList / 互换堆顶和当前的堆底，使已有序的记录沉积在底部 /for / HeapSort,建堆算法 (等同于堆排序算法中的第一步）,HeapAdjust是针对结点 i 的堆调整函数，其含义

30、是：从结点i开始到堆尾为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。,参见教材P281-282,void HeapAdjust (SqList / 回移筛选下来的记录 / HeapAdjust,从结点i开始到当前堆尾m为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。,针对结点 i 的堆调整函数HeapAdjust 表述如下：,难点：将堆的当前顶点输出后，如何将剩余序列重新调整为堆？ 方法：将当前顶点与堆尾记录交换，然后仿建堆动作重新调整，如此反复直至排序结束。,3. 怎样进行整个序列的堆排序？,即：将任务转化为 H.ri

31、m中除ri外，其他都具有堆特征。 现调整ri的值 ，使H.rim为堆。,基于初始堆进行堆排序的算法步骤： 堆的第一个对象r0具有最大的关键码，将r0与rn对调，把具有最大关键码的对象交换到最后; 再对前面的n-1个对象，使用堆的调整算法，重新建立堆。结果具有次最大关键码的对象又上浮到堆顶，即r0位置; 再对调r0和rn-1，然后对前n-2个对象重新调整，如此反复，最后得到全部排序好的对象序列。,交换 1号与 6 号记录 r0 rn,例：对刚才建好的大根堆进行排序：,08 25 21 25* 16 49,从 1 号到 5 号 重新 调整为最大堆,08,25,25*,08,从 1号到 4号 重新

32、调整为最大堆,16,25*,从 1 号到 3号 重新 调整为最大堆,从 1 号到 2 号 重新 调整为最大堆,堆排序算法分析：,时间效率： O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法，而算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。,课堂练习,1. 给定一个由n个关键字不同的记录构成的序列，你能否用少于2n-3次比较找出n个元素中的最大值和最小值？如果有，请描述你的方法。最快需多少次比较？（无需写算法） (8分) 答：可以实现。选

33、用锦标赛算法。两两元素比较，淘汰较小的，形如一棵二叉树。树根为最大值（此时用掉n-1次比较）。而最小者一定位于首次被淘汰之列。故只有 n/2个。一共需n-1+ n/2次比较。,课堂练习,设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？ 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果， 时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：（请自己计算） 堆排序的准确比较次数为： （请自己计算） 若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+n-10）=10n

34、-55=10000-55=9945（次）,10.5 归并排序,归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。 更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 n / 2 个长度为 2 的有序子序列 ；再做两两归并，如此重复，直到最后得到一个长度为 n 的有序序列。,例：关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。,len=1,len=2,len=4,len=8,len=16,整个归并排序仅需log2n 趟,void Merge (RcdType

35、SR, RcdType / 将剩余的SRjn复制到TR / Merge,一趟归并排序算法: (两路有序并为一路) 参见教材P283,if ( s=t )TR1s=SRs; / 当len=1时返回 else /if / MSort,m=(s+t)/2; / 将SR st平分为SR sm和SR m+1t MSort (SR，TR2，s, m); / 将SR 一分为二, 2分为4 / 递归地将SR sm归并为有序的TR2sm MSort (SR，TR2，m+1, t ); / 递归地将SR m+1t归并为有序的TR2m+1t Merge(TR2， TR1， s, m, t ); / 将TR2 sm和

36、TR2 m+1t归并到TR1 st,void MSort (RcdType SR , RcdType / 开始从0号队列（总共radix个队）开始收集 while ( f j = 0 ) j+; /若是空队列则跳过 r0.next=p = f j; /建立本趟收集链表的头指针 int last = ej; /建立本趟收集链表的尾指针 for ( k = j+1; k radix; k+) /逐个队列链接（收集） if ( f k ) /若队列非空 rlast.next=f k; last = ek; /队尾指针链接 / for rlast.next=0; /本趟收集链表之尾部应为0 / for

37、 / RadixSort,注：在此算法中，数组rn被反复使用，用来存放原始序列和每趟收集的结果。记录从未移动，仅指针改变。,基数排序算法分析,假设有n 个记录, 每个记录的关键字有d 位，每个关键字的取值有radix个, 则每趟分配需要的时间为O(n)，每趟收集需要的时间为O(radix)，合计每趟总时间为O (n+radix ) 全部排序需要重复进行d 趟“分配”与“收集”。因此时间复杂度为：O ( d ( n+radix ) )。 基数排序需要增加n+2radix个附加链接指针，空间效率低 空间复杂度：O(n+radix）. 稳定性：稳定。(一直前后有序)。 用途：若基数radix相同，对

38、于记录个数较多而关键码位数较少的情况，使用链式基数排序较好。,特点：不用比较和移动，改用分配和收集，时间效率高！,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0 f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,1,1,2,2,3,3,4,4,5,6,6,7,7,8,9,10,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0 f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,1,3,4,4,7,7,9,10,3,10,1,6,2,5,8,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0 f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,4,4,7,9,2,8,7,9,2,8,3,1,10,6,5,10.7 各种内部排