《数据结构与算法》第九章排序.优秀PPT.ppt

《《数据结构与算法》第九章排序.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法》第九章排序.优秀PPT.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter 9Sorting1、插入排序（干脆插入排序、希尔排序）、插入排序（干脆插入排序、希尔排序）2、交换排序（起泡排序、快速排序）、交换排序（起泡排序、快速排序）3、选择排序（简洁选择排序、堆排序）、选择排序（简洁选择排序、堆排序）4、归并排序、基数排序、归并排序、基数排序排序：将数据元素的一个随意序列，重新排列成一排序：将数据元素的一个随意序列，重新排列成一 个按关键字有序的序列。个按关键字有序的序列。9.1 概述概述 假设含假设含 n 个记录的序列为个记录的序列为 R1,R2,Rn，其相，其相应的关键字序列为应的关键字序列为 K1,K2,Kn 这些关键字相互之间可以进行比较，即在

2、它们之间这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系存在着这样一个关系：Kp1Kp2Kpn 按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1,Rp2,Rpn 的操作称作的操作称作排序排序排序排序。例：将关键字序列：例：将关键字序列：52 49 80 36 14 58 61 23 调整为：调整为：14 23 36 49 52 58 61 80 设设 Ki=Kj(1in,1jn,ij)，且在排序前的，且在排序前的序列中序列中 Ri 领先于领先于 Rj（即（即 i j）。若在排序后的序列）。若在排序后的序列中中 Ri 仍领先于仍领先于 Rj，则称所用

3、的，则称所用的排序方法是稳定的排序方法是稳定的；反之，则称所用的反之，则称所用的排序方法是不稳定的排序方法是不稳定的。设排序前的关键字序列为：设排序前的关键字序列为：52,49,80,36,14,58,3636,23 若排序后的关键字序列为：若排序后的关键字序列为：14,23,36,3636,49,52,58,80，则则排序方法是稳定的排序方法是稳定的排序方法是稳定的排序方法是稳定的。若排序后的关键字序列为：若排序后的关键字序列为：14,23,3636,36,49,52,58,80，则则排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的。内部排序和外部排序内部排序和外部排

4、序 若整个排序过程不须要访问外存便能完成，则称若整个排序过程不须要访问外存便能完成，则称此类排序问题为内部排序；此类排序问题为内部排序；反之，若参与排序的记录数量很大，整个序列的反之，若参与排序的记录数量很大，整个序列的排序过程不行能在内存中完成，则称此类排序问题为排序过程不行能在内存中完成，则称此类排序问题为外部排序。外部排序。内部排序的方法内部排序的方法 逐步扩大记录的有序序列的过程逐步扩大记录的有序序列的过程 有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区经过一趟排序经过一趟排序 9.2 插入排序插入排序 有序序列有序序列 R1.i-1

5、Ri无序序列无序序列 Ri.n有序序列有序序列 R1.i无序序列无序序列 Ri+1.n实现实现“一趟插入排序一趟插入排序”可分可分三步三步进行：进行：3将将 Ri 插入（复制）到插入（复制）到 R j+1 的位置上。的位置上。2将将 R j+1.i-1 中的全部记录均后移一个位置；中的全部记录均后移一个位置；1在在 R1.i-1 中查找中查找 Ri 的插入位置，的插入位置，R1.j.key Ri.key R j+1.i-1.key；一趟干脆插入排序的基本思路一趟干脆插入排序的基本思路9.2.1 干脆插入排序干脆插入排序 初始状态初始状态4938659776132749 R0 R1 R2 R3

6、R4 R5 R6 R7i=1 i=2 3849659776132749i=3 3849659776132749i=4 3849657697132749i=5 3849657697132749i=6 3849657697132749i=7 384965769713274949386597761327494938 排序过程：先将序列中第排序过程：先将序列中第 1 个记录看成是一个有序子序列，个记录看成是一个有序子序列，然后从第然后从第 2 个记录起先，逐个进行插入，直至整个序列有序。个记录起先，逐个进行插入，直至整个序列有序。插入排序举例：插入排序举例：21 25 49 25*16 08 21 2

7、5 49 25*16 08 21 25 49 25*16 08 21 25 25*49 16 08 16 21 25 25*49 08 08 16 21 25 25*49 templatevoid Insert(ElemTypeelem,int n)/在数组在数组elem中作插入排序中作插入排序 for(int i=1;i0&elemj.key elemj-1.key;j-)/将比将比elemj大的元素交换到后面大的元素交换到后面 Swap (elemj,elemj-1);当当elemj比它前面元素的关键字小时，就向前移动，比它前面元素的关键字小时，就向前移动，直到遇到一个关键字比它大或相等的

8、为止直到遇到一个关键字比它大或相等的为止T(n)=O(n)算法评价算法评价 时间困难度：时间困难度：比较次数：比较次数：最好的状况：待排序记录按关键字从小到大排列（正序）最好的状况：待排序记录按关键字从小到大排列（正序）比较次数：比较次数：最坏的状况：待排序记录按关键字从大到小排列（逆序）最坏的状况：待排序记录按关键字从大到小排列（逆序）一般状况：待排序记录是随机的，取平均值。一般状况：待排序记录是随机的，取平均值。干脆插入排序是稳定排序干脆插入排序是稳定排序 9.2.2 希尔排序（缩小增量排序）希尔排序（缩小增量排序）思路：思路：对待排序列先对待排序列先“宏观宏观”调整，再调整，再“微观微观

9、”调整。调整。排序过程：先取一个正整数排序过程：先取一个正整数 d1 n，把全部相隔，把全部相隔 d1 的记录放在一组内，组内进行干脆插入排序；然后取的记录放在一组内，组内进行干脆插入排序；然后取 d2 0;i-)for(int j=0;jelemj+1.key)elem j elem j+1 9.4 交换排序交换排序 1、冒泡排序、冒泡排序 v 排序过程排序过程 初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 第第 一一 趟趟 排排 序序 38 49 76 97 13 97 27 97 49 9797 38 49 65 76 13 27 49 979738 49

10、 65 13 27 49 76 76 第第 二二 趟趟 排排 序序 38 49 13 27 49 65 65 第第 三三 趟趟 排排 序序 38 13 27 49 4949 第第 四四 趟趟 排排 序序 13 27 3849 49 第第 五五 趟趟 排排 序序 13 13 2727 38 38 第第 六六 趟趟 排排 序序 时间困难度时间困难度时间困难度时间困难度T(n)=O(n2)T(n)=O(n2)13 13 27 27 第第 七七 趟趟 排排 序序 冒泡排序的时间性能分析冒泡排序的时间性能分析正序正序比较次数：比较次数：时间困难度为时间困难度为O(n)反序反序比较次数：比较次数：时间困难

11、度为时间困难度为O(n2)2 2)1 1(1 1-=n nn n(n n-i i)n n-1-1i i54321123452 2)1 1(1 1-=n nn n(n n-i i)n n-1-1i i一般取第一个记录一般取第一个记录 基本思想：基本思想：任选任选任选任选一个记录，以它的关键字作为一个记录，以它的关键字作为“枢枢枢枢轴轴轴轴”，凡关键字小于枢轴的记录均移至枢轴之前，凡，凡关键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录均移至枢轴之后。关键字大于枢轴的记录均移至枢轴之后。2、一趟快速排序（一次划分）、一趟快速排序（一次划分）lowhigh设设 Rs=52 为枢轴。为枢轴。例

12、：例：52 52 52 49 80 36 14 58 61 97 23 75 high23 low low80highhighhighhigh14lowlow5252课本课本270页页 3、快速排序、快速排序 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，之后分别对，之后分别对分割所得两个子序列分割所得两个子序列“递归递归”进行一趟快速排序。进行一趟快速排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴 一次划分一次划分 分别进行一趟快速排序分别进行一趟快速排序 有有 序序 的的 记记 录录 序序 列列 1

13、313656527275050383849495555ji13133838656527275050494955551313656527275050494938385555jjiiijijjj如何实现一次划分？如何实现一次划分？解决方法：解决方法：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。13132727383865655050494955551313272750503838494955556565ijij如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？void QSort(elem,int low,int high)/对依次表对

14、依次表 L 中的子序列中的子序列 L.rlow.high 进行快速排序进行快速排序 if(low high)/长度大于长度大于1 /QSortint pivotloc=Partition(elem,low,high);int pivotloc=Partition(elem,low,high);/对对对对 L.rlow.high L.rlow.high 进行一次划分进行一次划分进行一次划分进行一次划分 QSort(elem,low,pivotloc-1);/对低子序列递归排序，对低子序列递归排序，pivotloc 是枢轴位置是枢轴位置 QSort(elem,pivotloc+1,high);/对

15、高子序列递归排序对高子序列递归排序 第一次调用函数第一次调用函数 Qsort 时，待排序记录序列的上时，待排序记录序列的上下界分别为下界分别为 0 和和 n-1。void QuickSort(elem,int n)/对依次表进行快速排序对依次表进行快速排序 QSort(elem,0,n-1);/QuickSort 快速排序的时间分析快速排序的时间分析 若待排序列中记录的关键字是随机分布的，则若待排序列中记录的关键字是随机分布的，则 k 取取 1 至至 n 中任一值的可能性相同。中任一值的可能性相同。由此可得快速排序所需时间的平均值为：由此可得快速排序所需时间的平均值为：结论：快速排序的时间困难

16、度为结论：快速排序的时间困难度为结论：快速排序的时间困难度为结论：快速排序的时间困难度为 O(n log n)O(n log n)。一次划分所需时间和表长成正比一次划分所需时间和表长成正比 到目前为止快速排序是到目前为止快速排序是平均速度最大平均速度最大平均速度最大平均速度最大的一种排序方法。的一种排序方法。(1)21 25 49 25*16 08 练习练习快速排序是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。请举例说明。请举例说明。9.5 选择排序选择排序 9.5.1 简洁选择排序简洁选择排序 首先通过首先通过 n 1 n 1 次关键字比较，从次关键字比较，从 n n 个记录中找个

17、记录中找出关键字最小的记录，将它与第一个记录交换。出关键字最小的记录，将它与第一个记录交换。再通过再通过 n 2 n 2 次比较，从剩余的次比较，从剩余的 n 1 n 1 个记录中个记录中找出关键字次小的记录，将它与其次个记录交换。找出关键字次小的记录，将它与其次个记录交换。重复上述操作，共进行重复上述操作，共进行 n 1 n 1 趟排序后，排序结趟排序后，排序结束。束。例例 一趟一趟:13 38 65 97 76 49 27 i=0 二趟二趟:13 27 65 97 76 49 38 三趟三趟:13 27 38 97 76 49 65 四趟四趟:13 27 38 49 76 97 65 五趟

18、五趟:13 27 38 49 65 97 76 六趟六趟:13 27 38 49 65 76 97 i=4 i=1 i=2 i=3 n-1 n-2 n-6 初始初始：49 38 65 97 76 13 27 jjjjjjk13 49 kki=5 排序结束排序结束比较次数比较次数 for(j=i+1;j n;j+)if(elemj.key elemk.key)k=j;elemielemk;/与第与第 i 个记录交换个记录交换void SelectSort(ElemType elem,int n)/SelectSort 比较次数：比较次数：时间困难度：时间困难度：时间困难度：时间困难度：O(n2)

19、O(n2)for(i=0;i n-1;+i)int k=i;(1)21 25 49 25*16 08 练习练习 简洁选择排序是一种不稳定的排简洁选择排序是一种不稳定的排序方法。序方法。请举例说明。请举例说明。9.5.2 堆排序堆排序 堆排序是选择排序的改进（堆排序是选择排序的改进（1964提出）。提出）。在排序过程中，将在排序过程中，将r1到到rn看成是一个看成是一个完全二叉树依次存储结构，利用完全二叉完全二叉树依次存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系树中双亲结点和孩子结点之间的内在关系来选择最小或最大元素。来选择最小或最大元素。堆的定义：堆的定义：n个数据序列个数据序列

20、K1,k2,.,Kn称为堆，当称为堆，当且仅当该序列满足特性：且仅当该序列满足特性：此种状况称为小顶堆。或者，均大于也可以。此种状况称为小顶堆。或者，均大于也可以。此种状况状况称为大顶堆。此种状况状况称为大顶堆。从堆的定义可以看出，堆实质上是满足如下从堆的定义可以看出，堆实质上是满足如下性质的二叉树：树中任一非叶子结点的值均小于性质的二叉树：树中任一非叶子结点的值均小于等于它的孩子结点的值。或者，树中任一非叶子等于它的孩子结点的值。或者，树中任一非叶子结点的值均大于等于它的孩子结点的值。结点的值均大于等于它的孩子结点的值。)2/1(ni 例例(96,83,27,38,11,09)(13,38,

21、27,49,76,65,49,97)9627091138831327384965764997全部非终端结点的值均不大全部非终端结点的值均不大(小小)于其左右孩子结点的值。于其左右孩子结点的值。堆顶元素必为序列中堆顶元素必为序列中 n 个元素的最小值或最大值。个元素的最小值或最大值。小顶堆小顶堆 大顶堆大顶堆 堆排序：堆排序：堆排序需解决的两个问题：堆排序需解决的两个问题：1、如何由一个无序序列建成一个堆？、如何由一个无序序列建成一个堆？2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？将无序序列建成一个堆，得到关键字最小（大）的将无序序列

22、建成一个堆，得到关键字最小（大）的将无序序列建成一个堆，得到关键字最小（大）的将无序序列建成一个堆，得到关键字最小（大）的 记录；输出堆顶的最小（大）值后，将剩余的记录；输出堆顶的最小（大）值后，将剩余的记录；输出堆顶的最小（大）值后，将剩余的记录；输出堆顶的最小（大）值后，将剩余的 n-1 n-1 个元个元个元个元 素重又建成一个堆，则可得到素重又建成一个堆，则可得到素重又建成一个堆，则可得到素重又建成一个堆，则可得到 n n 个元素的次小值；如此个元素的次小值；如此个元素的次小值；如此个元素的次小值；如此 重复执行，直到堆中只有一个记录为止，每个记录出堆重复执行，直到堆中只有一个记录为止，

23、每个记录出堆重复执行，直到堆中只有一个记录为止，每个记录出堆重复执行，直到堆中只有一个记录为止，每个记录出堆 的依次就是一个有序序列，这个过程叫堆排序。的依次就是一个有序序列，这个过程叫堆排序。的依次就是一个有序序列，这个过程叫堆排序。的依次就是一个有序序列，这个过程叫堆排序。817364279812第一个问题解决方法：第一个问题解决方法：建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。例例:排序之前的关键字序列为：排序之前的关键字序列为：40554936123673499881984940 现在，左现在，左/右子树都已经调整为堆，最终只要调右子树都已经调整为堆，最终只

24、要调整根结点，使整个二叉树是个整根结点，使整个二叉树是个“堆堆”即可。即可。817355 从无序序列的第从无序序列的第 n/2 的元素（即无序序列对应的完全二的元素（即无序序列对应的完全二叉树的最终一个内部结点）起，至第一个元素止，进行反复叉树的最终一个内部结点）起，至第一个元素止，进行反复筛选。筛选。堆堆堆堆筛筛选选所谓所谓“筛选筛选”指的是，对一棵左指的是，对一棵左/右子树均为堆的完右子树均为堆的完全二叉树，全二叉树，“调整调整”根结点使整个二叉树也成为一个根结点使整个二叉树也成为一个堆。堆。其次个问题解决方法其次个问题解决方法筛选：筛选：输出堆顶元素之后，以堆中最终一个元素替输出堆顶元素

25、之后，以堆中最终一个元素替代之；然后将根结点值与左、右子树的根结点值代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操进行比较，并与其中小者进行交换；重复上述操作直至叶子结点，将得到新的堆，称这个从堆顶作直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为至叶子的调整过程为“筛选筛选”。132738496576499797972797499738979749656549764976979765762765493849971376对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的所需进行的关键字比较的次数至多为次数至多为 2(k-1)。例

26、子：关键字序列为例子：关键字序列为 42，13，91，23，24，16，05，88，n=8，故从第四个结点起先，故从第四个结点起先调整调整4242131391912323242416160505888842 13 91 23 24 16 05 884242131391918888242416160505232342 13 91 88 24 16 05 23不调整不调整4242131391918888242416160505232342 13 91 88 24 16 05 234242888891912323242416160505131342 88 91 23 24 16 05 1391918

27、88842422323242416160505131391 88 42 23 24 16 05 13建成的堆建成的堆筛选算法筛选算法:(假假设设rkrk的的左左右右子子树树均均为为堆堆，将将以以rkrk为为根根的的完完全全二二叉叉树树建建成成大顶堆）大顶堆）void Sift(Record r,int k,int m)i=k;j=2*i;/置置i 为要筛选的结点，为要筛选的结点，j为为i的左孩子的左孩子 while(j=m)/筛选还没有进行到叶子结点筛选还没有进行到叶子结点 if(jm&rj.keyrj.key)break;/根结点已经大于左、右孩子中的较大者根结点已经大于左、右孩子中的较大者

28、 else rirj;/将根结点与结点将根结点与结点j交换交换 i=j;j=2*i;/被筛结点位于原来结点被筛结点位于原来结点j的位置的位置 上述算法只是对一个指定的结点进行调整。有了这上述算法只是对一个指定的结点进行调整。有了这个算法，则将初始的无序区个算法，则将初始的无序区r1r1到到rnrn建成一个大顶堆，建成一个大顶堆，可用以下语句实现可用以下语句实现：for(i=n/2;i=1;i-)Sift(r,i,n)由于建堆的结果把关键字最大的记录选到了堆由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应当将顶的位置，而排序的结果应是升序，所以，应当将r1和和rn

29、交换，这就得到了第一趟排序的结果。交换，这就得到了第一趟排序的结果。其次趟排序的操作首先是将无序区其次趟排序的操作首先是将无序区r1到到rn-1调整为堆。这时对于当前堆来说，它的左右子树照调整为堆。这时对于当前堆来说，它的左右子树照旧是堆，所以，可以调用旧是堆，所以，可以调用Sift函数将函数将r1到到rn-1调调整为大根堆，选出最大关键字放入堆顶，然后将堆整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最终一个记录顶与当前无序区的最终一个记录rn-1交换，如此交换，如此反复进行下去。反复进行下去。9191888842422323242416160505131391 88 42 2

30、3 24 16 05 13（1 1）初始堆）初始堆R1R1到到R8R81313888842422323242416160505919113 88 42 23 24 16 05 91（2 2）第一趟排序之后）第一趟排序之后（3 3）重建的堆）重建的堆r1r1到到r7r78888242442422323131316160505919188 24 42 23 13 16 05 910505242442422323131316168888919105 24 42 23 13 16 88 91（4 4）其次趟排序之后）其次趟排序之后（5 5）重建的堆）重建的堆r1r1到到r6r6424224241616

31、2323131305058888919142 24 16 23 13 05 88 91（6 6）第三趟排序之后）第三趟排序之后0505242416162323131342428888919105 24 16 23 13 42 88 91（7 7）重建的堆）重建的堆r1r1到到r5r52424232316160505131342428888919124 23 16 05 13 42 88 91（8 8）第四趟排序之后）第四趟排序之后1313232316160505242442428888919113 23 16 05 24 42 88 91（9 9）重建的堆）重建的堆r1r1到到r4r42323

32、131316160505242442428888919123 13 16 05 24 42 88 91（1010）第五趟排序之后）第五趟排序之后0505131316162323242442428888919105 13 16 23 24 42 88 91（1111）重建的堆）重建的堆r1r1到到r3r31616131305052323242442428888919116 13 05 23 24 42 88 91（1212）第六趟排序之后）第六趟排序之后0505131316162323242442428888919105 13 16 23 24 42 88 91（1313）重建的堆）重建的堆r1

33、r1到到r2r21313050516162323242442428888919113 05 16 23 24 42 88 91（1414）第七趟排序之后）第七趟排序之后0505131316162323242442428888919105 13 16 23 24 42 88 91堆排序算法：堆排序算法：void HeapSort(Record r,int n)void HeapSort(Record r,int n)for(i=n/2;i=1;i-)for(i=n/2;i=1;i-)Sift(r,i,n);Sift(r,i,n);/初初始始建建堆堆，从从最最终终一一个个非非终终端端结结点至根结点

34、进行筛选点至根结点进行筛选 for(i=1;in;i+)for(i=1;in;i+)/重重复复执行移走堆顶及重建堆的操作执行移走堆顶及重建堆的操作 r1rn-i+1;r1rn-i+1;Sift(r,1,n Sift(r,1,ni);i);堆排序的时间困难度：堆排序的时间困难度：1.对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的次数至所需进行的关键字比较的次数至多为多为 2(k-1)；3.调整调整“堆顶堆顶”n-1 次，总共进行的关键字比较的次数不超次，总共进行的关键字比较的次数不超过过 2(log2(n-1)+log2(n-2)+log22)2n(log2n)因此，堆排序

35、的时间困难度为因此，堆排序的时间困难度为 O(nlog2n)，与简洁选择，与简洁选择排序排序 O(n2)相比时间效率提高了很多。相比时间效率提高了很多。2.对对 n 个关键字，建成深度为个关键字，建成深度为 h(=log2n+1)的堆，的堆，所需进所需进行行 的关键字比较的次数至多的关键字比较的次数至多 4n；堆排序是一种堆排序是一种速度快速度快的排序方法。的排序方法。不稳定。不稳定。不稳定。不稳定。将两个或两个以上的序列组合成一个新的有序表。将两个或两个以上的序列组合成一个新的有序表。在内部排序中，通常接受的是在内部排序中，通常接受的是 2-路归并排序。即将路归并排序。即将两个位置相邻的记录

36、有序子序列归并为一个记录有序的两个位置相邻的记录有序子序列归并为一个记录有序的序列。序列。初始关键字：初始关键字：49 38 65 97 76 13 27 一趟归并后：一趟归并后：38 49 65 97 13 76 27 9.6 归并归并排序排序 看成是看成是 n 个有序的子序列（长度个有序的子序列（长度为为 1），然后两两归并。），然后两两归并。得到得到 n/2 个长度为个长度为2 或或 1 的有序子序列的有序子序列每趟归并的时间困难度为每趟归并的时间困难度为O(n)，共需进行，共需进行 log2n 趟。趟。时间困难度为：时间困难度为：O(nlog2n)，稳定。稳定。二趟归并后：二趟归并后：

37、38 49 65 97 13 27 76 三趟归并后：三趟归并后：13 27 38 49 65 76 97 一趟归并后：一趟归并后：38 49 65 97 13 76 27 归并排序示例归并排序示例(25)(57)(48)(37)(12)(92)(86)(25 57)(37 48)(12 92)(86)(25 37 48 57)(12 86 92)(12 25 37 48 57 86 92)前面所探讨的排序算法均是基于关键字之前面所探讨的排序算法均是基于关键字之间的比较来实现的间的比较来实现的,而基数排序是通过而基数排序是通过“支配支配”和和“收集收集”过程来实现排序。过程来实现排序。9.7

38、基数基数排序排序 例例 对对52张扑克牌按以下次序排序：张扑克牌按以下次序排序：2 3.A 2 3.A 2 3 A 2 3 A 两个关键字：两个关键字：花色花色（）面值（面值（23A）614921485637738101215530790306第一趟支配（按最低位第一趟支配（按最低位）614738637921101485215530790306第一趟收集第一趟收集530790921101614485215306637738614921485637738101215530790306其次趟支配（按次低位）其次趟支配（按次低位）921485614215738637530790101306其次趟收集

39、其次趟收集530790921101614485215306637738614921485637738101215530790306第三趟支配（按最高位）第三趟支配（按最高位）921485614637101215530738790306第三趟收集第三趟收集530790921101614485215306637738 基数排序是一种稳定的排序方法基数排序是一种稳定的排序方法 初始序列的不同不会影响算法的效率初始序列的不同不会影响算法的效率 不是每趟排序后都将某个数据放置在它不是每趟排序后都将某个数据放置在它 的最终位置的最终位置排序方法分类：排序方法分类：1)、插入排序：干脆插入排序、希尔排序、插

40、入排序：干脆插入排序、希尔排序 2)、交换排序：、交换排序：冒泡排序、快速排序冒泡排序、快速排序 3)、选择排序：简洁选择排序、堆排序、选择排序：简洁选择排序、堆排序 4)、归并排序：、归并排序：2-路归并排序路归并排序 基于不同的基于不同的“扩大扩大”有序序列长度的方法，内有序序列长度的方法，内部排序可分下列几种类型：部排序可分下列几种类型：将无序子序列中的一个或几个记将无序子序列中的一个或几个记录录“插入插入插入插入”到有序序列中，从而到有序序列中，从而增加记录的有序子序列的长度。增加记录的有序子序列的长度。通过通过“交换交换交换交换”无序序列中的记录从而无序序列中的记录从而 得到其中得到

41、其中关键字最小关键字最小或或最大最大的记录，并的记录，并 将它将它加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。从记录的无序子序列中从记录的无序子序列中“选择选择选择选择”关键字最小关键字最小或或最大最大的记录，并将它的记录，并将它 加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。通过通过“归并归并归并归并”两个两个 或两个或两个以上的记录有以上的记录有 序子序列，逐步增序子序列，逐步增加加 记录有序序列的长度。记录有序序列的长度。一、时间性能一、时间性能 时间

42、困难度为时间困难度为 O(nlogn)：快速排序、堆排序和：快速排序、堆排序和 归并排序，其中以快速排序为最好。归并排序，其中以快速排序为最好。时间困难度为时间困难度为 O(n2)：干脆插入排序、起泡排序和：干脆插入排序、起泡排序和简洁选择排序，其中以干脆插入为最好，特殊是对简洁选择排序，其中以干脆插入为最好，特殊是对那些对关键字基本有序的记录序列尤为如此。那些对关键字基本有序的记录序列尤为如此。时间困难度为时间困难度为 O(n)：基数排序。：基数排序。1.按平均时间性能来分，有三类排序方法：按平均时间性能来分，有三类排序方法：各种排序方法的综合比较各种排序方法的综合比较 2.当待排序列按关键

43、字依次有序时，干脆插入排序当待排序列按关键字依次有序时，干脆插入排序和起泡排序能达到和起泡排序能达到 O(n)的时间困难度，快速排序的时间困难度，快速排序的时间性能蜕化为的时间性能蜕化为 O(n2)。3.简洁选择排序、堆排序和归并排序的时间性能不简洁选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而变更。随记录序列中关键字的分布而变更。二、空间性能二、空间性能 指的是排序过程中所需的帮助空间大小。指的是排序过程中所需的帮助空间大小。1.全部的简洁排序方法全部的简洁排序方法(包括：干脆插入、冒泡和包括：干脆插入、冒泡和简洁选择简洁选择)和和 堆排序的空间困难度为堆排序的空间困难度为

44、 O(1)；2.快速排序为快速排序为 O(logn)，为递归程序执行过程中，栈，为递归程序执行过程中，栈3.所需的帮助空间；所需的帮助空间；3.归并排序所需帮助空间最多，空间困难度为归并排序所需帮助空间最多，空间困难度为 O(n)；三、排序方法的稳定性能三、排序方法的稳定性能 1.对于不稳定的排序方法，只要能举出一个实例说对于不稳定的排序方法，只要能举出一个实例说2.明即可。明即可。2.快速排序、堆排序和希尔排序是不稳定的排序方快速排序、堆排序和希尔排序是不稳定的排序方3.法法。教学要求教学要求 1、驾驭排序的基本概念和各种排序方法的、驾驭排序的基本概念和各种排序方法的特点，并能加以灵敏应用；特点，并能加以灵敏应用；2、驾驭插入排序、希尔排序、交换排序、驾驭插入排序、希尔排序、交换排序、选择排序、归并排序、基数排序的排序过选择排序、归并排序、基数排序的排序过程及算法的实现。程及算法的实现。End.希望同学们细致复习，希望同学们细致复习，争取期末考试好成果！争取期末考试好成果！