《数据结构与算法》第九章排序..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 仍领先于仍领

3、先于 Rj，则称所用的，则称所用的排序方法是稳定的排序方法是稳定的；反之，则称所用的反之，则称所用的排序方法是不稳定的排序方法是不稳定的。设排序前的关键字序列为：设排序前的关键字序列为：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 插入排序插入排序 有序序列有序序

5、列 R1.i-1 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

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

7、6 08 21 25 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 9

10、79738 49 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 T(n n)=)=O O(n n2 2)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)枢轴枢轴 一次划分一次划分 分别进行一趟快速排序分别进行一趟快速排序 有有 序序 的的 记记

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

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

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

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

17、一个记录交换。的记录，将它与第一个记录交换。再通过再通过 n n 2 2 次比较，从剩余的次比较，从剩余的 n n 1 1 个记录个记录中找出关键字次小的记录，将它与第二个记录交换。中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行重复上述操作，共进行 n n 1 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 五趟五趟:13 27 38 49 65 97 76

18、六趟六趟: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 O(n n2 2)for(i=0;i n-1;+i)i

19、nt k=i;(1)21 25 49 25*16 08 练习练习 简单选择排序是一种不稳定的排序方法。简单选择排序是一种不稳定的排序方法。请举例说明。请举例说明。9.5.2 堆排序堆排序 堆排序是选择排序的改进（堆排序是选择排序的改进（1964提出）。提出）。在排序过程中，在排序过程中，将将r1到到rn看成是一个看成是一个完全二叉树顺序存储结构完全二叉树顺序存储结构，利用完全二叉，利用完全二叉树中双亲结点和孩子结点之间的内在关系树中双亲结点和孩子结点之间的内在关系来选择最小或最大元素。来选择最小或最大元素。堆的定义：堆的定义：n个数据序列个数据序列K1,k2,.,Kn称为堆，称为堆，当且仅当该

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

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

22、，得到关键字最小（大）的 记录；记录；输出堆顶的最小（大）值后，将剩余的输出堆顶的最小（大）值后，将剩余的 n-1 个元个元 素重又建成一个堆素重又建成一个堆，则可得到，则可得到 n 个元素的次小值；如此个元素的次小值；如此 重复执行，重复执行，直到堆中只有一个记录为止，每个记录出堆直到堆中只有一个记录为止，每个记录出堆 的顺序就是一个有序序列的顺序就是一个有序序列，这个过程叫，这个过程叫堆排序堆排序。817364279812第一个问题解决方法：第一个问题解决方法：建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。例例:排序之前的关键字序列为：排序之前的关键字序列为：40

23、554936123673499881984940 现在，左现在，左/右子树都已经调整为堆，最后只要调右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个整根结点，使整个二叉树是个“堆堆”即可。即可。817355 从无序序列的第从无序序列的第 n/2 的的元素（即无序序列对应元素（即无序序列对应的完全二叉树的最后一个内部结点）起，至第一个元的完全二叉树的最后一个内部结点）起，至第一个元素止，进行反复筛选。素止，进行反复筛选。堆堆堆堆筛筛选选所谓所谓“筛选筛选”指的是，对一棵左指的是，对一棵左/右子树均为堆的完右子树均为堆的完全二叉树，全二叉树，“调整调整”根结点使整个二叉树也成为一个根结点

24、使整个二叉树也成为一个堆。堆。第二个问题解决方法第二个问题解决方法筛选：筛选：输出堆顶元素之后，输出堆顶元素之后，以堆中最后一个元素替以堆中最后一个元素替代之代之；然后将根结点值与左、右子树的根结点值然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；进行比较，并与其中小者进行交换；重复上述操重复上述操作直至叶子结点，将得到新的堆，称这个从堆顶作直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为至叶子的调整过程为“筛选筛选筛选筛选”。132738496576499797972797499738979749656549764976979765762765493849971

25、376对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的所需进行的关键字比较的次数至多为次数至多为 2(k-1)。例子：例子：关键字序列为关键字序列为 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

26、 05 234242888891912323242416160505131342 88 91 23 24 16 05 139191888842422323242416160505131391 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)/筛选还没有进行到叶子结点筛选还没有

27、进行到叶子结点 if(jm&rj.keyrj.key)break;/根结点已经大于左、右孩子中的较大者根结点已经大于左、右孩子中的较大者 else rirj;/将根结点与结点将根结点与结点j交换交换 i=j;j=2*i;/被筛结点位于原来结点被筛结点位于原来结点j的位置的位置 上述算法只是对一个指定的结点进行调整。有了这上述算法只是对一个指定的结点进行调整。有了这个算法，则将初始的无序区个算法，则将初始的无序区r1r1到到rnrn 建成一个大顶堆，建成一个大顶堆，可用以下语句实现可用以下语句实现：for(i=n/2;i=1;i-)Sift(r,i,n)由于建堆的结果把关键字最大的记录选到了堆顶

28、的由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将位置，而排序的结果应是升序，所以，应该将r1r1和和rnrn 交换，这就得到了第一趟排序的结果。交换，这就得到了第一趟排序的结果。第二趟排序的操作首先是将无序区第二趟排序的操作首先是将无序区r1r1到到rn-1rn-1调整调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用以，可以调用SiftSift函数将函数将r1r1到到rn-1rn-1调整为大根堆，选调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后出最大关键字放入堆顶，然后

29、将堆顶与当前无序区的最后一个记录一个记录rn-1rn-1交换，如此反复进行下去。交换，如此反复进行下去。9191888842422323242416160505131391 88 42 23 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 9105052424424223231

30、31316168888919105 24 42 23 13 16 88 91（4 4）第二趟排序之后）第二趟排序之后（5 5）重建的堆）重建的堆r1r1到到r6r64242242416162323131305058888919142 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）第四趟排

31、序之后）第四趟排序之后1313232316160505242442428888919113 23 16 05 24 42 88 91（9 9）重建的堆）重建的堆r1r1到到r4r42323131316160505242442428888919123 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 9

32、1（1212）第六趟排序之后）第六趟排序之后0505131316162323242442428888919105 13 16 23 24 42 88 91（1313）重建的堆）重建的堆r1r1到到r2r21313050516162323242442428888919113 05 16 23 24 42 88 91（1414）第七趟排序之后）第七趟排序之后0505131316162323242442428888919105 13 16 23 24 42 88 91堆排序算法：堆排序算法：void HeapSort(Record r,int n)for(i=n/2;i=1;i-)Sift(r,i,

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

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

35、。即将两个位置相邻的记录有序子序列归并为一个记录有序的两个位置相邻的记录有序子序列归并为一个记录有序的序列。序列。初始关键字：初始关键字：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)，稳定。稳定。

36、二趟归并后：二趟归并后：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)前面所讨论的排序算法均是基于关键字之前面所讨论的排序算法均是基于关键字之间的比较来实现的间的比较来实现的,而基数排序是通过而基数排序是通过“分配分配”和和“收集收集”过程来实现排序。

37、过程来实现排序。9.7 基数基数排序排序 例例 对对52张扑克牌按以下次序排序：张扑克牌按以下次序排序：2 3.A 2 3.A 2 3 A 2 3 A 两个关键字：两个关键字：花色花色（）面值（面值（23A）614921485637738101215530790306第一趟分配（按最低位第一趟分配（按最低位）614738637921101485215530790306第一趟收集第一趟收集530790921101614485215306637738614921485637738101215530790306第二趟分配（按次低位）第二趟分配（按次低位）92148561421573863753079

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

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

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

41、间性能一、时间性能 时间复杂度为时间复杂度为 O(nlogn)：快速排序、堆排序和快速排序、堆排序和 归并排序归并排序，其中以快速排序为最好。其中以快速排序为最好。时间复杂度为时间复杂度为 O(n2)：直接插入排序、起泡排序和简直接插入排序、起泡排序和简单选择排序，单选择排序，其中以直接插入为最好，特别是对那其中以直接插入为最好，特别是对那其中以直接插入为最好，特别是对那其中以直接插入为最好，特别是对那些对关键字基本有序的记录序列尤为如此。些对关键字基本有序的记录序列尤为如此。些对关键字基本有序的记录序列尤为如此。些对关键字基本有序的记录序列尤为如此。时间复杂度为时间复杂度为 O(n)：基数排

42、序。基数排序。1.按平均时间性能来分，有三类排序方法：按平均时间性能来分，有三类排序方法：各种排序方法的综合比较各种排序方法的综合比较 2.当待排序列按关键字顺序有序时，直接插入排序当待排序列按关键字顺序有序时，直接插入排序和起泡排序能达到和起泡排序能达到 O(n)的时间复杂度，快速排序的时间复杂度，快速排序的时间性能蜕化为的时间性能蜕化为 O(n2)。3.简单选择排序、堆排序和归并排序的时间性能不简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。随记录序列中关键字的分布而改变。二、空间性能二、空间性能 指的是排序过程中所需的辅助空间大小。指的是排序过程中所需的辅助空间

43、大小。1.所有的简单排序方法所有的简单排序方法(包括：直接插入、冒泡和包括：直接插入、冒泡和简单选择简单选择)和和 堆排序的空间复杂度为堆排序的空间复杂度为 O(1)；2.快速排序为快速排序为 O(logn)，为递归程序执行过程中，栈为递归程序执行过程中，栈3.所需的辅助空间；所需的辅助空间；3.归并排序所需辅助空间最多，空间复杂度为归并排序所需辅助空间最多，空间复杂度为 O(n)；三、排序方法的稳定性能三、排序方法的稳定性能 1.对于不稳定的排序方法，只要能举出一个实例说对于不稳定的排序方法，只要能举出一个实例说2.明即可。明即可。2.快速排序、堆排序和希尔排序是不稳定的排序方快速排序、堆排序和希尔排序是不稳定的排序方3.法法。教学要求教学要求 1、掌握排序的基本概念和各种排序方法的、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；特点，并能加以灵活应用；2、掌握、掌握插入排序插入排序、希尔排序希尔排序、交换排序交换排序、选择排序选择排序、归并排序归并排序、基数排序、基数排序的排序过的排序过程及算法的实现。程及算法的实现。End.希望同学们认真复习，希望同学们认真复习，争取期末考试好成绩！争取期末考试好成绩！