排序4-归并与基数排序

《排序4-归并与基数排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章排序数据结构讲义-归并与基数排序SunLand@nuc.edu.cn10.4归并排序归并——将两个或两个以上的有序表组合成一个新的有序表，叫~2-路归并排序设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。两两合并，得到n/2个长度为2或1的有序子序列。再两两合并，……如此重复，直至得到一个长度为n的有序序列为止。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。012344913659776780AB01234567Cijk例子：合并两个有序表3012344913659776780AB01234567Cijk740123449

2、13659776780AB01234567Cijk75012344913659776780AB01234567Cijk7136012344913659776780AB01234567Cijk713497012344913659776780AB01234567Cijk713498012344913659776780AB01234567Cijk71349659012344913659776780AB01234567Cijk713496510012344913659776780AB01234567Cijk71349657611012344913659776780AB01234567Cijk71349

3、657612012344913659776780AB01234567Cijk7134965768013012344913659776780AB01234567Cijk7134965768014012344913659776780AB01234567Cijk71349657680至此B表的元素都已移入C表，只需将A表的剩余部分移入C表即可。15012344913659776780AB01234567Cijk71349657680至此B表的元素都已移入C表，只需将A表的剩余部分移入C表即可。9716初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][659

4、7][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]例子：归并排序算法评价时间复杂度：T(n)=O(nlogn)空间复杂度：S(n)=O(n)它是一个稳定的排序方法。10.5基数排序多关键字排序例对52张扑克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A两个关键字：花色（<<<）面值（2<3<……

5、键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列。最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列。多关键字排序方法MSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序。链式基数排序基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法。链

6、式基数排序：用链表作存储结构的基数排序。例初始状态：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：基数排序的演示505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]

7、e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f