《数据结构10排序4》由会员分享，可在线阅读，更多相关《数据结构10排序4（70页珍藏版）》请在金锄头文库上搜索。
1、10.1 插入排序插入排序10.2 交换排序交换排序10.3 选择排序选择排序10.5 基数排序基数排序10.4 归并排序归并排序1设有记录序列： R1, R2, , Rn ;其相应的关键字序列为： K1, K2 , , Kn ; 若存在一种确定的关系： Ki1 Ki2 Kin ；则将记录序列 R1, R2, . , Rn 排成按该关键字有序的序列： Ri1, Ri2, , Rin 的操作，称之为排序排序。2内部排序内部排序：全部记录都可以同时调入内存进行的全部记录都可以同时调入内存进行的排序。排序。 外部排序外部排序：文件中的记录太大，无法全部将其同文件中的记录太大，无法全部将其同时调入内存
2、进行的排序。时调入内存进行的排序。稳定的排序方法：稳定的排序方法：若记录序列中的任意两个记录若记录序列中的任意两个记录 Rx、Ry 的关键字的关键字 Kx = Ky ；如果在排序之前和如果在排序之前和排序之后，它们的相对位置保持不变，则这种排排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则称为序方法是稳定的，否则称为不稳定的排序方法不稳定的排序方法简单的排序方法简单的排序方法： T(n)=O(n2)先进的排序方法先进的排序方法： T(n)=O(nlog2n)3顺序表的存储结构：顺序表的存储结构：#define MAXSIZE /定义一个常数定义一个常数typedef struct
3、 KeyType key：； /关键字成员关键字成员 ； /其它成员其它成员 RecordTypetypedef struct RecordType rMAXSIZE+1；/r0号单元不存记录号单元不存记录 int length； / 顺序表的长度顺序表的长度 SqList；4在数组r1，r2， ，rn 中从第二个元素起，将其依次插入到前面已排好序前面已排好序的序列中。10.1.1 直接插入排序直接插入排序设立监视哨：设立监视哨：rir0r1 r2 rj rj+1 ri-1 ri 小小 大大 r0两种移位方法两种移位方法(1) j从i-1开始，一边比较，一边移位。(2)先查找位置再移位。找j，
4、使 rj ri rj+15 3 8 2 5 9 1 6i=13 1 2 3 5 6 8 9 1 2 3 5 8 9 6 2 3 5 8 9 1 6 2 3 5 8 9 1 6 2 3 8 5 9 1 625916例： 关键字序列（8，3，2，5，9，1，6)r= r0 r1 r2 r3 r4 r5 r6 r7 8 3 2 5 9 1 6i=2i=3i=4i=5i=6i=76void straightsort1(SqList &L)/设立监视哨：设立监视哨：rir0，在查找的过程中同时后移记录在查找的过程中同时后移记录 for(i=2；iL.length；i+) L.r0=L.ri； j=i-1
5、； x = L.r0.key； while(xL.rj.key) L.rj+1=L.rj； j- ； L.rj+1= L.r0； /straightsort时间分析：时间分析：T=方法方法1：边比较边边比较边移动移动7void straightsort2(SqList &L) for(i=2；iL.length；i+) L.r0=L.ri； j=i-1； x=L.r0.key； while(xL.rj.key) j-； for(k=i-1；k j+1；k-) L.rk+1=L.rk； L.rj+1=L.r0； /straightsort1方法方法2：先定位后移动先定位后移动8性能分析：性能分析
6、：(1) 时间：时间： 总时间包括：关键字的比较和记录的移动。最好情况：最好情况：O(n)； 最坏情况：最坏情况：O(n2)平均时间：平均时间： T(n)=O(n2)(2) 空间：空间： 一个记录空间。S(n)=O(1)；(3) 稳定性：稳定性： 稳定的排序方法。当记录当记录“基本有序基本有序”或或n不太大时，该方法为最佳方不太大时，该方法为最佳方法法910.1.2 折半折半(二分二分)插入排序插入排序与直接插入排序的区别：与直接插入排序的区别： 在查找位置时使用折半查找。在查找位置时使用折半查找。例: 在有序集(13,42,46,55,94) 中插入17和46lowmidhighhigh 1
7、 2 3 4 5 6 7 8 913 42 46 55 94 lowmid 插入17 mid high1 2 3 4 5 6 7 8 913 17 42 46 55 9410插入46lowmidhighhigh low mid lowmid 1 2 3 4 5 6 7 8 913 17 42 46 46 55 941 2 3 4 5 6 7 8 913 17 42 46 55 9411void binsort(SqList &L)for(i=2；iL.length；i+) L.r0=L.ri； low=1； high=i-1； while(low high) /以下折半查找确定插入位置以下折半
8、查找确定插入位置high+1 mid=(low + high)/2； if(L.r0.keyL.rmid.key) high=mid-1； else low = mid+1； ； for(k=i-1；khigh+1；k-) L.rk+1=L.rk；L.rhigh+1=L.r0； /end_for /binsort 12性能分析：性能分析：(1)时间：时间：减少了与关键字比较的次数，记录移动次数不变。最好情况最好情况： 只需比较，不需移动。 比较次数：O(nlog2n)最坏情况：最坏情况：O(n2)；平均时间：平均时间： T(n)=O(n2)(2)空间：空间： 一个记录空间。S(n)=O(1)；
9、(3)稳定性：稳定性： 稳定的排序方法。稳定的排序方法。13基本思想：基本思想：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入组内进行直接插入排序排序；然后取d2=5时，时，di= (di-1+1)/2 否则：否则：di = (di-1+1)/3 又称又称“缩小增量缩小增量”排序排序14例：初始关键字如下：例：初始关键字如下：n=11， d1=5，d2=3，d3=1 49 38 65 97 76 13 27 49 55 04 1010 27 49 55 04 13 38 65 97 76 4910 04 13 38 27 49 55 49 97 76 65例1：当n=10时
10、， d1=5， d2=3， d3=1。例2：n=27时，d1=13， d2=7，d3=4，d4=1。04 10 13 27 38 49 49 55 65 76 9715在每一趟shell排序中，可对相距为dk的dk组子序列分别进行直接插入排序。设增量为step， 则step个子序列分别是：(1) r1， rstep+1， r2step+1， (2) r2， rstep+2， r2step+2， (step) rstep， r2step， r3step， ijijiiijjjj16例49 38 65 97 76 13 27 48 55 4ji49133827一趟排序一趟排序： 13 27 48
11、55 4 49 38 65 97 76jiji274jiji5538jijiji二趟排序二趟排序： 13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji7641 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10ji增量序列：增量序列：int d=5，3，1;17void shellpass(SqList &L，int step)/将将L.r1.n按间距按间距step分组进行一趟分组进行一趟shell排序排序for(i=step+1;iL.length;i+) /从每组第二个元起处理从每组第
12、二个元起处理 temp=L.ri； j=i-step； while(j1 & temp.keyd1d2 dt=1每一趟shell排序已用函数shellpass实现，共需要共需要t 趟趟，其中第i趟的增量为di。void shellsort (SqList &L，int dt) for(k=0；kri+1.key，则ri ri+1， (i=1n-1) 一趟起泡后，最大的元素就落在最底部。 第二趟起泡排序的范围是r1 . n-1； 直到没有任何交换；直到没有任何交换；最多需要最多需要n-1趟冒泡排序趟冒泡排序10.2.1 冒泡排序冒泡排序20 37，18，64，14，96，48，96，42 例:
13、关键字序列 (37, 18, 64, 14, 96, 48, 96, 42)第第1趟结果趟结果 18，37，14，64，48，96，42 9618，3714，6448，9642，9614，3748，64第第2趟结果趟结果 18，14，37，48，42，64 96 96第第3趟结果趟结果 14，18，37，42，48 64 96 96第第4趟结果趟结果 14，18，37，42，48 64 96 9642，9614，1842，48无交换，完成。无交换，完成。21void bubblesort(SqList &L)/设一个标志设一个标志flag，当本趟有交换则，当本趟有交换则flag置为置为1，否则
14、为，否则为0 。 i=1； /初始化，初始化，i为趟数为趟数 while(iL.rj+1.key） L.rj L.rj+1； flag=1； if (flag) i+ ； /如果有交换，进行下一趟如果有交换，进行下一趟 else break； /bubblesort22性能分析：性能分析：(1) 时间：时间：最好情况最好情况：初始序列已经有序，只需一趟冒泡排序，不交换任何元素。T= O(n)最坏情况最坏情况：初始序列与目标序列的顺序相反。 T=O(n2)(2) 空间：空间： 一个记录空间。S(n)=O(1)；(3) 稳定性：稳定性： 稳定的排序方法。稳定的排序方法。平均情况平均情况T=O(n2
15、)2310.2.2 快速排序快速排序 基本思想： 在待排序列中选一个关键字，按某一规律进行多次比较交换后，它移到某一位置，此元素将记录分割成独立的两部分，它它左边的关键字都小于或等于它，右边的关键字都大于或等于它。之后对这两部分分别之后对这两部分分别进行快速排序进行快速排序24s k-1 k k+1 t k-1 k+1 s k txs t25 第四次交换第四次交换 68 11 70 23 70 18 93 73 例：例： 70 73 70 23 93 18 11 68第一次交换第一次交换 68 73 70 23 93 18 11 70 第二次交换第二次交换 68 70 70 23 93 18
16、11 73ijiji 第三次交换第三次交换 68 11 70 23 93 18 70 73iij 第五次交换第五次交换 68 11 70 23 18 70 93 73i 完成一趟排序完成一趟排序 68 11 70 23 18 70 93 7326完成一趟排序完成一趟排序 68 11 70 23 18 70 93 73ij第第1次交换：次交换： 18 11 70 23 68 jii第第2次交换：次交换： 18 11 68 23 70 第第3次交换：次交换： 18 11 23 68 70 i完成两趟排序：完成两趟排序： 18 11 23 68 70 ij 73 93i 73 93第第1次交换次交换
17、 ： 18 11 23ijj第第2次交换次交换 ： 11 18 23i完成三趟排序：完成三趟排序：11 18 23 27快速排序快速排序 (分两步分两步) )：(1) (1) 求划分元素的位置。求划分元素的位置。(2) (2) 分别对两个子序列进行分别对两个子序列进行快速排序快速排序。void qksort(SqList &L，int s，int t) if (st) k=partition(L，s，t)；/求划分元素的位置求划分元素的位置 qksort(L，s，k-1)； qksort(L，k+1，t) /qksort 28int partition(SqList &L，int s，int
18、t) /对对L.rst中的记录进行一趟快速排序，返回中的记录进行一趟快速排序，返回k的值，当的值，当uk时，时，L.ru.key L.rk.key，当，当kv时，时，L.rk.key L.rv.key i=s； j=t； while(ij) while (ij & L.ri.keyL.rj.key) j-； L.ri L.rj； while (ij & L.ri.key L.rj.key) i+； L.ri L.rj； return i； / partition29性能分析：性能分析：(1) 时间：时间：最坏情况最坏情况：初始序列已经有序或基本有序，则划分不能将序列划分成两个子序列。T=O(n
19、2)最好情况最好情况：初始序列分布比较均匀，划分将序列划分成长度近似相等的两个子序列。T =O(nlog2n) 例：例：4 1 3 2 6 5 7平均情况：平均情况： O(nlog2n)(2) 空间：空间： 最好情况：最好情况：S(n)=O(log2n) 最坏情况：最坏情况：S(n)=O(n)(3) 稳定性：稳定性： 方法不稳定方法不稳定。30第1趟：在r1.n中进行n-1次比较，选择最小的rk，让rk r1；第i趟：在ri.n中进行n-i次比较，选择最小的rk，让rk ri；第n-1趟：在rn-1.n中进行1次比较，选择最小的rk，让rk rn-1；第i趟：在n-i+1(i=1，2，n-1)
20、个记录中选择值最小的记录作为有序序列的第i个记录。10.3.1 直接选择排序直接选择排序31例：数组：（37，18，64，14，96，48，42）第1 趟结果 14 18，64，37，96，48，42(i=2，k=2)第2趟结果 14 18 64，37，96，48，42(i=3,k=4)第3趟结果 14 18 37 64，96，48，42 (i=4，k=7)第4趟结果 14 18 37 42 96，48，64(i=5，k=6)当i=1时 : 37，18，64，14，96，48，42(i=1，k=4)第5趟结果 14 18 37 42 48 96，64(i=6，k=7)第6趟结果 14 18 3
21、7 42 48 64 9632void selectsort(SqList &L) for(i=1；iL.length；i+) k=i； for(j=i+1；jL.length；j+) if(L.rj.keyL.rk.key) k=j； if(ki) L.rk L.ri /selectsort时间：时间：33性能分析：性能分析：(1) 时间：时间： 该算法不受初始序列特征的影响。该算法不受初始序列特征的影响。 T(n)= O(n2)(2) 空间：空间： 一个记录空间：一个记录空间：S(n)= O(1）(3) 稳定性：稳定性： 不不稳定的排序方法。稳定的排序方法。例：（6，6，4）3410.3.
22、2 树型选择排序树型选择排序 又称锦标赛排序。 基本思想：基本思想：首先对n个记录的关键字进行两两比较，然后在其中 n/2 个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。 这个排序过程可用一棵有有n个叶子结点的个叶子结点的完全二叉树完全二叉树表示。35输出最小关键字之后，将该关键字对应的叶子结点中的关键字改为最大值，然后从该叶子结点开始，和其左（右）兄弟的关键字进行比较， 49389765132776493865132738131336含n个叶子结点的完全二叉树的深度为 log2n +1， 除了最小的关键字之外，每选择一个次小关键字需进行log2n次比较。缺点：缺点：(1
23、) 辅助存储空间较多，对辅助存储空间较多，对n个记录需个记录需2n-1个存储单元。个存储单元。(2) 和最大值的比较是多余的。和最大值的比较是多余的。T(n) = O(nlog2n)493897651327764938651327381313 76272737堆：堆：n个元素的序列k1，k2，kn，当且仅当满足以下关系时，称之为堆堆。 ki k2i ki k2i ki k2i +1 ki k2i +110.3.3 堆排序堆排序或i=1，2， ，n/2小根堆小根堆大根堆大根堆若将此序列看成是完全二叉树的按层次遍历的序列，则完全二叉树中所有非终端结点的值均不大于(或不小于)其左右孩子的值。2i2i
24、+1i38例：序列96，83，27，38，11，09 对应的完全二叉树为：大根堆96832738110939例：序列12，36，24，85，47，30，53，91 对应的完全二叉树为：小根堆小根堆123624854730539140堆排序：堆排序：输出堆顶的最小值之后，使得剩余的n-1个元素的序列重又建成一个堆重又建成一个堆，则得到次小值，如此反复执行，便得到有序序列。实现堆排序需解决两个问题：实现堆排序需解决两个问题：(1) 如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？(2) 如何在输出堆顶元素之后，调整剩如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？余元素成为一个新的
25、堆？41堆排序：堆排序：已知一个堆，将堆顶元素堆顶元素与堆中最后一个最后一个元素元素交换，之后只需调整根结点即可。12362485473053911291429136248547305312筛选：筛选：自堆顶到叶子的调整过程。自堆顶到叶子的调整过程。假设 rk+1 . m中各元素已满足堆的性质，编写筛选算法 sift 调整rk， 使整个序列rk . m中各元素满足堆的性质。91912430itjjiji43void sift(SqList &L，int k，int m)/ L.rk. m是以是以L.rk为根的完全二叉树为根的完全二叉树 ，以，以L.r2k和和/L.r2k+1为根的完全二叉树满足
26、堆的性质，调整为根的完全二叉树满足堆的性质，调整L.rk， 使使整整/个序列个序列L.rk . m中各元素满足堆的性质。中各元素满足堆的性质。 i=k； j=2*i； t=L.rk； while (jm) if(jm & L.rj+1.key L.rj.key) j+； / 在在i的左右孩子中选小的为的左右孩子中选小的为j if(t.keyL.rj.key) break； else L.ri=L.rj；i=j；j=2*i； ； L.ri=t；最坏时间：最坏时间： log2n +1-1= log2(m-k+1) 44初始初始建堆：建堆： 从一个无序序列建堆的过程就是一个反从一个无序序列建堆的过程
27、就是一个反复复“筛选筛选”的过程。的过程。 将 n 个元素的序列看成是一个完全二叉树，则最后一个非叶子结点是第n/2个元素。 从第n/2个元素开始筛选，一直筛选到第1个元素，就建立了堆。45例：已知序列 49，38，65，97，76，13，27，49， 将此序列初始建堆。从 i=4开始：i=3时，调整49386597761327499749651349491327i=2不用调整i=1时，调整46973827497665491313382749766549972797堆排序如下：堆排序如下：974997384949766527133849499776652713筛选后筛选后47654949977
28、6382713筛选后筛选后49654997763827137665499749382713筛选后筛选后4965769749382713489765764949382713筛选后筛选后65977649493827137697654949382713977665494938271349void heapsort(SqList &L)/对对L.r1.L.length进行堆排序，使进行堆排序，使L.r1.L.length按关键字按关键字从大到小有序从大到小有序 for(i=L.length/2；i1；i-) sift(L.r，i，L.length)； /以以ri为根初始建队为根初始建队 for(i=L
29、.length；i2；i-) L.ri L.r1； sift(L.r，1，i-1)；/调整调整r1，使，使r1.i-1是堆是堆 ； /heapsort50(n*log2n)/2 +n*log2n=(3*n*log2n)/2平均时间：平均时间： T(n)=O(n*log2n)(2) 空间空间： 一个记录空间。 S(n)=O(1)；(3) 稳定性：稳定性： 不稳定的排序方法。 适合大量记录的排序。性能分析：性能分析：(1) 时间：时间：最坏情况：最坏情况：T=-+-=niniiin222/121)(log) 1(log51归并归并：将两个或两个以上的有序表有序表合并成一个有序表二路归并二路归并：将
30、两个有序表合并成一个有序表。多路归并：多路归并：将两个以上的有序表合并成一个有序表。二路归并排序：二路归并排序： 设初始序列含有n个记录，归并排序把此序列看成是由n个只包含一个记录的有序表组成，然后进行两两归并，最后形成包含n个记录的有序表。52例：已知关键字序列： 46，55，13，42，94，05，17，70，60 第一趟：46 5513 4205 9417 7060第二趟：13 42 46 5505 17 70 9460第三趟：05 13 17 42 46 55 70 9460第四趟：05 13 17 42 46 55 60 70 94 归并排序过程如下：初始状态：46551342940
31、517706053算法：算法： 假设n个记录的序列放在数组r1.n中，设 L为归并段（子表）的长度，在一趟归并中要进行两两归并，分别使长度为 L 的两两相邻的子表归并为一个有序的子表。开始时取 L=1；第一趟归并排序后，L=L*2；再进行下一趟归并， ，直到排序结束。子表的长度子表的长度L分别：分别： 1，2，4，8，2i-154 已知： rs.m和 rm+1.n分别按关键字有序，本算法将其归并为一个有序序列，归并后的结果存放在数组 r1s.n 中。设变量 i， j分别指向两个归并段的开始位置， rs . m rm+1 . n i所指的关键字与j所指的关键字进行比较， 取小者放在结果数组r1中
32、。ij算法算法1:两个相邻的有序表归并成一个有序表两个相邻的有序表归并成一个有序表merge(r，r1，s，m，n)55void merge(RecordType r ，RecordType &newr ，int s，int m，int n)/已知数组已知数组rs.m和和rm+1.n分别按关键字有序，将它们归并分别按关键字有序，将它们归并新新/数组数组newrs.n中，使中，使newrs.n按关键字有序按关键字有序 i=s； j= m+1； k= s-1； /初始化初始化 while (im & jn) k+； / 插入位置插入位置 if(ri.keyrj.key) newrk=ri； i+；
33、 else newrk=rj； j+ ； while(im) k+；newrk=ri；i+； while(jn) k+；newrk=rj；j+； /merge 56算法算法2: 一趟归并一趟归并 mergpass(r，r1，L，n) 两段等长数组的归并：两段等长数组的归并： 从待排序列的第一个记录开始，按归并长度L进行“两两归并两两归并”， 设变量i记录第一个归并段的起始位置。则相邻的两个归并段的位置如下：开始时 i=1，相邻的两段归并完成后 i=i+2*L；再进行下两个归并段的归并。循环的条件循环的条件：下两个归并段存在存在；即： i+2L-1 n 两段不等长数组的归并两段不等长数组的归并;
34、 (最后一段长度 L) 最后一段的长度最后一段的长度L； i i+L-1 i+L i+2L-157void mergpass(RecordType r ， RecordType &r1， int L，int n)/将数组将数组r中长度各为中长度各为L的相邻的两个子列归并为长度为的相邻的两个子列归并为长度为2L的子的子/列列,归并后的结果存入数组归并后的结果存入数组r1中；中；n为数组总长度。为数组总长度。 i=1； while (i+2*L-1n) / 够两组时归并够两组时归并 merge(r，r1，i，i+L-1，i+2*L-1)；/两组归并两组归并 i = i+2*L ； if(i+L-1
35、n) merge(r，r1，i，i+L-1，n)； / 剩余数据比一组多，但不够两组剩余数据比一组多，但不够两组 else r1i.n= ri.n； /剩余数据不超过一组剩余数据不超过一组 / mergpass58算法算法3: 2-路归并排序算法路归并排序算法void mergsort(SqList &LS )/对数组对数组LS.r中的记录进行中的记录进行2-路归并排序，路归并排序，temp为辅助数组为辅助数组 m =1； /子列长度初始化子列长度初始化 while (mLS.length) mergpass(LS，temp，m，LS.length)； /将将LS.r按长度按长度L归并到归并到
36、temp数组中数组中 LS.r1.LS.length=temp1.LS.length； /将一趟排序结果回送到将一趟排序结果回送到r中中 m = 2*m； /改变子列长度改变子列长度 /mergsort59性能分析性能分析：（1）时间：）时间：时间为归并趟数归并趟数与每一趟时间每一趟时间复杂性的乘积。归并趟数为 log2n 。每一趟的比较次数和移动次数均等于数组中记录的个数 n。 T(n) = O(nlog2n)（2）空间复杂度：）空间复杂度： S(n) = O(n)（3）稳定性：）稳定性： 是稳定的排序方法。是稳定的排序方法。60多关键字排序多关键字排序例: 对52张扑克牌按以下次序排序：
37、两个关键字：花色（） 面值（23A）并且“花色”地位高于“面值” 23A23A23A23A61两种方法：两种方法：(1)最高位优先最高位优先 (MSD)先对最高位关键字k1(如花色)排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2(如面值)排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列(2) 最低位优先最低位优先 (LSD)先对最低位关键字kd起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列62MSD与与LSD不同特点不同特点v按
38、按MSD排序排序 必须将序列逐层分割成若干子序列，然后对各子序列分别排序v按按LSD排序排序不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配分配与收集收集实现排序63链链式基数排序式基数排序基数排序：基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法链链式基数排序：式基数排序：用链表作存储结构的基数排序存储结构：存储结构：使用静态链表静态链表存储 n 个待排记录。以下的例子设基数d=10。64链链式基数排序的步骤：式基数排序的步骤：设置设置10个队列，fi和ei分别为第i个队列的头指针和尾指针。第一趟分配对最低位关键字（个位）进行，改变记
39、录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列65例例初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：66
40、505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：67008063083109184269278505589930三趟收集三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集：二趟收集：68算法评价算法评价l时间复杂度：时间复杂度：u分配：T(n)=O(n)u收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：n记录数 d关键字数 rd关键字取值范围 l空间复杂度空间复杂度：S(n)=2rd个队列指针+n个指针域空间69 谢谢同学们 再见！70
