文本教案成果d

1、第 2 页l排序排序(Sorting)：将一个数据元素（记录）的将一个数据元素（记录）的任意序列，重新排列成一个任意序列，重新排列成一个按关键字有序按关键字有序的的序列。序列。 设：设：R1，R2，R3，Rn 是是n个记录，个记录，k1，k2，k3，kn 为它们的关键字，排序就是为它们的关键字，排序就是将记录按关键字将记录按关键字递增递增（或（或递减递减）的次序排列）的次序排列起来。起来。l常见的排序结果常见的排序结果 递递 增：增：k ki i k ki+1i+1 递递 减：减：k ki i k ki+1i+1 非递减：非递减：k ki i k ki+1i+1 非递增：非递增：k ki i

2、k ki+1i+110.110.1 排序概述排序概述第 3 页l排序的分类排序的分类按照排序记录所在的位置划分按照排序记录所在的位置划分 内部排序：内部排序：待排序记录存放在计算机待排序记录存放在计算机随随机存储器中（内存）机存储器中（内存）进行排序过程。进行排序过程。 外部排序：外部排序：待排序记录数量很大，内存待排序记录数量很大，内存无法一次容纳全部记录，在排序过程中无法一次容纳全部记录，在排序过程中尚需尚需对外存进行访问对外存进行访问的排序过程。的排序过程。10.110.1 排序概述排序概述第 4 页无序序列区无序序列区l内部排序的分类：内部排序的分类：内部排序的过程就是一个内部排序的过

3、程就是一个逐步扩大逐步扩大记录的记录的有序序列长度的过程。有序序列长度的过程。10.110.1 排序概述排序概述按照逐步扩大的方式划分：按照逐步扩大的方式划分：插入排序插入排序：直接插入排序直接插入排序、折半插入排序、希尔、折半插入排序、希尔排序排序交换排序交换排序：冒泡排序冒泡排序、快速排序、快速排序选择排序选择排序：简单选择排序简单选择排序、堆排序、堆排序归并排序归并排序：2-路归并排序路归并排序基数排序基数排序：有序序列区有序序列区无序序列区无序序列区有序序列区有序序列区第 5 页l内部排序的分类：内部排序的分类：按排序所需工作量划分按排序所需工作量划分 简单的排序方法简单的排序方法：T

4、(n)=O(n) 先进的排序方法先进的排序方法：T(n)=O(logn) 基数排序基数排序：T(n)=O(d.n)l排序排序的的基本操作基本操作：比较两个关键字大小。比较两个关键字大小。将记录从一个位置移动到另一个位置。将记录从一个位置移动到另一个位置。10.110.1 排序概述排序概述第 6 页l待排序记录的存储方式：待排序记录的存储方式：1.地址连续的存储单元地址连续的存储单元：记录的次序关系由：记录的次序关系由其存储位置决定（排序必须移动记录）。其存储位置决定（排序必须移动记录）。2.静态链表静态链表：记录的次序关系由指针指示：记录的次序关系由指针指示（排序不必移动记录）。（排序不必移动

5、记录）。3.地址连续的存储单元地址连续的存储单元+指示位置的地址向指示位置的地址向量量：排序不移动记录，排序后调整记录。：排序不移动记录，排序后调整记录。10.110.1 排序概述排序概述第 7 页#define MAXSIZE 20/ 顺序表的最大长度顺序表的最大长度typedef int KeyType； / 定义关键字类型定义关键字类型typedef struct KeyType key; / 关键字关键字 InfoType otherinfo; / 其他数据项其他数据项 RedType;/ 记录类型记录类型10.110.1 排序概述排序概述typedef struct typedef

6、struct RedType r MAXSIZE + 1 ; RedType r MAXSIZE + 1 ; / r0 / r0闲置或作哨兵闲置或作哨兵 int length;int length; SqList; SqList;第 8 页l评价排序的性能评价排序的性能稳定性稳定性稳定的排序方法：稳定的排序方法：设在排序前的序列中记录设在排序前的序列中记录 Ri 领先于领先于 Rj（即（即 ij ），且），且 Ri、Rj 对应的对应的关键字为关键字为 Ki、Kj，如果，如果 KiKj 并且在排序并且在排序后的序列中后的序列中 Ri 仍领先于仍领先于 Rj，称所用方法是，称所用方法是稳定的稳定的

7、。不稳定的排序方法：不稳定的排序方法：排序后的序列中排序后的序列中Rj领先领先于于Ri。10.110.1 排序概述排序概述待排序列：待排序列：49,38,65,97,76,13,27,49 排序后排序后: 13,27,38,49,49,65,76,97 稳定稳定排序后排序后: 13,27,38,49,49,65,76,97 不稳定不稳定第 9 页l直接插入排序直接插入排序是一种最简单的排序方法。是一种最简单的排序方法。基本思想基本思想：将一个记录插入到已排好序的：将一个记录插入到已排好序的有序有序表表中，得到一个新的、记录数增中，得到一个新的、记录数增 1 的有序表。的有序表。整个排序过程为整

8、个排序过程为 n-1 趟插入趟插入排序：排序：即先将序列即先将序列中第中第 1 个记录看成是一个个记录看成是一个有序子序列有序子序列，然后，然后从第从第 2 个记录开始，逐个进行插入，直至整个记录开始，逐个进行插入，直至整个序列有序个序列有序。其中，一趟插入排序包括其中，一趟插入排序包括三个步骤三个步骤：10.2 10.2 插入排序插入排序直接插入排序直接插入排序第 10 页l一趟插入排序过程：一趟插入排序过程：10.2 10.2 插入排序插入排序直接插入排序直接插入排序 前提：在插入第前提：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录个记录已经排好序已经排好序(非递减

9、的序列非递减的序列)。 1.查找插入位；查找插入位；2.后移插入位后的有序记录；后移插入位后的有序记录；3.插入。插入。 有序序列有序序列无序序列无序序列12i-1ini+112i-1ini+1第 11 页 算法的实现算法的实现10.2 10.2 插入排序插入排序直接插入排序直接插入排序Status InsertSort ( SqList &L ) Status InsertSort ( SqList &L ) for( i=2; i=L.length; +i ) for( i=2; i=L.length; +i ) ifif ( ( LTLT( L.ri.key, L.ri-

10、1.key ) )( L.ri.key, L.ri-1.key ) ) L.r0.key = L.ri.key; L.r0.key = L.ri.key; /设置哨兵设置哨兵 for(j=i-1; for(j=i-1; LTLT(L.r0.key,L.rj.key); -j)(L.r0.key,L.rj.key); -j) L.rj+1 = L.rj; L.rj+1 = L.rj; /记录后移记录后移 L.rj+1 = L.r0; L.rj+1 = L.r0; /插入到正确位置插入到正确位置 /InsertSort/InsertSort第 12 页l直接插入排序过程：直接插入排序过程：10.2

11、 10.2 插入排序插入排序直接插入排序直接插入排序L.r0L.r0 初始关键字初始关键字 ： （4949）38 65 97 76 13 27 4938 65 97 76 13 27 49i=2i=2： （3838）（）（38 4938 49）65 97 76 13 27 4965 97 76 13 27 49i=3i=3： （6565）（）（38 49 6538 49 65）97 76 13 27 4997 76 13 27 49i=4i=4： （9797）（）（38 49 65 9738 49 65 97）76 13 27 4976 13 27 49i=5i=5： （7676）（）（38

12、49 65 76 9738 49 65 76 97）13 27 4913 27 49i=6i=6： （1313）（）（13 38 49 65 76 9713 38 49 65 76 97）27 4927 49i=7i=7： （2727）（）（13 27 38 49 65 76 9713 27 38 49 65 76 97）4949i=8i=8： （4949）（）（13 27 48 49 49 65 76 9713 27 48 49 49 65 76 97）第 13 页10.2 10.2 插入排序插入排序直接插入排序直接插入排序 直接插入排序算法性能分析直接插入排序算法性能分析 “移动移动”次数

13、次数= 0 “比较比较”次数次数= u最好的情况（正序序列）最好的情况（正序序列） “比较比较”次数次数= u最坏的情况（逆序序列）最坏的情况（逆序序列） u平均平均复杂度复杂度 O(n2) “移动移动”次数次数= n-11 ni=2i ni=22) 1)(2(-+=nn2+( i-1) ni=22(n+4)(n-1)=( i+1) ni=2第 14 页 直接插入排序的特点直接插入排序的特点10.2 10.2 插入排序插入排序直接插入排序直接插入排序（1）若待排序记录按关键码）若待排序记录按关键码基本有序基本有序时，直时，直接插入排序的效率可以大大提高。接插入排序的效率可以大大提高。（2）由于

14、直接插入排序算法简单，则在待排）由于直接插入排序算法简单，则在待排序记录数量序记录数量n较小较小时效率也很高。时效率也很高。 第 15 页如何改进直接插入排序如何改进直接插入排序?10.2 10.2 插入排序插入排序折半插入排序折半插入排序 在插入第在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1 个记录已经排好序，在寻找插入位置时，可个记录已经排好序，在寻找插入位置时，可以用以用折半查找来代替顺序查找折半查找来代替顺序查找，从而减少比，从而减少比较次数。较次数。折半插入排序基本思想折半插入排序基本思想： 用折半查找方法确定插入位置的排序。用折半查找方法确定插入位置的排序。第 1

15、6 页10.2 10.2 插入排序插入排序折半插入排序折半插入排序例例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 20 30 39 42 70 85 )sjmjsmsj第 17

16、 页l希尔排序基本思想：希尔排序基本思想： 将整个待排记录序列分割成为若干将整个待排记录序列分割成为若干子序列子序列分分别进行别进行直接插入排序直接插入排序，待整个序列中的记录，待整个序列中的记录“基本有序基本有序”时，再对全体记录进行一次直接时，再对全体记录进行一次直接插入排序。插入排序。 子序列子序列的构成不是简单的的构成不是简单的“逐段分割逐段分割”，而，而是将是将相隔某个相隔某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。l分割待排序记录的目的：分割待排序记录的目的：减少待排序记录个数；减少待排序记录个数；使整个序列向基本有序发展。使整个序列向基本有序发展。10.2 10.

17、2 插入排序插入排序希尔排序希尔排序第 18 页l例如，将例如，将n个记录分割为个记录分割为d个子序列。个子序列。R1, R1+d, R1+2d,R1+kdR2, R2+d, R2+2d,R2+kdRd, R2d, R3d,Rkd,R(k+1)d其中，增量其中，增量d的值在排序过程中的值在排序过程中从大到小逐从大到小逐渐减少渐减少，直到最后一次排序减为，直到最后一次排序减为1。10.2 10.2 插入排序插入排序希尔排序希尔排序第 19 页l具体实现办法具体实现办法先取一个正整数先取一个正整数 d1n，把所有相隔把所有相隔d1 的记录放的记录放一组，一组，组内进行直接插入排序组内进行直接插入排

18、序； 然后取然后取 d2=1; d=d/2) 以以d为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；第 20 页l希尔排序实例：希尔排序实例：假设：假设：d1=5，d2=3，d3=1。10.2 10.2 插入排序插入排序希尔排序希尔排序 初始关键字初始关键字 ： 49 38 65 97 76 13 27 49 38 65 97 76 13 27 4949 55 04 55 04 49 13 49 13 38 2738 27 65 65 4949 97 5597 55 76 0476 04一趟排序结果：一趟排序结果： 13 13 2727 4949 55 55 0404 49 49

19、3838 65 9765 97 76 76 13 13 5555 3838 7676 27 04 6527 04 65 4949 49 97 49 97二趟排序结果：二趟排序结果： 13 13 0404 4949 38 38 2727 4949 55 55 65 65 97 97 76 76三趟排序结果三趟排序结果: : 04 13 27 38 04 13 27 38 4949 49 55 65 76 97 49 55 65 76 97第 21 页 由于在前两趟的插入排序中，记录的关由于在前两趟的插入排序中，记录的关键字是与同一子序列中的前一个记录的关键键字是与同一子序列中的前一个记录的关键字

20、进行比较，因此关键字较小的记录不是一字进行比较，因此关键字较小的记录不是一步一步的往前挪动，而是步一步的往前挪动，而是跳跃式跳跃式的往前移。的往前移。 在进行最后一趟增量为在进行最后一趟增量为 1 1 的插入排序的插入排序时，序列已基本有序，只要作记录的少量比时，序列已基本有序，只要作记录的少量比较和移动即可完成排序。因此较和移动即可完成排序。因此比直接插入排比直接插入排序快序快。 希尔排序算法是希尔排序算法是不稳定不稳定的排序算法。的排序算法。10.2 10.2 插入排序插入排序希尔排序希尔排序第 22 页l交换排序的基本思想交换排序的基本思想 交换排序的主要操作是交换排序的主要操作是交换交

21、换。 在待排序列中选在待排序列中选两个两个记录，将它们的关键记录，将它们的关键字值相比较，如果字值相比较，如果反序反序（即排列顺序与排序（即排列顺序与排序后的次序正好相反），则后的次序正好相反），则交换交换它们的存储位它们的存储位置。置。10.3 10.3 交换排序交换排序起泡排序起泡排序反序则反序则 交换交换第 23 页l起泡排序起泡排序两两比较两两比较相邻相邻记录的关键码，如果反序则交换，记录的关键码，如果反序则交换，直到没有反序的记录为止。直到没有反序的记录为止。 10.3 10.3 交换排序交换排序起泡排序起泡排序一趟起泡排序一趟起泡排序 无序序列无序序列R1.i有序序列有序序列 Ri

22、+1.n 例：例： 49 38 65 97 76 13 27 49 38 49 65 76 13 27 49 97第 24 页l起泡排序起泡排序 两两比较两两比较相邻相邻记录的关键码，如果反序则记录的关键码，如果反序则交换，直到没有反序的记录为止。交换，直到没有反序的记录为止。 10.3 10.3 交换排序交换排序起泡排序起泡排序rj rj+1 ri+1 rn- -1 rn 无序区无序区 有序区有序区 1ji- -1 已经位于最终位置已经位于最终位置反序则交换反序则交换第 25 页 将第将第1个记录的关键字与第个记录的关键字与第2个记录的关键字进个记录的关键字进行比较，若为逆序行比较，若为逆序

23、r1.keyr2.key，则交换；则交换； 然后比较第然后比较第2个记录与第个记录与第3个记录；依次类推，个记录；依次类推，直至第直至第 n-1 个记录和第个记录和第 n 个记录比较为止个记录比较为止第第一趟冒泡排序一趟冒泡排序，结果关键字，结果关键字最大最大的记录被安置在的记录被安置在最后一个最后一个（第（第n个）个）记录上记录上。 对前对前 n-1 个记录进行个记录进行第二趟冒泡排序第二趟冒泡排序，结果，结果使关键字次大的记录被安置在第使关键字次大的记录被安置在第n-1个记录位置个记录位置。 重复上述过程，直到重复上述过程，直到“在一趟排序过程中没有在一趟排序过程中没有进行过交换记录的操作

24、进行过交换记录的操作”为止为止。 一般：一般：n个记录最多进行个记录最多进行 n-1 趟冒泡排序。趟冒泡排序。10.3 10.3 交换排序交换排序起泡排序起泡排序第 26 页例：例：10.3 10.3 交换排序交换排序起泡排序起泡排序初始关键字：初始关键字： 49 38 65 97 76 13 27 49 38 65 97 76 13 27 4949第一趟排序后：第一趟排序后：38 49 65 76 13 27 38 49 65 76 13 27 4949 9797第二趟排序后：第二趟排序后：38 49 65 13 27 38 49 65 13 27 4949 7676第三趟排序后：第三趟排序

25、后：38 49 13 27 38 49 13 27 4949 6565第四趟排序后：第四趟排序后：38 13 27 49 38 13 27 49 4949第五趟排序后：第五趟排序后：13 27 38 13 27 38 4949第六趟排序后：第六趟排序后：13 27 3813 27 38逐步有序逐步有序第 27 页l快速排序快速排序在起泡排序中，记录的比较和移动是在在起泡排序中，记录的比较和移动是在相邻相邻单单元中进行的，记录每次交换只能上移或下移元中进行的，记录每次交换只能上移或下移一一个单元个单元，因而总的比较次数和移动次数较多。，因而总的比较次数和移动次数较多。10.3 10.3 交换排序

26、交换排序快速排序快速排序减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面第 28 页l 基本思想：基本思想：选定一记录，以它的关键字作为选定一记录，以它的关键字作为“枢轴枢轴”，关关键字小于键字小于枢轴枢轴的记录移的记录移至该记录之前；关键字至该记录之前；关键字大于大于枢轴枢轴的记录的记录移至该记录之后。移至该记录之后。记录序列记录序列 Rs.t 被分割成两部分：被分割成两部分：Rs.i-1和和 Ri+1.t；继续；继续对对R前后两

27、部分记录进行快前后两部分记录进行快速排序。速排序。10.3 10.3 交换排序交换排序快速排序快速排序无序序列无序序列一次划分一次划分枢轴枢轴无序子序列无序子序列1无序子序列无序子序列2快速排序快速排序快速排序快速排序第 29 页l一趟快速排序具体算法：一趟快速排序具体算法：设两个指针设两个指针 low 和和 high，其初值分别指向，其初值分别指向数组的元素数组的元素1和元素和元素n。选第选第 1 个记录为个记录为枢轴枢轴，关键字为，关键字为pivotkey。将将 pivotkey 复制到复制到 r0 中，从中，从 high 所指所指的位置起的位置起 向前向前 搜索找到第一个关键字搜索找到第

28、一个关键字 小于小于pivotkey的记录，复制到的记录，复制到 low 所指位置中；然所指位置中；然后从后从 low 所指位置起所指位置起向后向后搜索，找到第一个关搜索，找到第一个关键字键字 大于大于 pivotkey的记录，复制到的记录，复制到high所指位所指位置中。置中。重复这两步直到重复这两步直到 lowhigh 为止。为止。10.3 10.3 交换排序交换排序快速排序快速排序第 30 页l一趟快速排序算法一趟快速排序算法int Partition ( SqList &L, int low, int high ) L.r0 = L.rlow; pivotkey = L.rlo

29、w.key; while ( low high ) while ( low=pivotkey ) - high; L.rlow = L.rhigh; while ( lowhigh & L.rlow.key=pivotkey ) + low; L.rhigh = L.rlow; L.rlow = L.r0; / 枢轴枢轴记录到位记录到位 return low;/ 返回返回枢轴枢轴的位置的位置 / Partition10.3 10.3 交换排序交换排序快速排序快速排序第 31 页l一趟快速排序的过程一趟快速排序的过程10.3 10.3 交换排序交换排序快速排序快速排序0 1 2 3 4

30、5 0 1 2 3 4 5 6 7 86 7 849493838656597977676131327274949初始关键字初始关键字pivotkey = 49pivotkey = 49lowlowhighhigh0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838656597977676131327274949第一次交换第一次交换lowlowhighhigh0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838656597977676131365654949第二次交换第二次交换lowlowhighhigh第 32 页l一趟快速排序的

31、过程一趟快速排序的过程10.3 10.3 交换排序交换排序快速排序快速排序0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838131397977676131365654949第三次交换第三次交换lowlowhighhigh0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838131397977676979765654949第四次交换第四次交换lowlowhighhigh0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838131349497676979765654949第一趟完成第一趟完成lowlow

32、highhighpivotkey = 49pivotkey = 49子序列子序列1子序列子序列2第 33 页l快速排序的过程快速排序的过程10.3 10.3 交换排序交换排序快速排序快速排序 初始状态初始状态 49 38 65 97 76 13 27 49 38 65 97 76 13 27 4949 一趟快速排序后一趟快速排序后 27 38 13 27 38 13 4949 76 97 65 76 97 65 4949 分别进行快速排序分别进行快速排序 13 13 2727 38 38 结束结束结束结束 4949 65 65 7676 97 97 4949 65 65 结束结束结束结束 有序

33、序列有序序列 13 27 38 49 13 27 38 49 4949 65 76 97 65 76 97 整个快速排序过整个快速排序过程可递归进行程可递归进行第 34 页10.3 10.3 交换排序交换排序快速排序快速排序void void QSortQSort( SqList &L, int low, int high ) ( SqList &L, int low, int high ) /对表对表L L中的子序列中的子序列 L.rlowhigh L.rlowhigh 作快速排序作快速排序 ifif ( low high ) ( low high ) / / 长度大于长度大

34、于1 1 pivotloc = Partition( L, low, high ); pivotloc = Partition( L, low, high ); / / 将将 L.rlowhigh L.rlowhigh 一分为二一分为二 QSortQSort( L, low, pivotloc-1 );( L, low, pivotloc-1 ); / / 对低子表递归排序，对低子表递归排序，pivotlocpivotloc是界点位置是界点位置 QSortQSort( L, pivotloc+1, high ); ( L, pivotloc+1, high ); / / 对高子表对高子表 /Q

35、Sort/QSortvoid QuickSort( SqList &L ) void QuickSort( SqList &L ) /对顺序表对顺序表L L快速排序快速排序 QSortQSort( L, 1, L.length);( L, 1, L.length); /QuickSort/QuickSort第 35 页10.3 10.3 交换排序交换排序快速排序快速排序l 快速排序特点快速排序特点:存储结构：顺序存储结构：顺序不稳定不稳定时间复杂度为时间复杂度为O( nlog2n );空间复杂度为空间复杂度为O( log2n ) 。 最坏情况：最坏情况：每次划分选择枢轴是最小或

36、最大元素每次划分选择枢轴是最小或最大元素 13 . 最好情况（每次划分折半）：最好情况（每次划分折半）： ., 49 第 36 页10.4 10.4 选择排序选择排序l选择排序基本思想选择排序基本思想每趟排序在当前待排序序列中每趟排序在当前待排序序列中选择选择关键码关键码最小最小的记录，添加到有序序列中。的记录，添加到有序序列中。有序序列有序序列12i-1ink无序序列无序序列ni+112i-1ii交换交换最小记录最小记录第 37 页10.4 10.4 选择排序选择排序简单选择排序简单选择排序 一趟简单选择排序：通过一趟简单选择排序：通过 n-i n-i 次关键字间次关键字间的比较，从的比较，

37、从 n-i+1n-i+1 个记录中选出关键字最小的个记录中选出关键字最小的记录，并和第记录，并和第 i i（1=i=n1=i=n）个记录交换。）个记录交换。void SelectSort( SqList &L )void SelectSort( SqList &L ) forfor( i=1; i L.length; +i ) ( i=1; i L.length; +i ) j = SelectMinKey( L, i ); j = SelectMinKey( L, i ); if ( i != j ) if ( i != j ) L.ri L.rj; L.ri L.rj; /

38、SelectSort/SelectSort 对于对于n n个关键字，要进行个关键字，要进行 n-1 n-1 趟选择排序。趟选择排序。第 38 页10.4 10.4 选择排序选择排序简单选择排序简单选择排序例：例：初始：初始： 49 38 65 97 76 13 27 ji=11349一趟：一趟： 13 38 65 97 76 49 27 i=2j2738二趟：二趟： 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 六趟：六趟： 13

39、27 38 49 65 76 97 排序结束：排序结束： 13 27 38 49 65 76 97第 39 页10.4 10.4 选择排序选择排序简单选择排序简单选择排序l 简单选择排序算法的性能分析简单选择排序算法的性能分析最坏情况：最坏情况：3(n-1)次次移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次空间性能：空间性能：需要一个辅助空间。需要一个辅助空间。稳定性：稳定性：是一种是一种不稳定不稳定的排序算法。的排序算法。比较次数：比较次数：= =O O (n2)21n(n-1)= =n-1i=1 （n-i)n-i)简单选择排序的时间复杂度为简单选择排序的时间复杂度为O(n2

40、)。第 40 页10.4 10.4 选择排序选择排序堆排序堆排序l 对简单选择排序算法的改进：对简单选择排序算法的改进： 改进的着眼点：改进的着眼点：如何如何减少减少关键码之间的关键码之间的比较比较次数次数。 核心思想：核心思想：充分利用每趟比较后的结果充分利用每趟比较后的结果。即。即在找出键值最小记录的同时，也利用找出的键在找出键值最小记录的同时，也利用找出的键值较小的记录来减少后面选择中所用的比较次值较小的记录来减少后面选择中所用的比较次数，从而提高整个排序过程的效率。数，从而提高整个排序过程的效率。减少关键码间的比较次数减少关键码间的比较次数查找最小值的同时，找出较小值查找最小值的同时，

41、找出较小值第 41 页10.4 10.4 选择排序选择排序堆排序堆排序例：树型选择排序（锦标赛排序）例：树型选择排序（锦标赛排序）序列：序列：49，38，65，97，76，13，27，49133813381327654938657697132749时间复杂度：时间复杂度：O(nlog2n)；需要较多的；需要较多的辅助存储空辅助存储空间间；不稳定不稳定的排序。的排序。第 42 页10.4 10.4 选择排序选择排序堆排序堆排序l 对简单选择排序算法的改进：对简单选择排序算法的改进：如何如何减少减少关键码之间的关键码之间的比较次数比较次数，同时，同时不不增加增加过多的辅助存储的过多的辅助存储的空间

42、空间。Robert.Floyd和和J.Williams在在1964年共同发年共同发明了明了堆排序算法堆排序算法( Heap Sort ) 。 利用前次比较的结果（较小值），减少利用前次比较的结果（较小值），减少了比较的次数；了比较的次数；只需一个辅助空间记录大小。只需一个辅助空间记录大小。 第 43 页10.4 10.4 选择排序选择排序堆排序堆排序或或堆的定义堆的定义：n n个元素的序列个元素的序列 kk1 1,k,k2 2, ,k,kn n ，当，当且仅当满足以下关系时，称之为且仅当满足以下关系时，称之为堆堆： k ki i = k k2i2i k ki i = k k2i+12i+1 (

43、 i=1 ( i=1，2 2， n/2n/2) )kik2ik2i+1第 44 页10.4 10.4 选择排序选择排序堆排序堆排序l若序列若序列 k1，k2，kn 是堆，则是堆，则堆顶元素堆顶元素必为序列中必为序列中 n 个元素的个元素的最小值（或最大值）最小值（或最大值）。l把把堆序列看成完全二叉树堆序列看成完全二叉树，则，则堆顶元素堆顶元素（完全二叉（完全二叉树的根）必为序列中树的根）必为序列中 n 个元素的个元素的最小值或最大值最小值或最大值。并且，由堆序列形成的完全二叉树中所有非终端结并且，由堆序列形成的完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的点的值均不大于

44、（或不小于）其左、右孩子结点的值。值。小根堆：最小堆小根堆：最小堆大根堆：最大堆大根堆：最大堆分类分类第 45 页10.4 10.4 选择排序选择排序堆排序堆排序 堆序列的实例：堆序列的实例：96969 91111838327272 23 31 14 45 5121247478585919136362424535330306 62 27 73 31 18 84 45 5堆序列：堆序列：96,83,27,11,9堆序列：堆序列：12,36,24,85,47,30,53,91第 46 页10.4 10.4 选择排序选择排序堆排序堆排序l 堆的存储堆的存储: :将堆用顺序存储结构来存储，则堆对应一组

45、序列。将堆用顺序存储结构来存储，则堆对应一组序列。50 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用顺序存储采用顺序存储第 47 页10.4 10.4 选择排序选择排序堆排序堆排序l 堆排序堆排序: :利用堆的特性进行排序。利用堆的特性进行排序。基本思想：基本思想：首先将待排序的记录序列构造成一首先将待排序的记录序列构造成一个堆；然后，选出堆中所有记录的个堆；然后，选出堆中所有记录的最小者最小者；再；再把它从堆中移走，并把剩余的记录再调整成堆，把它从堆中移走，并把剩余的记录再调整成堆，这样又找出了这样又找出了次小次小的记录。以此类推，直到堆的

46、记录。以此类推，直到堆中只有一个记录。中只有一个记录。 l 需解决的关键问题需解决的关键问题? ? 如何由一个无序序列建成一个堆（即初始建堆）？如何由一个无序序列建成一个堆（即初始建堆）？ 如何处理堆顶记录？如何处理堆顶记录？ 如何调整剩余记录，成为一个新堆（即重建堆）？如何调整剩余记录，成为一个新堆（即重建堆）？ 第 48 页10.4 10.4 选择排序选择排序堆排序堆排序131376765050979738382727494965656 62 27 73 31 18 84 45 5用堆中最后一用堆中最后一个元素替代根个元素替代根76765050979738382727494965656 6

47、2 27 73 31 14 45 576765050272738389797494965656 62 27 73 31 14 45 576765050272738384949979765656 62 27 73 31 14 45 57676979750504949383865656 62 23 31 14 45 5 输出堆顶元素之后，以堆中输出堆顶元素之后，以堆中最后一个元素替代最后一个元素替代堆堆顶元素；然后将顶元素；然后将根结点根结点值与值与左左、右子树的根结点右子树的根结点值进值进行比较，并与其中行比较，并与其中小小者进行交换；重复上述操作，直者进行交换；重复上述操作，直至叶子结点，将得

48、到新的堆，称这个从堆顶至叶子的至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为调整过程为“筛选筛选”。进行进行筛选筛选继续继续筛选筛选输出输出堆顶堆顶第 49 页10.4 10.4 选择排序选择排序堆排序堆排序273849657650979727384965765013输出：输出：132749389765765013输出：输出：139749382765765013输出：输出：13 273849502765769713输出：输出：13 276549502738769713输出：输出：13 27 38第 50 页10.4 10.4 选择排序选择排序堆排序堆排序496550273876971

49、3输出：输出：13 27 387665502738499713输出：输出：13 27 38 495065762738499713输出：输出：13 27 38 499765762738495013输出：输出：13 27 38 49 506597762738495013输出：输出：13 27 38 49 509765762738495013输出：输出：13 27 38 49 50 65第 51 页10.4 10.4 选择排序选择排序堆排序堆排序7665972738495013输出：输出：13 27 38 49 50 659765762738495013输出：输出：13 27 38 49 50 65

50、 769765762738495013输出：输出：13 27 38 49 50 65 76 97第 52 页10.4 10.4 选择排序选择排序堆排序堆排序 从一个无序序列建堆的过程是一个反复从一个无序序列建堆的过程是一个反复“筛选筛选”的过程。的过程。 若将此序列看成是一个完全二叉树，则最若将此序列看成是一个完全二叉树，则最后一个非终端结点是第后一个非终端结点是第 n/2n/2个元素，由此个元素，由此筛选只需从第筛选只需从第 n/2n/2个元素开始。个元素开始。时间复杂度时间复杂度：最坏的情况最坏的情况O（nlog2n）接近于平均情况。接近于平均情况。不稳定不稳定的排序。的排序。第 53 页

51、10.5 10.5 归并排序归并排序l归并的思想：归并的思想： 将两个或两个以上的有序表将两个或两个以上的有序表合并合并成一个新成一个新的有序表。的有序表。l2-2-路归并排序的核心思想路归并排序的核心思想：设初始序列含有设初始序列含有n n个记录，则可看成个记录，则可看成 n n 个有序的子序列，每个子序列长度为个有序的子序列，每个子序列长度为1 1。两两合并两两合并，得到，得到 n/2n/2 个长度为个长度为 2 2 或或1 1的有序子序列的有序子序列。再两两合并，再两两合并，如此重复，直至得到如此重复，直至得到一个长度为一个长度为 n n 的有序序列为止的有序序列为止。第 54 页10.

52、5 10.5 归并排序归并排序例：例：初始关键字：初始关键字： 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 97第 55 页10.6 10.6 基数排序基数排序l基数排序思想：基数排序思想：借助借助多关键字排序多关键字排序的方法对的方法对单逻辑关键字单逻辑关键字排排序。序。l设设n个记录的序列个记录的序列R1, R2, . Rn，且每个记，且每个记录录Ri都包含都包含d位关键字（位关键字（ k1, k2,

53、kd）。对）。对此序列排序，保证任意此序列排序，保证任意Ri Rj满足下列关系满足下列关系： R( k1, k2, kd)i R( k1, k2, kd)jl基数排序分类：基数排序分类：最高位优先（最高位优先（MSD）最低位优先（最低位优先（LSD）第 56 页10.6 10.6 基数排序基数排序例：对例：对52张扑克牌排序张扑克牌排序 l排序方法排序方法l先按花色分类，再按面值分类先按花色分类，再按面值分类l先按面值分类，再按花色分类先按面值分类，再按花色分类第 57 页10.6 10.6 基数排序基数排序l最高位优先最高位优先按花色（最高位）分堆按花色（最高位）分堆梅花：梅花：13 张张方

54、块：方块：13 张张红桃：红桃：13 张张黑桃：黑桃：13 张张 每一堆按面值从小到大排列每一堆按面值从小到大排列 第 58 页10.6 10.6 基数排序基数排序l最低位优先最低位优先分配（按面值）分配（按面值） 收集（按面值有序）收集（按面值有序）2：4张，张，3：4张，张，4：4张张 A：4张张第 59 页10.6 10.6 基数排序基数排序再分配（按花色）再分配（按花色） 再收集（按花色有序，同花色按面值有序）再收集（按花色有序，同花色按面值有序） 梅花：梅花：13张，张， 方块：方块：13张，张， 红桃：红桃：13张，张， 黑桃：黑桃：13张张第 60 页10.6 10.6 基数排序基数排序Initial list：46 91 85 15 92 35