第1章排序-归并与基数排序ppt课件

1、数据构造讲义 - 归并与基数排序SunLl归并将两个或两个以上的有序表组合成一个新的有序表，叫l2-路归并排序l设初始序列含有n个记录，那么可看成n个有序的子序列，每个子序列长度为1。l两两合并，得到n/2个长度为2或1的有序子序列。l再两两合并，如此反复，直至得到一个长度为n的有序序列为止。顺序比较两者的相应元素，小者移入另一表中，反复顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk0 1 2 3 4491365

2、9776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7130 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2

3、 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680至此至此 B

4、表的元素表的元素都已移入都已移入 C 表，表，只需将只需将 A 表的剩表的剩余部分移入余部分移入 C 表表即可。即可。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680至此至此 B 表的元素表的元素都已移入都已移入 C 表，表，只需将只需将 A 表的剩表的剩余部分移入余部分移入 C 表表即可。即可。97初始关键字： 49 38 65 97 76 13 27一趟归并后： 38 49 65 97 13 76 27二趟归并后： 38 49 65 97 13 27 76三趟归并后： 13 27 38 49 65 76 97l时间复杂度：lT(

5、n)=O(nlogn)l空间复杂度：lS(n)=O(n)l它是一个稳定的排序方法。l多关键字排序例 对52张扑克牌按以下次序排序：23A23A23A23A两个关键字：花样 面值23A并且“花样位置高于“面值l最高位优先法最高位优先法MSD)：先对最高位关键字：先对最高位关键字k1如花样排序，将序列分成假设干子序列，如花样排序，将序列分成假设干子序列，每个子序列有一样的每个子序列有一样的k1值；然后让每个子序列值；然后让每个子序列对次关键字对次关键字k2如面值排序，又分成假设干如面值排序，又分成假设干更小的子序列；依次反复，直至就每个子序列更小的子序列；依次反复，直至就每个子序列对最低位关键字对

6、最低位关键字kd排序；最后将一切子序列依排序；最后将一切子序列依次衔接在一同成为一个有序序列。次衔接在一同成为一个有序序列。l最低位优先法最低位优先法(LSD)：从最低位关键字：从最低位关键字kd起进起进展排序，然后再对高一位的关键字排序，展排序，然后再对高一位的关键字排序，依次反复，直至对最高位关键字依次反复，直至对最高位关键字k1排序后，便排序后，便成为一个有序序列。成为一个有序序列。l按按MSD排序，必需将序列逐层分割排序，必需将序列逐层分割成假设干子序列，然后对各子序列成假设干子序列，然后对各子序列分别排序。分别排序。l按按LSD排序，不用分成子序列，对排序，不用分成子序列，对每个关键

7、字都是整个序列参与排序；每个关键字都是整个序列参与排序；并且可不经过关键字比较，而经过并且可不经过关键字比较，而经过假设干次分配与搜集实现排序。假设干次分配与搜集实现排序。l基数排序：借助“分配和“搜集对单逻辑关键字进展排序的一种方法。l链式基数排序：用链表作存储构造的基数排序。例初始形状：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟搜集：505008109930063

8、269278083184589二趟搜集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟搜集：008063083109184269278505589930三趟搜集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟搜集：l设置10个队列，fi和ei分别为第i个队列的头指针和

9、尾指针。l第一趟分配对最低位关键字个位进展，改动记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位一样。l第一趟搜集是改动一切非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表。l反复上述两步，进展第二趟、第三趟分配和搜集，分别对十位、百位进展，最后得到一个有序序列。l时间复杂度：l分配：T(n)=O(n)l搜集：T(n)=O(rd)、lT(n)=O(d(n+rd)l其中：n记录数， d关键字数， rd关键字取值范围(如十进制为10) 。l空间复杂度：lS(n)=2rd个队列指针+n个指针域空间。 平均时间平均时间 最差最差 最正

10、确最正确 辅助空间辅助空间 稳定稳定性性直接插入直接插入 O(n2) O(n2) O(n) O(1) O(n2) O(n2) O(n) O(1) 稳定稳定起泡排序起泡排序 O(n2) O(n2) O(n) O(1) O(n2) O(n2) O(n) O(1) 稳定稳定直接选择直接选择 O(n2) O(n2) O(n2) O(1) O(n2) O(n2) O(n2) O(1) 不稳定不稳定希尔排序希尔排序 O(n1.5) O(1) O(n1.5) O(1) 不稳定不稳定快速排序快速排序 O(nlog2n) O(n2) O(nlog2n) O(n2) 同平均同平均 O(log2n) O(log2n) 不稳定不稳定堆排序堆排序 O(nlog2n) O(nlog2n) 同平均同平均 同平均同平均 O(1) O(1) 不稳定不稳定归并排序归并排序 O(nl