大学教程零起点数据结构-排序课件.ppt

1、1/27/20231直接插入排序（基于顺序查找）直接插入排序（基于顺序查找）表插入排序（基于链表存储）表插入排序（基于链表存储）折半插入排序（基于折半查找）折半插入排序（基于折半查找）希尔排序（基于逐趟缩小增量）希尔排序（基于逐趟缩小增量）直接插入排序（基于顺序查找）直接插入排序（基于顺序查找）直接插入排序思想：直接插入排序思想：依次将待排序记录中的第依次将待排序记录中的第i个记录插入到有序序列中个记录插入到有序序列中.初始情况：将初始情况：将r1作为有序序列，将作为有序序列，将r2-rn逐个插入逐个插入,通过顺序查找方式找到通过顺序查找方式找到ri在有序表中的位置在有序表中的位置,找位置的同

2、时移动有序序列中元素的位置找位置的同时移动有序序列中元素的位置,找位置时从后向前找找位置时从后向前找.在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。直接插入排序（基于顺序查找）直接插入排序（基于顺序查找）初始关键字初始关键字35 48351845 12 68334835第一趟排序第一趟排序48351845 12 6833步骤：步骤：i=2i=2riri存入存入r0r0位置位置将将r0r0关键字与关键字与rjrj关键字比较（关键字比较（j j从从i-1i-1开始到开始到1 1）若若r0rjr0rj则则rjrj存入存入

3、rj+1rj+1位置位置，j j减减1 1r0r0存入存入rj+1rj+1位置位置r0为监视哨为监视哨直接插入排序（基于顺序查找）直接插入排序（基于顺序查找）初始关键字初始关键字351845 12 68334835第二趟排序第二趟排序48351845 12 6833步骤：步骤：i=3i=3riri存入存入r0r0位置位置将将r0r0关键字与关键字与rjrj关键字比较（关键字比较（j j从从i-1i-1开始到开始到1 1）若若r0rjr0rj则则rjrj存入存入ri+1ri+1位置，位置，j j减减1 1r0r0存入存入rj+1rj+1位置位置18483518r0为监视哨为监视哨直接插入排序（基

4、于顺序查找）直接插入排序（基于顺序查找）初始关键字初始关键字45 12 6833第三趟排序第三趟排序48351845 12 6833步骤：步骤：i=4i=4riri存入存入r0r0位置位置将将r0r0关键字与关键字与rjrj关键字比较（关键字比较（j j从从i-1i-1开始到开始到1 1）若若r0rjr0rj则则rjrj存入存入rj+1rj+1位置，位置，j j减减1 1r0r0存入存入rj+1rj+1位置位置18483518454845r0为监视哨为监视哨直接插入排序（基于顺序查找）直接插入排序（基于顺序查找）初始关键字初始关键字 12 6833第四趟排序第四趟排序48351845 12 6

5、833步骤：步骤：i=5i=5riri存入存入r0r0位置位置将将r0r0关键字与关键字与rjrj关键字比较（关键字比较（j j从从i-1i-1开始到开始到1 1）若若r0rjr0rj则则rjrj存入存入rj+1rj+1位置，位置，j j减减1 1r0r0存入存入rj+1rj+1位置位置3518454845 12 48453518 12 r0为监视哨为监视哨直接插入排序（基于顺序查找）直接插入排序（基于顺序查找）初始关键字初始关键字 48 35 18 45 12 68 3335 48 18 45 12 68 3318 35 48 45 12 68 3318 35 45 48 12 68 331

6、2 18 35 45 48 68 3312 18 35 45 48 68 3312 18 33 35 45 48 68【例】打扑克牌时的抓牌就是插入排序一个很好的例子，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。已知一组键值序列已知一组键值序列（2222，2424，2626，2525，2727，2929，2121，2828），），试给出采用直接插入排序法对该组序列试给出采用直接插入排序法对该组序列作升序排序的每一趟结果作升序排序的每一趟结果 试写出直接插入排序算法试写出直接插入排序算法 设顺序表设顺序表vava中的数据元素递增有序。试编写算法实中的数据元素递增有序。试编写

7、算法实现将现将x x插入到顺序表的适当位置上，以保持该表的有插入到顺序表的适当位置上，以保持该表的有序性序性 用插入排序算法对数据序列用插入排序算法对数据序列（4747，3333，6161，8282，7272，1111，2525，5757）进行排序，写出整个插入排序的每一趟过程。进行排序，写出整个插入排序的每一趟过程。直接插入排序（基于顺序查找）直接插入排序（基于顺序查找）Void StraightSort（list r,int n）for（i=2；i=n;i+）r0=ri;j=i-1;while(r0.key rj.key)rj+1=rj;j-;rj+1=r0;r0为监视哨为监视哨该算法时间

8、复杂度为该算法时间复杂度为O（n2）该算法空间复杂度为该算法空间复杂度为O（1）该算法是稳定的排序算法该算法是稳定的排序算法设顺序表设顺序表vava中的数据元素递增有序。试编写算法实现将中的数据元素递增有序。试编写算法实现将x x插入到顺序表的适当位置上，以保持该表的有序性插入到顺序表的适当位置上，以保持该表的有序性Va类型定义类型定义typedef struct int key；anytype others；record；define maxsize 100typedef struct record itemmaxsize+1;/记录数组，从记录数组，从1到到n int n;/记录条数记录条

9、数list；Void Sort（list va，record x）i=va.n；while()ri+1=ri;i-;ri+1=x;x.key=1实现排序的基本操作有两个：（1）“比较”序列中两个关键字的大小；（2）“移动”记录。最好的情况（关键字在记录序列中顺序有序）：最坏的情况（关键字在记录序列中逆序有序）：时间复杂度为O(n2)1/27/202318折半插入排序（基于折半查找）折半插入排序（基于折半查找）折半插入排序思想：折半插入排序思想：依次将待排序记录中的第依次将待排序记录中的第i个记录插入到有序序列中个记录插入到有序序列中初始情况：将初始情况：将r1作为有序序列，将作为有序序列，将r

10、2-rn逐个插入逐个插入通过折半查找方式找到通过折半查找方式找到ri在有序表中的位置在有序表中的位置找位置后，移动有序序列中元素的位置找位置后，移动有序序列中元素的位置希尔排序（分组插入排序）希尔排序（分组插入排序）21希尔排序应用实例1/27/202321取取d3=1三趟分组：三趟分组：13 27 48 55 4 49 38 65 97 76三趟排序结果：三趟排序结果：4 13 27 38 48 49 55 65 76 97 初始初始：49 38 65 97 76 13 27 48 55 4一趟排序结果：一趟排序结果：13 27 48 55 4 49 38 65 97 76二趟排序结果：二趟

11、排序结果：13 4 48 38 27 49 55 65 97 76取取d1=5一趟分组：一趟分组：49 38 65 97 76 13 27 48 55 4取取d2=3二趟分组：二趟分组：13 27 48 55 4 49 38 65 97 76所谓交换排序所谓交换排序就是将待排序序列中的两个键值比较，就是将待排序序列中的两个键值比较，根据比较结果，交换两个记录的位置根据比较结果，交换两个记录的位置冒泡排序冒泡排序快速排序快速排序冒泡排序冒泡排序冒泡排序是最简单的交换排序算法冒泡排序是最简单的交换排序算法算法思想：算法思想：将第一个记录键值与第二个比较，若符合条件则交换将第一个记录键值与第二个比较

12、，若符合条件则交换将第二个记录键值与第三个比较，若符合条件则交换将第二个记录键值与第三个比较，若符合条件则交换将第三个记录键值与第四个比较，若符合条件则交换将第三个记录键值与第四个比较，若符合条件则交换冒泡排序需要进行多少趟排序？冒泡排序需要进行多少趟排序？若某趟排序未进行交换，则算法停止若某趟排序未进行交换，则算法停止 j从从1开始到开始到n将第将第j个记录键值与个记录键值与第第j+1个比较个比较若符合条件则交换若符合条件则交换这这是是第第一一趟趟排排序序过过程程交换条件是：第交换条件是：第j个大于第个大于第j+1个记录则交换个记录则交换第一趟排序后第一趟排序后最后一个记录最后一个记录已排至

13、合适位已排至合适位置，第二趟排置，第二趟排序对序对1到到n-1条条记录排序即可记录排序即可第第二二趟趟排排序序后后交换条件是：第交换条件是：第j个大于第个大于第j+1个记录则交换个记录则交换j从从1开始到开始到n-1将第将第j个记录键值与个记录键值与第第j+1个比较个比较若符合条件则交换若符合条件则交换要进行多少趟排序？要进行多少趟排序？1/27/20232749 38 65 97 76 13 27 30初始初始38 49 65 76 13 27 30 97第一趟第一趟38 49 65 13 27 30 76第二趟第二趟38 49 13 27 30 65第三趟第三趟38 13 27 30 49

14、第四趟第四趟13 27 30 38第五趟第五趟13 27 30第六趟第六趟384976971397279730971376767627301365276530651313494930492738273830381.void BubbleSort(int a,int n)2./*将a中整数序列重新排列成自小至大有序的整数序列*/3.for(i=n-1,change=TRUE;i=1&change;-i)4.5.change=FALSE;6.for(j=0;jaj+1)9.10.swap(aj,aj+1);11.change=TRUE;12.13.14.15.重复上述过程，直到“在一趟排序过程中没

15、有进行过交换记录的操作”为止1 1）设置两个搜索指针，）设置两个搜索指针，i i是向后搜索指针初值为是向后搜索指针初值为1 1 j j是向前搜索指针初值为是向前搜索指针初值为n n 且把且把r1r1存入存入r0r0中（中（r1r1为基准记录）为基准记录）2 2）j j逐渐减小，进行逐渐减小，进行rj.keyrj.key 和和r0.keyr0.key比较比较 直到满足直到满足rj.keyrj.key r0.key r0.key r0.key时时 将将riri 移动至移动至rjrj 位置位置4 4）重复）重复2 2，3 3步骤直至步骤直至i=ji=j为止，一趟快速排序完成为止，一趟快速排序完成初始

16、关键字初始关键字48351849 12 6833ij48rj.keyrj.key r0.key r0.key r0.key时将时将riri 移动至移动至rjrj 位置位置4 4，j=j+1j=j+1，重复，重复2 2，3 3步骤，步骤，直到直到i=ji=j时将时将r0r0存入存入riri 位置位置49 12 48第一趟排序完成第一趟排序完成一趟排序后一趟排序后关键字关键字351868i483349 12 48j33 12 351833已知序列已知序列503503，8787，512512，6161，908908，170170，897897，275275，653653，462462请给出采用快速排

17、序法作升序排序时的每一趟的结果。请给出采用快速排序法作升序排序时的每一趟的结果。503503，8787，512512，6161，908908，170170，897897，275275，653653，462462503503ij50350387875125126161908908170170897897275275653653462462462462512512275275908908170170503503第一趟排序结果第一趟排序结果lowlow到到highhigh之间记录进行快速排序之间记录进行快速排序Void quick Void quick（list rlist r，intint low

18、 low，intint high high）i=low i=low；j=highj=high；r0=rir0=ri;if(i if(i=j)return;=j)return;while(ij)while(ij)while(ij&rj.key while(i=r0.key)j-;=r0.key)j-;if(ij)ri=rj if(ij)ri=rj;i+;i+;while(ij&ri.key while(ij&ri.key=r0.key)i+;=r0.key)i+;if(ij)rj=ri if(ij)rj=ri;j-;j-;ri ri=r0=r0 quick(r,low,i-1);quick(r,

19、i+1,high)quick(r,low,i-1);quick(r,i+1,high)用快速排序法对数据序列用快速排序法对数据序列(49(49，3838，6565，9797，1616，5353，134134，2727，39)39)进行排序，写出其第一趟排序的全过程进行排序，写出其第一趟排序的全过程 4949，3838，6565，9797，1616，5353，134134，2727，39394949ij快速排序快速排序时间复杂度：时间复杂度：O O（nlognnlogn）该算法不稳定该算法不稳定 若数据序列本身有序，若数据序列本身有序，则算法执行效率最低，近似则算法执行效率最低，近似O O（n

20、n2 2）7.4 7.4 选择排序选择排序直接（简单）选择排序算法思想直接（简单）选择排序算法思想首先从待排序序列中选取最小记录，把它与第一个首先从待排序序列中选取最小记录，把它与第一个记录交换，然后在剩余的记录中选择最小记录与第记录交换，然后在剩余的记录中选择最小记录与第二个记录进行交换，直至排序完成二个记录进行交换，直至排序完成直接（简单）选择排序直接（简单）选择排序堆排序堆排序初始关键字：初始关键字：5151 33 62 96 87 33 62 96 87 1717 28 28 5151 第一趟排序：第一趟排序：17173333 62 96 87 51 62 96 87 51 2828

21、5151第二趟排序：第二趟排序：17 28 17 28 6262 96 87 51 96 87 51 3333 5151第三趟排序：第三趟排序：17 28 33 17 28 33 9696 87 87 5151 62 62 5151第四趟排序：第四趟排序：17 28 33 51 17 28 33 51 8787 96 62 96 62 5151第五趟排序：第五趟排序：17 28 33 51 17 28 33 51 5151 96 96 62 62 87 87第六趟排序：第六趟排序：17 28 33 51 17 28 33 51 5151 62 62 9696 8787第七趟排序：第七趟排序：1

22、7 28 33 51 17 28 33 51 5151 62 87 96 62 87 96N N个数据需要多少趟排序？个数据需要多少趟排序？直接选择排序算法直接选择排序算法Void select Void select（list rlist r，intint n n）for(i=1;i=n-1;i+)for(i=1;i=n-1;i+)k=i;k=i;for(j=i+1;j=n;j+)for(j=i+1;j=n;j+)if(rj.key rk.key if(rj.key rk.key)k=j;)k=j;if(k!=i)swap(rk,ri if(k!=i)swap(rk,ri););时间复杂度：

23、时间复杂度：O O（n n2 2）直接选择排序是不稳定的直接选择排序是不稳定的7.4 7.4 选择排序选择排序基本思想：对基本思想：对n n个待排序记录的关键字进行两两比较，个待排序记录的关键字进行两两比较，从中选出从中选出n/2n/2个较小者再两两比较，直到选出关键字最个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。小的记录为止，此为一趟排序。一趟选出的关键字最小的记录称为一趟选出的关键字最小的记录称为“冠军冠军”，而，而“亚亚军军”是从与是从与“冠军冠军”比较失败的记录中找出。比较失败的记录中找出。输出输出“冠军冠军”后，将（冠军）叶子结点关键字改为最后，将（冠军）叶子结点

24、关键字改为最大，继续进行锦标赛排序，直到选出关键字次小的记大，继续进行锦标赛排序，直到选出关键字次小的记录为止，如此循环直到输出全部有序序列。录为止，如此循环直到输出全部有序序列。对关键字序列对关键字序列 72,73,71,23,94,16,05,6872,73,71,23,94,16,05,68进行树形选择排序进行树形选择排序 05230572231605727371239416056872,23,16 0572,23,16 05“亚军亚军”是从与是从与“冠军冠军”比较失败的记录中找出比较失败的记录中找出的的72,73,71,23,94,16,6872,73,71,23,94,16,6805

25、0516231672231668687273712394166816堆排序堆排序 是一种改进的树形排序是一种改进的树形排序堆是满足下列性质的数列堆是满足下列性质的数列r1,r2,，rn：或或122iiiirrrr122iiiirrrr堆的定义堆的定义:(小顶堆小顶堆)(大顶堆大顶堆)12,36,27,65,40,34,98,81,73,55,4912,36,27,65,40,14,98,81,73,55,491 2 3 4 5 6 7 8 9 10 1112,36,27,65,40,34,98,81,73,55,49是小顶堆是小顶堆1236276581735540984934122iiiirr

26、rr12,36,27,65,40,14,98,81,73,55,49不是堆不是堆1236276581735540984914堆排序的基本思想是：堆排序的基本思想是：首先将待排序的记录序列首先将待排序的记录序列构造一个堆构造一个堆，此时，选，此时，选出了堆中所有记录的出了堆中所有记录的最小者或最大者最小者或最大者，然后将它，然后将它从堆从堆中移走中移走，并将剩余的记录，并将剩余的记录再调整成堆再调整成堆，这样又找出了，这样又找出了次小（或次大）的记录，以此类推，直到堆中只有一次小（或次大）的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。个记录为止，每个记录出堆的顺

27、序就是一个有序序列。两个问题：两个问题：1 1，输出堆顶后，如何调整堆，输出堆顶后，如何调整堆2 2，如何建立一个堆，如何建立一个堆1480754618636184646146148075636184646146143618361875367536804680467536141880756466183663618已知一组键值序列已知一组键值序列（3232，4444，3838，6565，5353，4242，2929，5757），），试采用堆排序法对该组序列作升序排序，试采用堆排序法对该组序列作升序排序，给出建立的初始堆给出建立的初始堆以及第一次输出堆元素后筛选调整的堆以及第一次输出堆元素后筛选调

28、整的堆32324444383865655353424229295757已知一组键值序列已知一组键值序列（3232，4444，3838，6565，5353，4242，2929，5757），），试采用堆排序法对该组序列作升序排序，试采用堆排序法对该组序列作升序排序，给出建立的初始堆给出建立的初始堆以及第一次输出堆元素后筛选调整的堆以及第一次输出堆元素后筛选调整的堆32324444383865655353424229295757575765652929383829293232已知一组键值序列已知一组键值序列（3232，4444，3838，6565，5353，4242，2929，5757），），试采用

29、堆排序法对该组序列作升序排序，试采用堆排序法对该组序列作升序排序，给出建立的初始堆给出建立的初始堆以及第一次输出堆元素后筛选调整的堆以及第一次输出堆元素后筛选调整的堆32324444383865655353424229295757575765652929383829293232292965656565323238386565 已知一组键值序列已知一组键值序列（3333，3737，2626，4343，5555，6767，4242，3838），），试采用堆排序法对该组序列作升序排序，试采用堆排序法对该组序列作升序排序，给出建立的初始堆，给出建立的初始堆，以及第一次输出堆元素后筛选调整的堆。以及第一

30、次输出堆元素后筛选调整的堆。画出对应于序列画出对应于序列1010，2020，7 7，7575，4141，6767，3 3，9 9，3030，4545的初始堆（堆顶元素取最小值）。的初始堆（堆顶元素取最小值）。设要将序列设要将序列（Q Q，H H，C C，Y Y，P P，A A，M M，S S，R R）按字母升序排序，）按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆形态。以及第一次输出堆顶元素后经过筛选调整的堆形态。什么是堆什么是堆?写出对应于序列写出对应于序列(10(10，2020，7 7，7575，41

31、41，6767，3 3，9 9，3030，45)45)的初始堆的初始堆(堆顶元素取最小值堆顶元素取最小值)。7.5 7.5 归并排序归并排序基本思想：基本思想：将多个有序序列合并成一个有序序列将多个有序序列合并成一个有序序列将两个有序子序列合并为一个有序序列将两个有序子序列合并为一个有序序列 称为称为2 2路归并排序路归并排序写出键值写出键值8383，4040，6363，1313，8484，3535，9696，5757，3939，7979，6161，1515应用二路归并排序算法从小到大排序后各趟的结果。应用二路归并排序算法从小到大排序后各趟的结果。83834040636313138484353

32、5 9696 5757 3939 7979 6161 1515404083831313636335358484 5757 9696 3939 7979 1515 6161131340406363838335355757 8484 9696 1515 3939 6161 7979131335354040575763638383 8484 9696 1515 3939 6161 7979131315153535393940405757 6161 6363 7979 8383 8484 9696两个有序序列两个有序序列A A，B B如何合并成一个有序序列？如何合并成一个有序序列？1313353540

33、40575763638383 84841515 3939 6161 7979i ij j合并至合并至A A序列序列合并形成新序列合并形成新序列C Ck k两个有序序列如何合并成一个有序序列？两个有序序列如何合并成一个有序序列？设设i i，j j是两个有序序列中的记录下标，是两个有序序列中的记录下标，m m，n n是两个是两个序列长度，序列长度，RR是新的合并后的序列，下表从是新的合并后的序列，下表从k k开始开始1 1，imim且且jnjmim或或jnjn时，将对应序列中的剩余部分存入时，将对应序列中的剩余部分存入R R中中13133535 40405757636383838484 96961

34、515393961617979i ij jk k13131515 35353939404057576161 63637979838384849696有序序列的合并算法有序序列的合并算法Void mergeVoid merge（list alist a，list blist b，list clist c）i=1 i=1；j=1;k=1;j=1;k=1;while while（ian&jbnian&jbn）if(if(ai.key bj.keyai.key bj.key)ck=ai ck=ai;i+;k+;i+;k+;else else ck=aj ck=aj;j+;k+;j+;k+;/循环结束后

35、是否所有记录已存入循环结束后是否所有记录已存入c c中？中？有序序列的合并算法有序序列的合并算法Void mergeVoid merge（list alist a，list blist b，list clist c）/循环结束后是否所有记录已存入循环结束后是否所有记录已存入c c中？中？while(ian)while(ian)ck=ai ck=ai;i+;k+;i+;k+;while(jbn while(jbn)ck=bj ck=bj;j+;k+;j+;k+;写出键值写出键值8383，4040，6363，1313，8484，3535，9696，5757，3939，7979，6161，1515应

36、用二路归并排序算法从小到大排序后各趟的结果。应用二路归并排序算法从小到大排序后各趟的结果。已知一组键值序列已知一组键值序列（1313，1212，1616，1717，1515，1414，1111），），试采用二路归并排序法对该组序列作升序排序试采用二路归并排序法对该组序列作升序排序并给出每一趟的排序结果并给出每一趟的排序结果已知一组键值序列已知一组键值序列(26(26，2121，3232，5656，7878，8989，90)90)，试采用二路归并排序法对该组序列试采用二路归并排序法对该组序列 作升序排序，作升序排序，并给出每一趟的排序结果。并给出每一趟的排序结果。7.6 7.6 分配排序分配排序

37、 -箱（桶）排序箱（桶）排序箱排序也称桶排序箱排序也称桶排序算法思想：算法思想：设置若干个箱子，依次扫描待排序记录，把关键字等于设置若干个箱子，依次扫描待排序记录，把关键字等于K K的记录的记录全部装入第全部装入第k k个箱子（分配过程），然后依次将各个非空的箱子个箱子（分配过程），然后依次将各个非空的箱子首尾连接起来（收集过程）。首尾连接起来（收集过程）。7.6 7.6 分配排序分配排序 -箱（桶）排序箱（桶）排序 78,17,39,26,72,94,21,12 78,17,39,26,72,94,21,12，23,68 23,68 B0B0B1B1B2B2B3B3B4B4B5B5B6B6

38、B7B7B8B8 B9B92626393994947878212172721717桶桶0-100-1020-3020-3040-5040-5060-7060-7080-9080-90121223236868每个桶首尾相连，收集即可得到有序序列每个桶首尾相连，收集即可得到有序序列基数排序是一种借助基数排序是一种借助“多关键字排序多关键字排序”的思想来的思想来实现实现“单关键字排序单关键字排序”的内部排序算法。的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序最低位优先最低位优先LSDLSD法法最高位优先最高位优先MSDMSD法法7.6 7.6 分配排序分配排序 -基数排序基数排

39、序 无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下的排序过程如下:在计算机上实现基数排序时，为减少所需辅助存在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，储空间，应采用链表作存储结构，即链式基数排序，具体作法为：具体作法为：待排序记录以指针相链，构成一个链表；待排序记录以指针相

40、链，构成一个链表；“分配分配”时，按当前时，按当前“关键字位关键字位”所取值，将记所取值，将记录分配到不同的录分配到不同的“链队列链队列”中，每个队列中记录的中，每个队列中记录的 “关键字位关键字位”相同；相同；“收集收集”时，按当前关键字位取值从小到大将各时，按当前关键字位取值从小到大将各队列首尾相链成一个链表队列首尾相链成一个链表;对每个关键字位均重复对每个关键字位均重复 2)2)和和 3)3)两步。两步。对关键字序对关键字序(278,109,063,930,589,184,505,269,008,083)(278,109,063,930,589,184,505,269,008,083)进

41、行基数排序进行基数排序 930930083083063063184184505505008008278278269269589589109109f0f0f1f1f2f2f3f3f4f4f5f5f6f6 f7f7f8f8 f9f9930930083083063063184184505505008008278278269269589589109109f0f0f1f1f2f2f3f3f4f4f5f5f6f6 f7f7f8f8 f9f9收集收集930930063063083083184184505505278278008008109109589589269269收集收集9309300630630830

42、83184184505505278278008008109109589589269269505505930930184184083083f0f0f1f1f2f2f3f3f4f4f5f5f6f6 f7f7f8f8 f9f9063063278278008008109109589589269269收集收集505505008008109109930930063063269269278278083083184184589589收集收集505505008008109109930930063063269269178178083083184184589589008008f0f0f1f1f2f2f3f3f4f4f5f5f6f6 f7f7f8f8 f9f9505505083083589589109109178178930930063063269269184184收集收集008008063063083083109109178178184184269269505505589589930930各种内部排序算法的比较各种内部排序算法的比较