《数据结构与算法》第十章内部排序.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * (1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4) (1,1),(1,3),(2,4),(2,3),(3,2),(3,4),(4,4),(4,3) (1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4) ?最低位优先法LSD： 根据最次关键字Kd-1起对记录排序 再根据Kd-2对记录排序 。。。。。。 根据K0对记录排序后， 整个序列有序 (1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4) (1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(4,4),(3,4) (1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4) 二、链式基数排序 用分配和收集两种操作对单关键字进行排序 某些单关键字可以看成是若干个关键字复合而成,如多位数可以看成是由多个数字复合而成的。 分配： 按关键字把不同的记录送到不同的队列中 收集： 按某种顺序把不同队列中的记录集中起来 614 921 485 637 738 101 215 530 790 306 第一趟分配（按最低位） 第一趟收集 530 790 921 101 614 485 215 306 637 738 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 614 738 921 485 637 101 215 530 790 306 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 614 921 485 637 738 101 215 530 790 306 第二趟分配（按次低位） 第二趟收集 530 790 921 101 614 485 215 306 637 738 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 614 738 921 485 637 101 215 530 790 306 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 614 921 485 637 738 101 215 530 790 306 第三趟分配（按最高位） 第三趟收集 530 790 921 101 614 485 215 306 637 738 614 738 921 485 637 101 215 530 790 306 e[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] 10．7各种排序方法比较 排序方法 平均时间 最坏情况 辅助存储 直接插入排序 O(n2) O(n2) O(1) 直接选择排序 冒泡排序 快速排序 O(nlogn) O(n2) O(logn) 堆排序 O(nlogn) O(nlogn) O(1) 归并排序 O(nlogn) O(nlogn) O(n) 基数排序 O(d(n+rd)) O(d(n+rd)) O(rd) 排序方法 稳定性 方法类别 直接插入排序 稳定 插入 直接选择排序 不稳定 选择 冒泡排序 稳定 交换 快速排序 不稳定 交换 堆排序 不稳定 选择 归并排序 稳定 合并 基数排序 稳定 比较和移动 希尔排序 不稳定 插入 规模 10 100 10K 100K 1M 10K正序 10K逆序 直接 插入 00.00002 0.1752 17.917 _____ 0.00011 0.35094 选择 排序 0.0000011 0.000041 0.2778 36.5 _____ 0.27781 0.29109 冒泡 排序 0.0000016 0.000156 1.5617 207.69 _____ 0.00006 2.4484 Shell排序(2) 00.0000