《第10章-内部排序-数据结构-(第二版)-教学课件.ppt》由会员分享，可在线阅读，更多相关《第10章-内部排序-数据结构-(第二版)-教学课件.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十章第十章 内部排序内部排序 基本概念基本概念 插入排序插入排序 快速排序快速排序 选择排序选择排序 基数排序基数排序10.110.1 基本概念基本概念 设设设设含含含含有有有有n n个个个个记记记记录录录录的的的的文文文文件件件件RR1 1,R,R2 2,.,R,.,Rn n，其其其其相相相相应应应应的的的的关关关关键键键键字字字字为为为为KK1 1,K,K2 2,.,K,.,Kn n，将将将将记记记记录录录录按按按按关关关关键键键键字字字字值值值值非非非非递递递递减减减减(或非递增或非递增或非递增或非递增)顺序排列的过程，称为顺序排列的过程，称为顺序排列的过程，称为顺序排列的过程，称为排
2、序排序。对对对对所所所所有有有有的的的的KKi i=K=Kj j(ij),(ij),若若若若排排排排序序序序前前前前R Ri i领领领领先先先先于于于于R Rj j,排排排排序序序序后后后后R Ri i仍仍仍仍领领领领先先先先于于于于R Rj j,则则则则称称称称该该该该排排排排序序序序方方方方法法法法是是是是稳稳定定的的，反反反反之之之之，称为称为称为称为不稳定不稳定 的。的。的。的。稳稳稳稳定定定定性性性性是是是是对对对对序序序序列列列列中中中中的的的的两两两两个个个个相相相相同同同同的的的的关关关关键键键键字字字字在在在在初初初初始始始始序序序序列列列列和和和和最最最最终终终终有有有有序
3、序序序序序序序列列列列中中中中相相相相对对对对位位位位置置置置（即即即即领领领领先先先先关关关关系系系系）是是是是否否否否变化。变化。变化。变化。10.110.1 基本概念基本概念 内内部部排排序序：待待排排序序文文件件的的全全部部记记录录存存放放在在内内存存进行的排序，称为内部排序。进行的排序，称为内部排序。外外部部排排序序：排排序序过过程程中中需需要要进进行行内内外外存存数数据据交交换的排序，称为外部排序。换的排序，称为外部排序。10.110.1 基本概念基本概念内排序分类内排序分类内排序分类内排序分类 按排序过程依据的原则分为：插入排序按排序过程依据的原则分为：插入排序按排序过程依据的原
4、则分为：插入排序按排序过程依据的原则分为：插入排序 交换排序交换排序交换排序交换排序 选择排序选择排序选择排序选择排序 归并排序归并排序归并排序归并排序 计数排序计数排序计数排序计数排序 按排序过程所需的工作量分：简单排序按排序过程所需的工作量分：简单排序按排序过程所需的工作量分：简单排序按排序过程所需的工作量分：简单排序 O(n O(n2 2)先进排序先进排序先进排序先进排序 O(nlog O(nlogn n)基数排序基数排序基数排序基数排序 O(d O(dn)n)10.2 插入排序插入排序 直接插入排序算法直接插入排序算法 PROC strainsort(VAR r:)；FOR i:=2
5、TO n DO r0:=ri;j:=i-1;r1ri-1为有序子文件为有序子文件 WHILE r0.keyrj.key DO rj+1:=rj;j:=j-1;确定插入位置并移动确定插入位置并移动 rj+1:=r0 ENDP;strainsort10.2 插入排序插入排序 算法分析算法分析 空空间间上上，只只只只需需需需i i，j j两两两两个个个个整整整整型型型型变变变变量量量量和和和和一一一一个个个个记记记记录录录录的的的的辅辅辅辅助助助助空空空空间间间间r0,r0,r0r0作作作作为为为为“监监监监视视视视哨哨哨哨”，控控控控制制制制待待待待插插插插入入入入元元元元素素素素相相相相对对对对
6、于于于于有有有有序序序序子子子子文文文文件件件件为为为为最最最最小小小小时时时时WHILEWHILE循环的结束，同时也用于暂存待插入元素。循环的结束，同时也用于暂存待插入元素。循环的结束，同时也用于暂存待插入元素。循环的结束，同时也用于暂存待插入元素。时间上时间上，只包含比较关键字和移动记录两种操作。，只包含比较关键字和移动记录两种操作。，只包含比较关键字和移动记录两种操作。，只包含比较关键字和移动记录两种操作。比较次数比较次数比较次数比较次数:1/.1/.当待初始文件按关键字递增有序当待初始文件按关键字递增有序当待初始文件按关键字递增有序当待初始文件按关键字递增有序(正序正序正序正序)时：时
7、：时：时：a.a.对每个记录只进行一次比较，整个排序过程共对每个记录只进行一次比较，整个排序过程共对每个记录只进行一次比较，整个排序过程共对每个记录只进行一次比较，整个排序过程共 n n进行了进行了进行了进行了1=n-11=n-1次比较次比较次比较次比较(最少最少最少最少)；i=2 i=2 b.b.每每每每个个个个记记记记录录录录都都都都要要要要进进进进行行行行riri移移移移到到到到r0r0和和和和r0r0移移移移到到到到rj+1rj+1两两两两次次次次移移移移动动动动，因此共移动因此共移动因此共移动因此共移动2(n-1)2(n-1)次次次次(最少最少最少最少)。10.2 插入排序插入排序
8、2/.2/.当待排序文件按关键字非递增有序当待排序文件按关键字非递增有序当待排序文件按关键字非递增有序当待排序文件按关键字非递增有序(逆序逆序逆序逆序)时时时时 记记记记录录录录ri(i=2,3,.n)ri(i=2,3,.n)均均均均要要要要和和和和前前前前i-1i-1个个个个记记记记录录录录及及及及r0r0进进进进行行行行比比比比较较较较，整整整整个个个个排序过程共进行了排序过程共进行了排序过程共进行了排序过程共进行了 n n i=(n+2)(n-1)/2 i=(n+2)(n-1)/2次比较次比较次比较次比较(最多最多最多最多)；i=2i=2 移移移移动动动动记记记记录录录录次次次次数数数数
9、：每每每每个个个个记记记记录录录录都都都都要要要要进进进进行行行行riri移移移移动动动动到到到到r0r0和和和和r0r0移移移移动动动动到到到到rj+1rj+1两两两两次次次次移移移移动动动动，另另另另外外外外当当当当ri.keyri.keyrj.keyrj.key时时时时，还还还还将将将将rjrj移移移移动动动动到到到到rj+1rj+1，所所所所以以以以，当当当当初初初初始始始始文文文文件件件件为为为为正正正正序序序序时时时时，移移移移动动动动记记记记录录录录次次次次数数数数最最最最少少少少为为为为2 2（n-1n-1）次，当初始文件为逆序时移动记录次数最多为）次，当初始文件为逆序时移动记
10、录次数最多为）次，当初始文件为逆序时移动记录次数最多为）次，当初始文件为逆序时移动记录次数最多为 n n (i-1)+2(n-1)=(n+4)(n-1)/2 (i-1)+2(n-1)=(n+4)(n-1)/2次次次次(最多最多最多最多)。i=2i=2 10.2 插入排序插入排序二二.折半插入排序折半插入排序 由于是在有序子文件中确定插入的位置，因此由于是在有序子文件中确定插入的位置，因此可用折半查找来代替直接插入排序法中的顺序查找，可用折半查找来代替直接插入排序法中的顺序查找，从而可减少比较次数。从而可减少比较次数。10.2 插入排序插入排序PROC binsort(VAR r：listtyp
11、e)；FOR i：=2 TO n DO s：=1；j：=i-1；r0：=ri；WHILE sj DO m：=（s+j）/2；IF rikeyrmkey 确保稳定，若改为确保稳定，若改为，则不稳定，则不稳定 THEN j：-1 ELSE s：=m+1；FOR k：=i-1 DOWNTO j+1 DO rk+1：=rk；rj+1：=r0 ENDP；binsort 移动次数未变，故仍为移动次数未变，故仍为O(n2)10.2 插入排序插入排序三三.希尔排序（希尔排序（Shells Methool）(又称为缩小增量排序又称为缩小增量排序)基基本本思思想想：分分割割成成若若干干个个较较小小的的子子文文件件
12、，对对各各个个子子文文件件分分别别进进行行直直接接插插入入排排序序，当当文文件件达达到到基基本本有有序序时时，再再对对整整个个文文件件进进行行一一次次直直接插入排序。接插入排序。依据依据：若待排序文件若待排序文件基本有序基本有序，即文件中具有特性：，即文件中具有特性：ri.key Max rj 1ji的记录数较少，的记录数较少，则文件中大多数记录都不需要进行插入。则文件中大多数记录都不需要进行插入。基本有序时，直接插入排序效率可以提高，接近于基本有序时，直接插入排序效率可以提高，接近于O(n)。10.2 插入排序插入排序4希尔排序的特点希尔排序的特点 子文件（子序列）的构成不是简单地子文件（子
13、序列）的构成不是简单地“逐段分割逐段分割”，而是将相隔某个，而是将相隔某个“增量增量”的记录组成一个子文件。的记录组成一个子文件。增量序列应是递减，且最后一个必须为增量序列应是递减，且最后一个必须为1。希尔排序法是不稳定的。希尔排序法是不稳定的。5.希尔排序算法的实现希尔排序算法的实现PROC shellsort(VAR r:ARRAY-d1:n OF rcdtypePROC shellsort(VAR r:ARRAY-d1:n OF rcdtype；d:ARRAY1.t OF integer)d:ARRAY1.t OF integer)；d1.dt为为增增量量序序列列，r(-d1.n)中中,
14、-d1.0为为各各趟趟监监视视哨哨位，位，1.n为记录为记录 k:=1;k:=1;REPEAT REPEAT dh:=dk;s:=-dh+1;dh:=dk;s:=-dh+1;s为哨兵位为哨兵位,dh为增量值为增量值 FOR i:=dh+1 TO n DO FOR i:=dh+1 TO n DO rs:=ri;j:=i-dh;rs:=ri;j:=i-dh;WHILE rs.key WHILE rs.keyrj.key DOrj.key DO rj+dh:=rj;j:=j-dh;rj+dh:=rj;j:=j-dh;rj+dh:=rs;s:=s+1;rj+dh:=rs;s:=s+1;IF s IF
15、s0 THEN s:=-dh+1;0 THEN s:=-dh+1;k:=k+1 k:=k+1 UNTIL dh=1 UNTIL dh=1ENDP;shellsort ENDP;shellsort 10.2 插入排序插入排序k dh i s j -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 101 5 6 -4 1 13 49 38 65 97 76 13 27 49 55 04 -4 while 49 13 FOR 7 -3 2 while 27 38 -3 27 8 -2 3 while 49 -2 49 97 9 -1-4 while 55 -1 55 10 0 5
16、 while 04 76 0 04 交换交换5次次 13 27 49 55 04 49 38 65 97 762 3 4 -2 1 while 55 5 -1 2 while 04 27 -1 04 6 0 3 while 49 7 1(-2)4 while 38 55 -2 38 8 -1 5 while 65 9 0 6 while 97 10 1(-2)7 while 76交换交换2次次 1 13 04 49 38 27 49 55 65 97 76共交换共交换12次次 04 13 49 38 27 49 55 65 97 76 10.3 10.3 快速排序快速排序 快速排序是目前内部排
17、序中最快的方法。快速排序是目前内部排序中最快的方法。基基本本思思想想：选选取取某某个个记记录录，（通通常常选选文文件件的的第第一一个个记记录录），将将所所有有关关键键字字不不大大于于它它的的记记录录放放在在它它的的前前面面，将将所所有有关关键键字字不不小小于于它它的的记记录录放放在在它它的的后后面面，这这样样遍遍历历一一趟趟文文件件后后，将将文文件件以以该该记记录录为为界界分分为为两两部部分分，然然后后对对各各部部分分重重复复上上述述过过程程，直直到到每每一一部部分分仅仅剩剩一一个个记录为止。记录为止。具体步骤具体步骤(1)置变量置变量i，j初值分别为文件的首、尾记录位置；初值分别为文件的首、
18、尾记录位置；选取文件首记录选取文件首记录ri，并将其关键字赋给变量，并将其关键字赋给变量x；(2)从从j 位置开始向前搜索，位置开始向前搜索，(3)直到遇到第一个关键字小于直到遇到第一个关键字小于x的记录，的记录，(4)并将并将rj移至移至ri；(5)从从i 位置开始向后搜索，位置开始向后搜索，(6)直到遇到第一个关键字大于直到遇到第一个关键字大于x的记录，的记录，(7)并将并将ri移至移至rj；(8)重复重复(2)(9)直到直到i=j，(10)并将并将x移至移至ri，以，以ri为中枢将文件分为为中枢将文件分为r1.i-1和和ri+1.n两部分，完成一趟排序；两部分，完成一趟排序；(11)重复
19、重复(1)至至(10)，直到每一部分只剩上一个记录，整个，直到每一部分只剩上一个记录，整个文件已有序，快速排序算法结束。文件已有序，快速排序算法结束。10.3 10.3 快速排序快速排序3.示意图：示意图：x 5向后搜索向后搜索rikeyxi=j 7ri rjrjkeyx向前搜索向前搜索 2j3rjkeyx8 4rj ririkeyx69 10 x ri1x 1 x i-1 i i+1 x n 注意：向前搜索时，注意：向前搜索时，j：=j-1，且，且ri空闲；空闲；向后搜索时，向后搜索时，i：=i-1，且，且rj空闲。空闲。10.3 10.3 快速排序快速排序 一趟快速排序算法一趟快速排序算法
20、 PROC qkpass(VAR r:listtype;s,t:integer;VAR i:integer);对对rs.t进行一趟快速排序进行一趟快速排序,i将将rs.t分为两部分分为两部分 rsi-1的关键字不大于的关键字不大于ri.key,ri+1t的关键字不小于的关键字不小于ri.key i:=s;j:=t;rp:=rs;x:=rs.key;WHILE ij DO WHILE (ij)AND(rj.keyx)DO j:=j-1;ri:=rj;WHILE (ij)AND(ri.keyx)DO i:=i+1;rj:=ri ri:=rp ENDP;qkpass 10.3 10.3 快速排序快速
21、排序 快速排序算法特点快速排序算法特点 快速排序算法是不稳定的。快速排序算法是不稳定的。对待排序文件对待排序文件 49 49 38 65，快速排序结果为快速排序结果为:38 49 49 65 快快速速排排序序的的效效率率跟跟初初始始文文件件中中关关键键字字的的排排列列和和选选取取划划分分的的记记录录有有关关。当当初初始始文文件件按按关关键键字字有有序序(正正序序或逆序或逆序)时，性能最差，时间复杂度为时，性能最差，时间复杂度为O(n2)；常常用用“三三者者取取中中”法法来来选选取取划划分分记记录录，即即取取首首记记录录rs.key.尾尾记记录录rt.key和和中中间间记记录录r(s+t)/2.
22、key三三者的中间值为划分记录。者的中间值为划分记录。(4)快速排序算法的平均时间复杂度为快速排序算法的平均时间复杂度为O(nlogn)。10.4 10.4 选择排序选择排序 一一.简单选择排序简单选择排序 基本思想基本思想：对文件进行对文件进行n-1趟排序，第趟排序，第i趟趟(i=1,2,.n-1)是在从是在从i到到 n的的n-i+1个记录中选择关个记录中选择关键字最小的记录，并将它与第键字最小的记录，并将它与第i个记录进行交换。个记录进行交换。1 n1 n第一趟第一趟第一趟第一趟 n n个记录个记录个记录个记录第二趟第二趟第二趟第二趟 n-1 n-1 第第第第-1-1趟趟趟趟 2 2比较次
23、数比较次数比较次数比较次数n-1n-1n-2n-21 110.4 10.4 选择排序选择排序 简单选择排序算法简单选择排序算法 PROC smp-selecsort(VAR r:listtype);FOR i:=1 TO n-1 DO k:=i;FOR j:=i+1 TO n DO IF rj.keyrk.key THEN k:=j;IF ki THEN rirk ENDP;smp-selecsort 10.4 10.4 选择排序选择排序 二二.堆排序堆排序 堆的定义堆的定义：n个元素的序列个元素的序列K1,K2,.,Kn 若满足：若满足：KiK2i 或或 KiK2i KiK2i+1 KiK2
24、i+1 (i=1,2,.n/2)称为堆。称为堆。10.4 10.4 选择排序选择排序 若若将将堆堆视视为为一一个个完完全全二二叉叉树树（图图一一），则则堆堆的的含含义义为为：完完全全二二叉叉树树中中所所有有非非终终端端结结点点的的值值均均不不大大于于(或或不不小小于于)其其左左、右右孩孩子子的的值值（图图二二）。堆堆顶顶元元素素(即即完完全全二二叉叉树树的的根根)是是序序列列中最小中最小(或最大或最大)的元素。的元素。k3k1k5 k2k4 图一图一241247 3885913053图二图二10.4 10.4 选择排序选择排序 调整方法调整方法 将堆顶元素和堆的最后一个元素位置交换；将堆顶元素
25、和堆的最后一个元素位置交换；然然后后以以当当前前堆堆顶顶元元素素和和其其左左、右右子子树树的的根根结结点点进进行行比比较较(此此时时，左左、右右子子树树均均为为堆堆)，并并与与值值较较小小的的结结点点进进行行交换；交换；重重复复，继继续续调调整整被被交交换换过过的的子子树树，直直到到叶叶结结点点或或没没进行交换为止。进行交换为止。称这个调整过程为称这个调整过程为筛选筛选。10.4 10.4 选择排序选择排序例：例：例：例：271376 3849976549输出输出13279776 3849136549筛选筛选492776 3849136597筛选筛选结果结果输出输出27499776 38491
26、3652712493876 499713652710.4 10.4 选择排序选择排序10.4 10.4 选择排序选择排序 筛选过程筛选过程PROC shift(VAR r:listtype;k,m:integer);已已知知 vk.m是是以以rk为为根根的的完完全全二二叉叉树树,以以r2k和和r2k+1 为为根的左、右子树是堆。根的左、右子树是堆。要求要求:调整调整rk使使rk.m为堆为堆 i:=k;j:=2*i;x:=rk.key;t:=rk;finished:=false;WHILE (jm)AND NOT finished DO IF (jm)AND(rj.keyrj+1.key)THE
27、N j:=j+1;满足条件满足条件,沿右枝筛选沿右枝筛选 IF xrj.key THEN finished:=true ELSE ri:=rj;i:=j;j:=2*i ri:=t ENDP;sift 10.4 10.4 选择排序选择排序 无序序列建堆过程无序序列建堆过程 方方法法：从从完完全全二二叉叉树树的的最最后后一一个个非非终终端端结结点点 n/2开开始始，反反复复调调用用筛筛选选过过程程，直直到到第第一一个个结点，则得到一个堆。结点，则得到一个堆。134976 3849976527654976 3897491327271376 3849976549例：例：49，38，65，97，76，1
28、3，27，49 10.4 10.4 选择排序选择排序 堆排序过程堆排序过程 PROC headsort(VAR r:listtype);FOR i:=n/2 DOWNTO 1 DO shift(r,i,n);自第自第 n/2开始筛选建堆开始筛选建堆 FOR i:=n DOWNTO 2 DO r1ri;堆顶与堆中最后一个记录交换堆顶与堆中最后一个记录交换 shift(r,1,i-1)使使r1.i-1成为堆成为堆 ENDP;headsort堆排序是不稳定的，时间复杂度为堆排序是不稳定的，时间复杂度为O(nlogn)。10.5 10.5 归并排序归并排序 归归并并概概念念：把把 2 个个有有序序子子
29、文文件件合合并并成成一一个个有有序序文文件件的的过过程，称为程，称为2-路归并。路归并。归并排序基本思想：归并排序基本思想：将文件的每个记录视为一个有序子将文件的每个记录视为一个有序子文件；文件；然后两两子文件进行然后两两子文件进行2-路归并；路归并；重复重复，直到只，直到只剩一个长度为剩一个长度为n的有序文件的有序文件 例：初始关键字：例：初始关键字：49 38 65 97 76 13 27 49 第一趟后第一趟后 38 49 65 97 13 76 27 49第二趟后第二趟后 38 49 65 97 13 27 49 76第三趟后第三趟后 13 27 38 49 49 65 76 97 每
30、个记录视为一个有序子文件，两个子文件进行归并，得每个记录视为一个有序子文件，两个子文件进行归并，得4个个有序子文件。有序子文件。归并排序过程归并排序过程 PROC merge(r:listtype;l,m,n:integer;VAR r2:listtype);ts.m和和rm+1.n 为两个有序子文件为两个有序子文件,归并结果存放在归并结果存放在r2s.n中中 i:=s;j:=m+1;k:=s-1;WHILE(im)AND(jn)DO k:=k+1;k为下一次存入为下一次存入r2的位置的位置 IF ri.keyrj.key THEN r2k:=ri;i:=i+1 ELSE r2k:=rj;i:
31、=j+1 ;IF im THEN r2k+1.n:=ri.m;IF jn THEN r2k+1.n:=rj.n 将其中一个文件的余下部分复制到将其中一个文件的余下部分复制到r2的尾部的尾部 ENDP;merge归并排序是稳定的，时间复杂度为归并排序是稳定的，时间复杂度为归并排序是稳定的，时间复杂度为归并排序是稳定的，时间复杂度为O(nlogn)O(nlogn)，需要和待排序记录相等数量的辅助空间需要和待排序记录相等数量的辅助空间需要和待排序记录相等数量的辅助空间需要和待排序记录相等数量的辅助空间r2r2。10.6 10.6 基数排序基数排序 基基基基数数数数排排排排序序序序法法法法是是是是一一
32、一一种种种种用用用用多多多多关关关关键键键键字字字字排排排排序序序序思思思思想想想想对对对对单单单单逻逻逻逻辑辑辑辑关关关关键键键键字字字字进进进进行行行行排排排排序序序序，而而而而无无无无需需需需进进进进行行行行关关关关键键键键字字字字比比比比较较较较的的的的新新新新排排排排序序序序方方方方法，其基本操作是法，其基本操作是法，其基本操作是法，其基本操作是“分配分配分配分配”和和和和“收集收集收集收集”。基基数数排排序序方方法法：基基基基数数数数排排排排序序序序是是是是按按按按组组组组成成成成关关关关键键键键字字字字的的的的各各各各位位位位的的的的值值值值进进进进行行行行分分分分配配配配和和和
33、和收收收收集集集集，与与与与前前前前面面面面介介介介绍绍绍绍的的的的排排排排序序序序方方方方法法法法不不不不同同同同，它无需进行关键字之间的比较。它无需进行关键字之间的比较。它无需进行关键字之间的比较。它无需进行关键字之间的比较。设关键字有设关键字有d 位，每位的取值范围为位，每位的取值范围为 r(称为基数称为基数)，则需要进行，则需要进行d 趟分配与收集，需要设立趟分配与收集，需要设立 r 个队列。个队列。例如，若每位是十进制数字，则需要设立例如，若每位是十进制数字，则需要设立10个队列，个队列，若每位由小写字母组成，则要设立若每位由小写字母组成，则要设立26个队列个队列。10.6 10.6
34、 基数排序基数排序2.基数排序的步骤基数排序的步骤 从从关关键键字字的的低低位位开开始始进进行行第第i趟趟(i=1,2,.d)分分配配即即将将单单链链表表中中的的记记录录依依次次按按关关键键字字的的第第i位位分分配配到到相相应应编号的队列中；编号的队列中；分分配配完完毕毕后后，将将各各队队列列的的记记录录按按队队列列编编号号顺顺序序收收集成一个单链表；集成一个单链表；重重复复，直直到到第第d趟趟收收集集完完毕毕，所所得得单单链链表表已已成成为有序表。为有序表。10.6 10.6 基数排序基数排序例：例：初始初始 278109063930589184505269008083 0 1 2 3 4
35、5 6 7 8 9第一趟分配第一趟分配 269 083 008 589 930 063 184 505 278 109第一趟收集第一趟收集 930063083184505278008109589269第二趟分配第二趟分配 109 589 008 269 184 505 930 063 278 083第二趟收集第二趟收集 505008109930063269278083184589第三趟分配第三趟分配 083 063 184 278 589 008 109 269 505 930 第三趟收集第三趟收集 00806308310918426927850558993010.6 10.6 基数排序基数排序 基数排序的特点基数排序的特点 基基数数排排序序的的基基本本操操作作是是分分配配和和收收集集，而而不不是是关关键字之间的比较；键字之间的比较；基基数数排排序序是是稳稳定定的的，其其时时间间复复杂杂度度为为O(d(n+rd)，其其中中n是是记记录录数数，d是是关关键键字字的的位位数数，r是是关关键键字字各各位位的的值域。值域。基数排序要进行基数排序要进行d趟分配和收集趟分配和收集,需需r个队列个队列