数据结构-使用C语言第4版[朱战立[电子教案第10章课件.ppt

1、1第第1010排序的基本概念排序的基本概念插入排序插入排序选择排序选择排序交换排序归并排序交换排序归并排序基数排序基数排序性能比较性能比较主要知识点主要知识点210.1 10.1 排序的基本概念排序的基本概念 排序排序是对数据元素序列建立某种有序排列的过程是对数据元素序列建立某种有序排列的过程,是把一个数是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。据元素序列整理成按关键字递增（或递减）排列的过程。关键字关键字是要排序的数据元素集合中的一个域，排序是以关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。为基准进行的。主关键字主关键字:数据元素值不同时该关键字的值也

2、一定不同，是能数据元素值不同时该关键字的值也一定不同，是能够惟一区分各个不同数据元素的关键字够惟一区分各个不同数据元素的关键字;不满足主关键字定义不满足主关键字定义的关键字称为的关键字称为次关键字次关键字。内部排序内部排序是把待排数据元素全部调入内存中进行的排序。是把待排数据元素全部调入内存中进行的排序。外部排序外部排序是因数量太大，把数据元素分批导入内存，排好序后是因数量太大，把数据元素分批导入内存，排好序后再分批导出到磁盘和磁带外存介质上的排序方法。再分批导出到磁盘和磁带外存介质上的排序方法。3比较排序算法优劣的标准比较排序算法优劣的标准:(1)时间复杂度时间复杂度:它主要是分析记录关键字

3、的比较次数和记录的它主要是分析记录关键字的比较次数和记录的 移动次数移动次数(2)空间复杂度空间复杂度:算法中使用的内存辅助空间的多少算法中使用的内存辅助空间的多少 (3)稳定性稳定性:若两个记录若两个记录A A和和B B的关键字值相等，但排序后的关键字值相等，但排序后A A、B B的的 先后次序保持不变，则称这种排序算法是稳定的先后次序保持不变，则称这种排序算法是稳定的410.210.2插入排序插入排序 插入排序的插入排序的基本思想基本思想是：是：每步将一个待排序的数据元素，每步将一个待排序的数据元素，按其关键码大小，插入到前面已经排好序的一组数据元素的适按其关键码大小，插入到前面已经排好序

4、的一组数据元素的适当位置上，直到数据元素全部插入为止。当位置上，直到数据元素全部插入为止。1.1.直接插入排序直接插入排序常用的插入排序有常用的插入排序有直接插入排序直接插入排序和和希尔排序希尔排序两种。两种。其基本思想是：其基本思想是：顺序地把待排序的数据元素按其关键字值的大小插入到顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。已排序数据元素子集合的适当位置。5算法如下：算法如下：void InsertSort(DataType a,int n)/用直接插入法对用直接插入法对a0-an-1排序排序 int i,j;DataType temp;for(i=0;

5、i-1&temp.key=aj.key)aj+1=aj;j-;aj+1=temp;6算法分析算法分析:(1)时间效率：时间效率：因为在最坏情况下，所有元素的比较次数总因为在最坏情况下，所有元素的比较次数总和为（和为（01n-1)O(n2)。其他情况下也要其他情况下也要考虑移动元素的次数。考虑移动元素的次数。故时间复杂度为故时间复杂度为O(n2)(2)空间效率：空间效率：仅占用仅占用1个附加内存单元个附加内存单元(3)算法的稳定性：算法的稳定性：稳定稳定764789624564896245764624576489245676489567246489589624初始关键字序列初始关键字序列:第一次

6、排序第一次排序:第二次排序第二次排序:第三次排序第三次排序:第四次排序第四次排序:第五次排序第五次排序:7直接插入排序过程直接插入排序过程 8又称缩小增量排序又称缩小增量排序)(1)(1)基本思想基本思想：把整个待排序的数据元素分成若干个小组，对同把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。当完成了所有数据元素都在一个组内的排序后排序过程结束。(2)(2)技巧：技巧：小组的构成不是简单地小组的构成不是简单地“逐段分割逐段分割”，而是

7、将相隔某，而是将相隔某个增量个增量dkdk的记录组成一个小组的记录组成一个小组,让增量让增量dkdk逐趟缩短（例如依次取逐趟缩短（例如依次取5,3,15,3,1），直到），直到dkdk1 1为止。为止。(3)(3)优点：优点：让关键字值小的元素能很快前移，且序列若基本有序让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。时，再用直接插入排序处理，时间效率会高很多。9算法如下：算法如下：void ShellSort(DataType a,int n,int d,int numOfD)/用希尔排序法对元素用希尔排序法对元素a0-an-1排序，排序，d0-dn

8、umOfD-1为希尔增量值为希尔增量值 int i,j,k,m,span;DataType temp;for(m=0;m numOfD;m+)/共共numOfD次循环次循环 span=dm;/取本次的增量值取本次的增量值 for(k=0;k span;k+)/共共span个小组个小组 /组内是直接插入排序，区别是每次不是增组内是直接插入排序，区别是每次不是增1而是增而是增span for(i=k;i -1&temp.key=aj.key)aj+span=aj;j=j-span;aj+span=temp;1065342587123856461477922356341477122365462587

9、9238结果序列结果序列d=6563414771223654625879238561214653423774625879238结果序列结果序列d=3561214653423774625879238121423253438465665778792结果序列结果序列d=1(a)(b)(c)希尔排序的排序过程希尔排序的排序过程1110.3 10.3 选择排序选择排序 基本思想是：基本思想是：每次从待排序的数据元素集合中选取每次从待排序的数据元素集合中选取关键字关键字最小（或最大）最小（或最大）的数据元素放到数据元素集合的的数据元素放到数据元素集合的最前（或最最前（或最后）后），数据元素集合不断缩小，当

10、数据元素集合为空时选择，数据元素集合不断缩小，当数据元素集合为空时选择排序结束。排序结束。常用的选择排序算法：常用的选择排序算法：（1 1）直接选择排序）直接选择排序 （2 2）堆排序）堆排序12 基本思想是：基本思想是：从待排序的数据元素集合中选取关键字最小从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取关换位置；然后从不包括第一个位置上数据元素的集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第二个数键字最小的数据元素并将它与原始数

11、据元素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。据元素为止。优点：优点：实现简单实现简单缺点：缺点：每趟只能确定一个元素，表长为每趟只能确定一个元素，表长为n n时需要时需要n-1n-1趟趟13算法如下：算法如下：void SelectSort(DataType a,int n)int i,j,small;DataType temp;for(i=0;i n-1;i+)small=i;/设第设第i个数据元素关键字最小个数据元素关键字最小 for(j=i+1;j n;j+)/寻找关键字最小的数据元素寻找关

12、键字最小的数据元素 if(aj.key asmall.key)small=j;/记住最小元素的下标记住最小元素的下标 if(small!=i)/当最小元素的下标不为当最小元素的下标不为i时交换位置时交换位置 temp=ai;ai=asmall;asmall=temp;14645789624564789624567896424567896424567246489567246489初始关键字序列初始关键字序列:第一次排序结果第一次排序结果:第二次排序结果第二次排序结果:第三次排序结果第三次排序结果:第四次排序结果第四次排序结果:第五次排序结果第五次排序结果:567246489最后结果序列最后结果序

13、列:直接选择排序的排序过程直接选择排序的排序过程 15算法分析算法分析时间效率：时间效率：O(nO(n2 2)虽移动次数较少，但比较次数仍多。虽移动次数较少，但比较次数仍多。空间效率：空间效率：O(1)O(1)没有附加单元（仅用到没有附加单元（仅用到1 1个个temp)temp)算法的稳定性：算法的稳定性：不稳定不稳定162.2.堆排序堆排序 基本思想基本思想:把待排序的数据元素集合构成一个完全二叉树结把待排序的数据元素集合构成一个完全二叉树结构，则每次选择出一个最大（或最小）的数据元素只需比较完构，则每次选择出一个最大（或最小）的数据元素只需比较完全二叉树的高度次，即全二叉树的高度次，即lo

14、g2n次，则排序算法的时间复杂度就是次，则排序算法的时间复杂度就是O(nlog2n)。一、堆的定义一、堆的定义堆分为最大堆和最小堆两种。定义如下：堆分为最大堆和最小堆两种。定义如下：设数组设数组a中存放了中存放了n个数据元素，数组下标从个数据元素，数组下标从0开始，如果当数开始，如果当数组下标组下标2i+1n时有时有:ai.keya2i+1.key(ai.keya2i+1.key)；如 果 当 数 组 下 标如 果 当 数 组 下 标 2 i+2 n 时 有时 有:a i .k e y a 2 i+2 .k e y(ai.keya2i+2.key)，则这样的数据结构称为最大堆则这样的数据结构称

15、为最大堆(最小堆最小堆)。171050325769408888764050109325(a)(b)(a)完全二叉树完全二叉树 (b)最大堆最大堆 性质：性质：（1 1）最大堆的根结点是堆中值最大的数据元素，最小堆的根结点）最大堆的根结点是堆中值最大的数据元素，最小堆的根结点是堆中值最小的数据元素，我们称堆的根结点元素为堆顶元素。是堆中值最小的数据元素，我们称堆的根结点元素为堆顶元素。（2 2）对于最大堆，从根结点到每个叶结点的路径上，数据元素组）对于最大堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是递减有序的；对于最小堆，从根结点到每个叶结点的路成的序列都是递减有序的；对于最小堆，从

16、根结点到每个叶结点的路径上，数据元素组成的序列都是递增有序的。径上，数据元素组成的序列都是递增有序的。18二、二、创建堆创建堆 创建最大堆过程中要多次调用函数：调整完全二叉树中某创建最大堆过程中要多次调用函数：调整完全二叉树中某个非叶结点个非叶结点aiai（i=(n-1)/2i=(n-1)/2）使之满足最大堆定义，前提条使之满足最大堆定义，前提条件是该结点的左孩子结点件是该结点的左孩子结点a2i+1a2i+1和右孩子结点和右孩子结点a2i+2a2i+2都已是都已是最大堆。最大堆。函数设计如下：函数设计如下：19void CreatHeap(DataType a,int n,int h)int

17、i,j,flag;DataType temp;i=h;/i为要建堆的二叉树根结点下标为要建堆的二叉树根结点下标 j=2*i+1;/j为为i的左孩子结点的下标的左孩子结点的下标 temp=ai;flag=0;while(j n&flag!=1)/寻找左右孩子结点中的较大者寻找左右孩子结点中的较大者,j为其下标为其下标 if(j n-1&aj.key aj.key)/ai.keyaj.key flag=1;/标记结束筛选条件标记结束筛选条件 else/否则把否则把aj上移上移 ai=aj;i=j;j=2*i+1;ai=temp;/把最初的把最初的ai赋予最后的赋予最后的aj20初始化创建最大堆算法

18、如下：初始化创建最大堆算法如下：void InitCreatHeap(DataType a,int n)int i;for(i=(n-1)/2;i=0;i-)CreatHeap(a,n,i);堆排序的基本思想是：循环执行如下过程直到数组为空：（堆排序的基本思想是：循环执行如下过程直到数组为空：（1）把堆）把堆顶顶a0元素（为最大元素）和当前最大堆的最后一个元素交换；（元素（为最大元素）和当前最大堆的最后一个元素交换；（2）最大）最大堆元素个数减堆元素个数减1；（；（3）由于第（）由于第（1）步后根结点不再满足最大堆的定义，）步后根结点不再满足最大堆的定义，所以调整根结点使之满足最大堆的定义。所

19、以调整根结点使之满足最大堆的定义。三、堆排序算法三、堆排序算法211050325769408810503257694088数组数组1050328876940510503288769405数组数组1050408876932510504088769325数组数组1088405076932510884050769325数组数组8876405010932588764050109325数组数组(a)初始状态初始状态(b)调整结点调整结点5 5后后 (c)调整结点调整结点32后后(d)调整结点调整结点50后后(e)调整结点调整结点1010后后 完全二叉树调整为最大堆的过程完全二叉树调整为最大堆的过程 22

20、堆排序算法如下：堆排序算法如下：void HeapSort(DataType a,int n)int i;DataType temp;InitCreatHeap(a,n);/初始化创建最大堆初始化创建最大堆 for(i=n-1;i 0;i-)/当前最大堆个数每次递减当前最大堆个数每次递减1 /把堆顶把堆顶a0元素和当前最大堆的最后一个元素交换元素和当前最大堆的最后一个元素交换 temp=a0;a0=ai;ai=temp;CreatHeap(a,i,0);/调整根结点满足最大堆调整根结点满足最大堆 238876405010932588764050109325(a)初始最大堆初始最大堆 76504

21、051093276504051093288503240510950324051097688(b)交换顶点交换顶点8888后后(c)交换顶点交换顶点7676后后 4032951040329510507688(d)交换顶点交换顶点5050后后 3210953210954050768832109105932405076889595103240507688(g)交换顶点交换顶点1010后后 559103240507688(h)交换顶点交换顶点9 9后后(f)交换顶点交换顶点3232后后(e)交换顶点交换顶点4040后后 堆排序算法的排序过程堆排序算法的排序过程 24算法分析：算法分析：时间效率：时间效

22、率：O(nlog2n)。因为整个排序过程中需要调因为整个排序过程中需要调用用n-1次堆顶点的调整，而每次堆排序算法本身次堆顶点的调整，而每次堆排序算法本身耗时为耗时为log2n；空间效率：空间效率：O(1)。仅在第二个仅在第二个for循环中交换记录时循环中交换记录时用到一个临时变量用到一个临时变量temp。稳定性：稳定性：不稳定。不稳定。优点：优点：对小文件效果不明显，但对大文件有效。对小文件效果不明显，但对大文件有效。2510.4 10.4 交换排序交换排序 交换排序的基本思想是：利用交换数据元素的位交换排序的基本思想是：利用交换数据元素的位置进行排序的方法。置进行排序的方法。交换排序的主要

23、算法有：交换排序的主要算法有：1)1)冒泡排序冒泡排序2)2)快速排序快速排序261.1.冒泡排序冒泡排序 基本思想：基本思想：每趟不断将数据元素两两比较，并按每趟不断将数据元素两两比较，并按“前小后前小后大大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，每趟结束时，不仅能挤出一个最大值到最后面位置，还能还能同时部分理顺其他元素同时部分理顺其他元素；一旦下趟没有交换发；一旦下趟没有交换发生，还可以生，还可以提前结束排序提前结束排序。27算法核心语句如下：算法核心语句如下：for(i=1;i n&flag=1;i+)flag=0;

24、for(j=0;j n -i;j+)flag=1;temp=aj;aj=aj+1aj+1;aj+1=temp;28初始关键字序列初始关键字序列:第一次排序结果第一次排序结果:第二次排序结果第二次排序结果:第三次排序结果第三次排序结果:第四次排序结果第四次排序结果:第五次排序结果第五次排序结果:最后结果序列最后结果序列:385192649971665192638491669751926381496697519261384966975191263849669751192638496697151926384966971519263849669715192638496697第六次排序结果第六次排序结果

25、:第七次排序结果第七次排序结果:冒泡排序算法的排序过程冒泡排序算法的排序过程 29算法分析：算法分析：最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动数据元素。次关键码比较，不移动数据元素。最坏情形：最坏情形：初始排列逆序，算法要执行初始排列逆序，算法要执行n-1趟起泡，第趟起泡，第i趟趟(1 i n)做了做了n-i 次关键码比较，执行了次关键码比较，执行了n-i 次数据元素交次数据元素交换。此时的比较总次数和记录移动次数为：换。此时的比较总次数和记录移动次数为：11111233121nininninnnin)()()(

26、)(移移动动次次数数比比较较次次数数302.2.快速排序快速排序 基本思想：基本思想：从待排序列中任取一个元素从待排序列中任取一个元素(例如取第一个例如取第一个)作为作为中心，所有比它小的元素一律前放，所有比它大的元素一律后中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。序列了。优点：优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，因为每趟可以确定不止一个元

27、素的位置，而且呈指数增加，所以特别快。所以特别快。因此：因此：时间效率：时间效率：O O（n n2 2)考虑最坏情况考虑最坏情况空间效率：空间效率：O O（1 1）只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳 定定 性：性：稳定的稳定的31算法核心语句如下：算法核心语句如下：while(i j&temp.key=aj.key)j-;/在数组的右端扫描在数组的右端扫描if(i j)ai=aj;i+;while(i j&ai.key temp.key)i+;/在数组的左端扫描在数组的左端扫描if(i j)aj=ai;j-;32605548371090843636554837109084

28、9090365548371090843655483710908436554837109084365548371090843655483710908436554837108436554837106084iiiiiiiijjjjjjjjij初始关键字序列初始关键字序列:(1)(2)(3)(4)(5)(6)(7)(8)快速排序算法一次快速排序过程快速排序算法一次快速排序过程 33图中标有下划横线的数据元素为本次快速排序选取的标准图中标有下划横线的数据元素为本次快速排序选取的标准元素。元素。快速排序算法各次快速排序过程快速排序算法各次快速排序过程 初始关键字序列初始关键字序列:(1)(2)605548

29、37109084363655483710609010 3637556084(3)10 3648608490最后结果最后结果10363748556084903748558490 34时间效率：时间效率：O(nlog2n)因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加空间效率：空间效率：O(log2n)因为递归要用堆栈因为递归要用堆栈稳稳 定定 性：性：不不 稳稳 定定 因为有跳跃式交换。因为有跳跃式交换。算法分析：算法分析：3510.5 10.5 归并排序归并排序 归并排序主要是二路归并排序归并排序主要是二路归并排序,基本思想是：基本思想是：可以把一个长可以把一个长度为度为n 的无序序

30、列看成是的无序序列看成是 n 个长度为个长度为 1 的有序子序列的有序子序列，首先做首先做两两归并，得到两两归并，得到 n/2 个长度为个长度为 2 的有序子序列的有序子序列；再做两两；再做两两归并，归并，如此重复，直到最后得到一个长度为，如此重复，直到最后得到一个长度为 n 的有序序列。的有序序列。一次二路归并排序算法如下：一次二路归并排序算法如下：36void Merge(DataType a,int n,DataType swap,int k)/k为子数组长度，一次二路归并排序后的子序列存于数组为子数组长度，一次二路归并排序后的子序列存于数组swap中中 int m=0,u1,l2,i,

31、j,u2;int l1=0;/第一个有序子数组下界为第一个有序子数组下界为0 while(l1+k=n-1)l2=l1+k;/第二个有序子数组下界第二个有序子数组下界 u1=l2-1;/第一个有序子数组上界第一个有序子数组上界 u2=(l2+k-1=n-1)?l2+k-1:n-1;/第二个子数组上界第二个子数组上界 /两个有序子数组合并两个有序子数组合并 for(i=l1,j=l2;i=u1&j=u2;m+)if(ai.key=aj.key)swapm=ai;i+;else swapm=aj;j+;37 /子数组子数组2已完，将子数组已完，将子数组1中剩余的元素存放到中剩余的元素存放到swap

32、while(i=u1)swapm=ai;m+;i+;/子数组子数组1已完，将子数组已完，将子数组2中剩余的元素存放到中剩余的元素存放到swap while(j=u2)swapm=aj;m+;j+;l1=u2+1;/将原始数组中只够一组的数据元素顺序存放到数组将原始数组中只够一组的数据元素顺序存放到数组swap for(i=l1;i n;i+,m+)swapm=ai;38因为在递归的归并排序算法中，递归调用函数因为在递归的归并排序算法中，递归调用函数Merge()约为约为 log2n 次，而每次归并要执行比较约为次，而每次归并要执行比较约为n次，所以算法总的次，所以算法总的时间复杂度为时间复杂度

33、为O(nlog2n)。因为需要一个与原始序列同样大小的辅助序列。这是此算因为需要一个与原始序列同样大小的辅助序列。这是此算法的缺点。法的缺点。3910.6 10.6 基数排序基数排序 基数排序也称作基数排序也称作桶排序桶排序，是一种当关键字为整数类型时非，是一种当关键字为整数类型时非常高效的排序方法常高效的排序方法。其基本思想是：其基本思想是：设待排序的数据元素关键字是设待排序的数据元素关键字是m m位位d d进制整数（不足进制整数（不足m m位的关位的关键字在高位补键字在高位补0 0），设置），设置d d个桶，令其编号分别为个桶，令其编号分别为0,1,2,0,1,2,d-1d-1。首先首先按

34、关键字最低位的数值依次把各数据元素放到相应的桶中，按关键字最低位的数值依次把各数据元素放到相应的桶中，然后然后按照桶号从小到大和进入桶中数据元素的先后次序收集分按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素，这样就形成了数据元素集合的一个新配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为的排列，我们称这样的一次排序过程为一次基数排序；一次基数排序；40 再对再对一次基数排序得到的数据元素序列按关键字次低位一次基数排序得到的数据元素序列按关键字次低位的数值依次把各数据元素放到相应的桶中，的数值依次把各数据元素放到相应的桶中，然后然后

35、按照桶号按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样的过程中的数据元素；这样的过程重复进行，当完成了第重复进行，当完成了第m次基数次基数排序后排序后，就得到了排好序的数据元素序列。，就得到了排好序的数据元素序列。数据元素的关键字序列为数据元素的关键字序列为710,342,045,686,006,841,429,134,068,264排序过程如下排序过程如下418411342231342644045568600667068871004299710841342134264045686006068429收集后的新序列收

36、集后的新序列:放置放置7101429213438413420454526406867686800609006710429134841342045264068686收集后的新序列收集后的新序列:放置放置1341264234234294568667107841800604506809006045068134264342429686710841收集后的新序列收集后的新序列:放置放置(a)初始状态初始状态(b)第一次基数排序第一次基数排序(c)c)第二次基数排序第二次基数排序 42 基数排序算法进出桶中的数据元素序列满足先进先出的原基数排序算法进出桶中的数据元素序列满足先进先出的原则，则，桶实际就是队

37、列。桶实际就是队列。实现基数排序算法时，有实现基数排序算法时，有基于顺序队列基于顺序队列和和基于链式队列基于链式队列两种不同的实现方法。两种不同的实现方法。在基于链式队列的基数排序算法中，可以把在基于链式队列的基数排序算法中，可以把d个队列设计成一个队列设计成一个队列数组（设队列数组名为个队列数组（设队列数组名为tub），），队列数组的每个元素中队列数组的每个元素中包括两个域：包括两个域：front域和域和rear域。域。front域用于指示队头，域用于指示队头，rear域用于指示队尾。当第域用于指示队尾。当第i（i=0,1,2,d-1）个队列中有数据元素个队列中有数据元素要放入时，就在队列数

38、组的相应元素要放入时，就在队列数组的相应元素tubi中的队尾位置插入中的队尾位置插入一个结点。基于链式队列基数排序算法的存储结构示意图如下一个结点。基于链式队列基数排序算法的存储结构示意图如下图所示。图所示。43.rearfrontdatanext 012d-1.tub 一个十进制关键字一个十进制关键字K的第的第i位数值位数值Ki的计算公式为：的计算公式为：),.,2,1()int(10)int(10101miKiiKKi44基于链式队列的基数排序算法基于链式队列的基数排序算法:#include LQueue.h void RadixSort(DataType a,int n,int m,in

39、t d)int i,j,k,power=1;LQueue*tub;/把把d个队列定义为动态数组个队列定义为动态数组tub=(LQueue*)malloc(sizeof(LQueue)*d);for(i=0;i d;i+)QueueInitiate(&tubi);/d个队列分别初始化个队列分别初始化45for(i=0;i m;i+)/进行进行m次放和收次放和收 if(i=0)power=1;else power=power*d;for(j=0;j n;j+)/放放 k=aj.key/power-(aj.key/(power*d)*d;QueueAppend(&tubk,aj);/把把aj放入第放

40、入第k个队列个队列 k=0;for(j=0;j d;j+)/回收回收while(QueueNotEmpty(tubj)!=0)QueueDelete(&tubj,&ak);/从各队列中回收从各队列中回收 k+;46基数排序算法分析基数排序算法分析特点：特点：不用比较和移动，改用分配和收集，时间效率高！不用比较和移动，改用分配和收集，时间效率高！时间复杂度为：时间复杂度为：O(mn)。空间复杂度：空间复杂度：O(n).稳定性：稳定性：稳定。稳定。(一直前后有序一直前后有序)。47排序方法排序方法最好时最好时 间间平均时间平均时间最坏时间最坏时间辅助空间辅助空间稳定性稳定性直接插入排序直接插入排序

41、O(n)O(n2)O(n2)O(1)稳定稳定希尔排序希尔排序 O(n1.3)O(1)不稳定不稳定直接选择排序直接选择排序O(n2)O(n2)O(n2)O(1)不稳定不稳定堆排序堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定不稳定冒泡排序冒泡排序O(n)O(n2)O(n2)O(1)稳定稳定快速排序快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)不稳定不稳定归并排序归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定稳定基数排序（基基数排序（基于链式队列）于链式队列）O(mn)O(mn)O(mn)O(n)稳定稳定基数排序（基基数排序（基于顺序队列）于顺序队列）O(mn)O(mn)O(mn)O(mn)稳定稳定10.7 10.7 性能比较性能比较 481)习题习题10-1，10-2，10-4(1)，10-20 2)习题习题10-4(3)，10-8，10-9，10-10，10-123)习题习题10-4(2,4,5)，10-13，10-17，10-5，10-6作业作业