第 10 章 排序

1、教学内容教学内容1、插入排序（直接插入排序、折半插入排序、插入排序（直接插入排序、折半插入排序、 希尔排序）；希尔排序）； 2、交换排序（起泡排序、快速排序）；、交换排序（起泡排序、快速排序）； 3、选择排序（直接选择排序、堆排序）；、选择排序（直接选择排序、堆排序）； 4、归并排序；、归并排序； 5、基数排序；、基数排序； 排序：排序：将数据元素的一个任意序列，重新排列成一个将数据元素的一个任意序列，重新排列成一个的序列。的序列。 10.1 概述概述 例：将关键字序列：例：将关键字序列：52, 49, 80, 36, 14, 58, 61, 23 调整为：调整为：14, 23, 36, 49

2、, 52, 58, 61 , 80 一般情况下，假设含一般情况下，假设含 n 个记录的序列为个记录的序列为 R1, R2, , Rn ， 其相应的关键字序列为其相应的关键字序列为 K1, K2, , Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这这些关键字相互之间可以进行比较，即在它们之间存在着这 样一个关系样一个关系 ： Kp1Kp2KpnKp1 Kp2 Kp3 Kp4 Kp5 Kp6 Kp7 Kp8 按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1, Rp2, , Rpn 的操作称作的操作称作。Rp1, Rp2, Rp3, Rp4, Rp5, R

3、p6, Rp7, Rp8 若若 Ki 为记录为记录 Ri 的的关键字，则排序关键字，则排序。 若若 Ki 为记录为记录 Ri 的的关键字，则排序关键字，则排序可以可以（因为（因为 会有相同的关键字）。会有相同的关键字）。 设设 Ki = Kj (1in, 1jn, ij )，且在排序前的序列中，且在排序前的序列中 Ri 领先于领先于 Rj（即（即 i j ）。若在排序后的序列中）。若在排序后的序列中 Ri 仍领先于仍领先于 Rj，则，则 称所用的称所用的；反之，则称所用的；反之，则称所用的。 例：例：设排序前的关键字序列为：设排序前的关键字序列为：52, 49, 80, 36, 14, 58,

4、 , 23 若排序后的关键字序列为：若排序后的关键字序列为：14, 23, 36, , 49, 52, 58, 80， 则则。 若排序后的关键字序列为：若排序后的关键字序列为：14, 23, , 36, 49, 52, 58, 80， 则则。 内部排序和外部排序内部排序和外部排序 若若整个排序过程不需要访问外存整个排序过程不需要访问外存便能完成，则称此类排序问便能完成，则称此类排序问 题题为内部排序；为内部排序； 反之，若参加排序的记录数量很大，整个序列的排序过程反之，若参加排序的记录数量很大，整个序列的排序过程不不可能在内存中完成可能在内存中完成，则称此类排序问题，则称此类排序问题为外部排序

5、为外部排序。 内部排序的方法内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列的过程。内部排序的过程是一个逐步扩大记录的有序序列的过程。 有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区经过一趟排序经过一趟排序 排序方法分类：排序方法分类： 1)、插入排序：、插入排序：直接插入排序、折半插入排序、希尔排序直接插入排序、折半插入排序、希尔排序 2)、交换排序：、交换排序：冒泡排序、快速排序冒泡排序、快速排序 3)、选择排序：、选择排序：简单选择排序、堆排序简单选择排序、堆排序 4)、归并排序：、归并排序：2-路归并排序路归并排序 5)、基数

6、排序、基数排序 基于不同的基于不同的“扩大扩大” 有序序列长度的方法，内部排序有序序列长度的方法，内部排序 方法大致可分下列几种类型：方法大致可分下列几种类型： 将无序子序列中的一将无序子序列中的一 个或几个记录个或几个记录“”到到有有 序序列中，从而增加记录序序列中，从而增加记录 的有序子序列的长度。的有序子序列的长度。 通过通过“”无序序列中的记录从而无序序列中的记录从而 得到其中得到其中关键字最小关键字最小或或最大最大的记录，并的记录，并 将它将它加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。 从记录的无序子序列中从记录

7、的无序子序列中“” 关键字最小关键字最小或或最大最大的记录，并将它的记录，并将它 加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。 通过通过“”两个两个 或两个以上的记录有或两个以上的记录有 序子序列，逐步增加序子序列，逐步增加 记录有序序列的长度。记录有序序列的长度。 基数排序是一种基于多基数排序是一种基于多 关键字排序的思想，将单关关键字排序的思想，将单关 键字按基数分成键字按基数分成 “多关键字多关键字” 进行排序的方法。进行排序的方法。 排序过程的基本操作：排序过程的基本操作：（1 1）比较：必要的；）比较：必要的；（2

8、 2）移动：可以避免；）移动：可以避免；待排序记录的存储方式：待排序记录的存储方式：（1 1）顺序存储：移动不可避免）顺序存储：移动不可避免（2 2）静态链表（表排序）：不移动记录，只修改指针；）静态链表（表排序）：不移动记录，只修改指针；（3 3）顺序存储，另设地址向量（地址排序）：不移动记录，只）顺序存储，另设地址向量（地址排序）：不移动记录，只 改变地址的值；改变地址的值；10.2 插入排序插入排序 有序序列有序序列 R1 . i -1 Ri无序序列无序序列 Ri . n一趟直接插入排序的基本思想：一趟直接插入排序的基本思想： 有序序列有序序列 R1 . i无序序列无序序列 Ri +1

9、. 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； 10.2.1 直接插入排序直接插入排序 初始状态初始状态4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 38

10、49659776132749 i =5 384965769713274976i =6 384965769713274913i =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟趟 排序排序 1 趟趟 排序排序 2 趟趟 排序排序 void InsertSort ( SqList &L ) / 对顺序表对顺序表 L 作直接插入排序。作直接插入排序。 for ( i = 2; i = L.length; + i ) if (L.ri.key L.ri -1.key) / InsertSort 排序过程

11、：排序过程：先将序列中第先将序列中第 1 个记录看成是一个有序子序列，个记录看成是一个有序子序列， 然后从第然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。个记录开始，逐个进行插入，直至整个序列有序。 在在 R1. i-1中查找中查找 Ri 的插入位置的插入位置; 对于在查找过程中找到的那些关键字对于在查找过程中找到的那些关键字 不小于不小于 Ri.key 的记录，在查找的同的记录，在查找的同 时实现记录向后移动；时实现记录向后移动； L.r0 = L.ri; / 复制为监视哨复制为监视哨 L.ri = L.ri -1; for ( j = i - 2; L.r0.key L.r j

12、 .key; - - j ) L.r j + 1 = L.r j ; / 记录后移记录后移 比较次数和移动次数均比较次数和移动次数均为：为： 112 nni2)1)(2(2 nnini2)1)(4()1(2 nnini42nT(n)=O(n) 算法评价算法评价 时间复杂度：时间复杂度： 比较次数：比较次数： 移动次数：移动次数：0 最好的情况：最好的情况：待排序记录按关键字从小到大排列（正序）待排序记录按关键字从小到大排列（正序） 比较次数：比较次数： 移动次数：移动次数： 最坏的情况：最坏的情况：待排序记录按关键字从大到小排列（逆序）待排序记录按关键字从大到小排列（逆序） 一般情况：一般情况

13、：待排序记录是随机的，取平均值。待排序记录是随机的，取平均值。 空间复杂度：空间复杂度：S(n)=O(1) 直接插入排序是稳定排序直接插入排序是稳定排序 5 4 3 2 1 10.2.2 其他插入排序其他插入排序 1、折半插入排序：、折半插入排序：用折半查找方法确定插入位置的排序。用折半查找方法确定插入位置的排序。 void BInsertSort ( SqList &L ) ( i = 2; i = L.length; + i ) L.r0 = L.ri; low = 1; high = i -1; while (low = high +1; -j ) L.rj +1 = L.rj;

14、 / 记录后移记录后移 L.rhigh+1 = L.r0; / 插入插入 / / BInsertSorti =1 (30) 13 70 85 39 42 6 20 i =7 6 (6 13 30 39 42 70 85 ) 20 i =8 20 (6 13 30 39 42 70 85 ) 20 lhmmi =8 20 (6 13 30 39 42 70 85 ) 20 lhi =8 20 (6 13 30 39 42 70 85 ) 20 lhi =8 20 (6 13 20 30 39 42 70 85 ) i =8 20 (6 13 30 39 42 70 85 ) 20 lhmT(n)

15、=O(n) 时间复杂度：时间复杂度： 空间复杂度：空间复杂度：S(n)=O(1) 折半插入排序是稳定排序折半插入排序是稳定排序 仅减少了比较次数，仅减少了比较次数， 移动次数不变。移动次数不变。 直到直到lowhigh时，由折半查找得到的插时，由折半查找得到的插入位置为入位置为low或或high+1。第二趟希尔排序第二趟希尔排序 第三趟分组，设第三趟分组，设 d3 = 1 10.2.3 希尔排序（缩小增量排序）希尔排序（缩小增量排序） 基本思想：基本思想：对待排序列先作对待排序列先作“宏观宏观”调整，再作调整，再作“微观微观”调调整。整。 排序过程：排序过程：先取一个正整数先取一个正整数 d1

16、 n，把所有相隔把所有相隔 d1 的记录放的记录放 在一组内，组内进行直接插入排序；然后取在一组内，组内进行直接插入排序；然后取 d2 d1，重复上述分重复上述分 组和排序操作；直至组和排序操作；直至 di = 1，即所有记录放进一个组中排序为止。即所有记录放进一个组中排序为止。 其中其中 称为称为。 例：例： 49 38 65 97 76 13 27 49 55 04 第一趟希尔排序第一趟希尔排序 13 27 49 55 04 49 38 65 97 76 13 04 49 38 27 49 55 65 97 76第三趟希尔排序第三趟希尔排序 第一趟分组，设第一趟分组，设 d1 = 5 49

17、 38 65 97 76 13 27 49 55 04 13 27 49 55 04 49 38 65 97 76 第二趟分组，设第二趟分组，设 d2 = 3 04 13 27 38 49 49 55 65 76 973.应用举例 设有一组关键字序列为（49，38，65，97，76，13，27，49，55，04），进行shell排序，增量序列为5，3，1，写出每趟的排序结果。012345678910初始关键字49 38 65 97 76 13 27 49 55 04第第1趟（趟（d1=5）4913134938272738654949659755559776040476第第2趟（趟（d2=3）1

18、355387613385576270465042765494997494997第第3趟（趟（d3=1）1304 49 3827 4955 6597 760413 2738 49 4955 6576 97希尔排序特点：希尔排序特点： 分组不是简单的分组不是简单的“逐段分割逐段分割”，而是将相隔某个增量的记录组成，而是将相隔某个增量的记录组成 一个子序列。一个子序列。 增量序列取法增量序列取法 希尔最早提出的选法是希尔最早提出的选法是 d1 = n/2 ，di +1 = di /2 。 克努特克努特 (Knuth) 提出的选法是提出的选法是 di +1 = (di-1) /3 。 还有其他不同的取

19、法。还有其他不同的取法。 如何选择增量序列以产生最好的排序效果，至今仍没有从数学如何选择增量序列以产生最好的排序效果，至今仍没有从数学 上得到解决。上得到解决。 1)、没有除、没有除 1 以外的公因子；以外的公因子； 2)、最后一个增量值必须为、最后一个增量值必须为 1。 希尔排序可提高排序速度希尔排序可提高排序速度 1)、记录跳跃式前移，在进行最后一趟排序时，已基本有序。记录跳跃式前移，在进行最后一趟排序时，已基本有序。 2)、分组后、分组后 n 值减小，值减小，n2 更小，而更小，而 T(n)=O(n2)，所以所以 T(n) 从从 总体上看是减小了。总体上看是减小了。 3、重复直到重复直到

20、 “” 或或“” 为止。为止。 10.3 交换排序交换排序 1、冒泡排序、冒泡排序 v 排序过程排序过程 1、比较第一个记录与第二个、比较第一个记录与第二个 记录，若记录，若关键字关键字为逆序为逆序则交换；然则交换；然 后比较第二个记录与第三个记录；后比较第二个记录与第三个记录； 依次类推，直至第依次类推，直至第 n -1 个记录和第个记录和第 n 个记录比较为止个记录比较为止，结果关键字最大的记录被安，结果关键字最大的记录被安 置在最后一个记录上。置在最后一个记录上。 2、对前对前 n-1 个记录进行第二个记录进行第二 趟冒泡排序，结果使关键字次大的趟冒泡排序，结果使关键字次大的 记录被安置

21、在第记录被安置在第 n-1 个记录位置。个记录位置。 初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 第第 一一 趟趟 排排 序序 49 38 49 97 76 97 97 13 97 97 27 97 97 49 38 49 65 76 13 27 49 38 49 65 13 27 49 第第 二二 趟趟 排排 序序 38 49 13 27 49 第第 三三 趟趟 排排 序序 38 13 27 49 第第 四四 趟趟 排排 序序 13 27 38第第 五五 趟趟 排排 序序 第第 六六 趟趟 排排 序序 for ( j = 1; j ; j + +) if (

22、 r j +1 r j ) r j r j + 1 ; for ( j = 1; j ; j + +) if ( r j +1 1; i - - ) ; while ( i 1) / while i = n ; i = k ; Void BubbleSort(SqList &L) 初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 k = j ; /交换的位置交换的位置（k k以后若正序就不用交换）以后若正序就不用交换） k = 1 ; 一般情况下每经过一般情况下每经过 一趟一趟“起泡起泡”，“ i 减减 1”， 但并不是每趟都如此。但并不是每趟都如此。 例：

23、例： 5 2 3 1 9 7 8 2 3 1 5 7 8 9 2 1 3 5 7 8 9i = 6 i = 2 1 2 3 5 7 8 9i = 1 v 算法评价算法评价 时间复杂度：时间复杂度： 最好情况（正序）最好情况（正序） 比较次数：比较次数：n -1 移动次数：移动次数：0 T(n) = O(n) 最坏情况（逆序）最坏情况（逆序） 比较次数：比较次数： 移动次数：移动次数： )(21)1(22nnini )(23)1(322nnini 空间复杂度：空间复杂度：S(n) = O(1) 稳定性：稳定排序稳定性：稳定排序 一般取第一个记录一般取第一个记录 基本思想：基本思想：一个记录，以它

24、的关键字作为一个记录，以它的关键字作为“”，凡，凡键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录 均移至枢轴之后。均移至枢轴之后。 2、一趟快速排序（一次划分）、一趟快速排序（一次划分） lowhigh设设 Rs=52 为枢轴。为枢轴。 例：例： 52 49 80 36 14 58 61 97 23 75 st 附设两个指针附设两个指针 low 和和 high，从，从 high 所指位置起向前搜索找所指位置起向前搜索找 到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然

25、后 从从 low 所指位置起向后搜索找到第一个关键字大于枢轴的关键字所指位置起向后搜索找到第一个关键字大于枢轴的关键字 的记录与枢轴记录交换，重复这两步直至的记录与枢轴记录交换，重复这两步直至 low = high 为止。为止。 high23 low low80highhighhighhigh14lowlowint Partition (SqList &L, int low, int high) pivotkey = L.rlow.key; /用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 while (low high) while (low = pivotkey) - -

26、 high; / 将比枢轴小的记录交换到低端将比枢轴小的记录交换到低端 while (low high & L.rlow.key = pivotkey) + + low; / 将比枢轴大的记录交换到高端将比枢轴大的记录交换到高端 /while return low; / 返回枢轴所在位置返回枢轴所在位置 / PartitionL.r0=L.rlow; L.rlow=L.rhigh; =L.r0; L.r0=L.rlow; =L.rhigh; L.rhigh=L.r0; L.r0=L.rlow;L.rlow=L.r0; / 将比枢轴小的记录移到低端将比枢轴小的记录移到低端 / 将比枢轴大

27、的记录移到高端将比枢轴大的记录移到高端 快速排序过程快速排序过程 3、快速排序、快速排序 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，之后分别对分割，之后分别对分割 所得两个子序列所得两个子序列“递归递归”进行一趟快速排序。进行一趟快速排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列 (1)无序子序列无序子序列 (2) 枢轴枢轴 一次划分一次划分 分别进行一趟快速排序分别进行一趟快速排序 有有 序序 的的 记记 录录 序序 列列 void QSort (SqList &L, int low, int high ) / 对顺序表对顺序表

28、 L 中的子序列中的子序列 L.rlow.high 进行快速排序进行快速排序 if (low high) / 长度大于长度大于1 / QSortQSort(L, low, pivotloc-1) ; / 对低子序列递归排序，对低子序列递归排序，pivotloc 是枢轴位置是枢轴位置 QSort(L, pivotloc+1, high); / 对高子序列递归排序对高子序列递归排序 第一次调用函数第一次调用函数 Qsort 时，待排序记录序列的上、时，待排序记录序列的上、 下界分别为下界分别为 1 和和 L.length。 void QuickSort( SqList & L) / 对顺序

29、表进行快速排序对顺序表进行快速排序 QSort(L, 1, L.length); / QuickSort 4、快速排序的时间分析快速排序的时间分析 假设一次划分所得枢轴位置假设一次划分所得枢轴位置 i=k，则对，则对 n 个记录进行快排所个记录进行快排所 需时间：需时间：其中其中 Tpass(n) 为对为对 n 个记录进行一次划分所需时间。个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的，则若待排序列中记录的关键字是随机分布的，则 k 取取 1 至至 n 中中 任一值的可能性相同。任一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k) nkav

30、gavgavgknTkTnCnnT1)()1(1)( 由此可得快速排序所需时间的平均值为：由此可得快速排序所需时间的平均值为：设设 Tavg(1)b，则可得结果：，则可得结果： )1ln()1)(22()( nncbnTavg快速排序的时间复杂度为快速排序的时间复杂度为 O(n log n)。 一次划分所需时间和表长成正比一次划分所需时间和表长成正比 到目前为止快速排序是到目前为止快速排序是的一种排序方法。的一种排序方法。 在最坏的情况，即待排序序列已经按关键字在最坏的情况，即待排序序列已经按关键字“正序正序”排列排列的情况下，每次划分只得到一个比上一次少一个对象的子序列。的情况下，每次划分只

31、得到一个比上一次少一个对象的子序列。这样，必须经过这样，必须经过 n-1 n-1 趟才能把所有对象定位，而且第趟才能把所有对象定位，而且第 i i 趟需趟需要经过要经过 n-i n-i 次关键码比较才能找到第次关键码比较才能找到第 i i 个对象的安放位置，个对象的安放位置，快速排序将蜕化为起泡排序，其时间复杂度为快速排序将蜕化为起泡排序，其时间复杂度为 O(n2)O(n2)。 所以所以快速排序适用于原始记录排列杂乱无章的情况。快速排序适用于原始记录排列杂乱无章的情况。 每趟排序后，枢轴都偏向子序列的一端，占用附加存储每趟排序后，枢轴都偏向子序列的一端，占用附加存储( (即即栈栈) )将达到将

32、达到o(n)o(n)。 用第一个对象作为基准对象用第一个对象作为基准对象 用居中排序码对象作为基准对象用居中排序码对象作为基准对象n改进方法：为避免出现蜕化情况，需在进行一次划分之前，改进方法：为避免出现蜕化情况，需在进行一次划分之前，进行进行“预预 处理处理”，即：先对，即：先对 R(s).key, R(t).key R(s).key, R(t).key 和和 R(s+t)/2.keyR(s+t)/2.key，进行相互比较，然后取关键字的大小为中，进行相互比较，然后取关键字的大小为中间的记录为枢轴记录。间的记录为枢轴记录。 快速排序是一种快速排序是一种的排序，在递归调用时需要占据的排序，在递

33、归调用时需要占据 一定一定的存储空间用来保存每一层递归调用时的必要信息。的存储空间用来保存每一层递归调用时的必要信息。对于对于 n n 较大的平均情况而言，快速排序是较大的平均情况而言，快速排序是“快速快速”的，但是当的，但是当 n n 很小时，这种排序方法往往比其它简单排序方法还要慢。很小时，这种排序方法往往比其它简单排序方法还要慢。10.4 选择排序选择排序 10.4.1 简单选择排序简单选择排序 排序过程：排序过程： 首先通过首先通过 n 1 次关键字比较，从次关键字比较，从 n 个记录中找出个记录中找出关键字最小关键字最小 的记录，将它与第一个记录交换。的记录，将它与第一个记录交换。

34、再通过再通过 n 2 次比较，从剩余的次比较，从剩余的 n 1 个记录中找出关键字次小个记录中找出关键字次小 的记录，将它与第二个记录交换。的记录，将它与第二个记录交换。 重复上述操作，共进行重复上述操作，共进行 n 1 趟排序后，排序结束。趟排序后，排序结束。 假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列 R1.i-1 无序序列无序序列 Ri.n 第第 i 趟趟简单选择排序简单选择排序从中选出从中选出关键字最小的记录关键字最小的记录有序序列有序序列R1.i无序序列无序序列 Ri+1.nj+ if (L.rj.key L.rk.key) k =

35、j; j = i+1; for (i = 1; i L.length; + i) 例：例： 初始：初始： 49 38 65 97 76 13 27 jjjjjjki =1 13 49 一趟：一趟： 13 38 65 97 76 49 27 i =2 二趟：二趟： 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 27 38 49 65 76 97 排序结束：六趟：排序结束：六趟： 13 27 38 49 65 76

36、97 kk = i; kfor ( j = i+1; j = n; j+) if (L.rj.key L.rk.key) k = j; if (i != k) L.riL.rk; / 与第与第 i 个记录交换个记录交换i =6 void SelectSort (SqList &L) / 对顺序表对顺序表 L 作简单选择排序。作简单选择排序。 / SelectSort i =3 i =4 i =5 比较次数比较次数 n - 1 n - 2 n - 6 比较次数：比较次数： 2)1()(11 nninni移动次数：移动次数： 正序：最小值为正序：最小值为 0； 最大值为最大值为 3(n-1

37、) 。 前前 n 1 个为正序，第个为正序，第 n 个记录的关键字最小。个记录的关键字最小。 锦标赛排序锦标赛排序 前提：前提：若乙胜丙，甲胜乙，则认为甲必能胜丙。若乙胜丙，甲胜乙，则认为甲必能胜丙。 Zhao Cha Liu Bao Diao Yang Xue Wang Cha Bao Diao Wang Bao Diao Bao Liu Cha Cha Bao Cha Zhao Liu Diao Diao Yang Wang Liu Liu Zhao Wang Wang Xue Xue Xue Xue Yang Yang Yang Zhao 选出冠军的比较次数为选出冠军的比较次数为 22+

38、21+20 = 23 -1 = n-1。 选出亚军的比较次数为选出亚军的比较次数为 3，即，即 log2n 次。次。 其后的其后的 n 2 个人的名次均如此产生，所以对于个人的名次均如此产生，所以对于 n 个参赛选手个参赛选手 来说，即对来说，即对 n 个记录进行锦标赛排序，总的关键字比较次数至多个记录进行锦标赛排序，总的关键字比较次数至多 为为 (n 1)log2n n 1，故，故。 此法除排序结果所需的此法除排序结果所需的 n 个单元外，尚需个单元外，尚需 n-1 个辅助单元。个辅助单元。 10.4.2 树形选择排序树形选择排序 思想：思想：首先对首先对 n 个记录的关键字进行两两比较，然

39、后在其个记录的关键字进行两两比较，然后在其 中中 n/2 个较小者之间再进行两两比较，直到选出最小关键字个较小者之间再进行两两比较，直到选出最小关键字 的记录为止。可以用一棵有的记录为止。可以用一棵有 n 个叶子结点的完全二叉树表示。个叶子结点的完全二叉树表示。 38 13 13 13 38 65 27 13 38 49 65 97 76 27 49 13 76 27 27 27 49 49 38 38 49 49 49 49 65 49 49 76 65 65 97 97 76 97 76 97 13 27 38 49 49 65 76 97 时间复杂度：时间复杂度：由于含有由于含有 n 个

40、叶子结点的完全二叉树的深度个叶子结点的完全二叉树的深度 为为 log2n +1，则在树形选择排序中，除了最小关键字外，每，则在树形选择排序中，除了最小关键字外，每 选择一个次小关键字仅需进行选择一个次小关键字仅需进行 log2n 次比较，故时间复杂度次比较，故时间复杂度 为为 O(nlogn)。 缺点：缺点： 1、与、与“ ”的比较多余；的比较多余； 2、辅助空间使用多。、辅助空间使用多。 10.4.3 堆排序堆排序 堆的定义：堆的定义：n 个元素的序列个元素的序列 (k1, k2, , kn)，当且仅当满足下当且仅当满足下 列关系时，称之为列关系时，称之为。 或或(i = 1, 2, , n

41、/2 )ki k2i ki k2i+1 ki k2iki k2i+1 小顶堆小顶堆 大顶堆大顶堆 小根堆小根堆 正正 堆堆 大根堆大根堆 逆逆 堆堆 例例1： (96, 83, 27, 38, 11, 09) 例例2： (13, 38, 27, 49, 76, 65, 49, 97) 9627091138831327384965764997 可将堆序列看成完全二叉树，则：可将堆序列看成完全二叉树，则： k2i 是是 ki 的左孩子；的左孩子； k2i+1 是是 ki 的右孩子。的右孩子。 所有非终端结点的值均不大（小）于其左右孩子结点的值。所有非终端结点的值均不大（小）于其左右孩子结点的值。

42、堆顶元素必为序列中堆顶元素必为序列中 n 个元素的最小值或最大值个元素的最小值或最大值。 堆排序：堆排序： 堆排序需解决的两个问题：堆排序需解决的两个问题： ，得到关键字最小（大）的，得到关键字最小（大）的 记录；记录；，则可得到，则可得到 n 个元素的次小值；如此个元素的次小值；如此 重复执行，重复执行，直到堆中只有一个记录为止，每个记录出堆直到堆中只有一个记录为止，每个记录出堆 的顺序就是一个有序序列的顺序就是一个有序序列，这个过程叫，这个过程叫堆排序堆排序。 堆堆堆堆筛选筛选 所谓所谓“筛选筛选”指的是，对一棵左指的是，对一棵左/右子树均为堆的完全二叉右子树均为堆的完全二叉 树，树，“调

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

44、979765762765493849971376 对深度为对深度为 k 的堆，的堆，“筛选筛选” 所需进行的关键字比较的次数所需进行的关键字比较的次数 至多为至多为 2(k-1)。 第一个问题解决方法：第一个问题解决方法： 从无序序列的第从无序序列的第 n/2 个元素（即无序序列对应的完全二叉个元素（即无序序列对应的完全二叉 树的最后一个内部结点）起，至第一个元素止，进行反复筛选。树的最后一个内部结点）起，至第一个元素止，进行反复筛选。 建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。例例: : 排序之前的关键字序列为：排序之前的关键字序列为： 132738494965

45、7697堆排序过程496538497613279749386597761327494997136513491397274997279749279797389738656549764949499797496565977697767697关键字初始序列关键字初始序列void HeapAdjust (HeadType &H, int s, int m) / 已知已知 H.rs.m中记录的关键字除中记录的关键字除 H.rs 之外均满足堆的特征，本函数自之外均满足堆的特征，本函数自 / 上而下调整上而下调整 H.rs 的关键字，使的关键字，使 H.rs.m 成为一个大顶堆成为一个大顶堆 / He

46、apAdjust rc = H.rs; / 暂存暂存 H.rs for ( j=2*s; j= Rj.key ) break; / 再作再作“根根”和和“子树根子树根”之间的比较，若之间的比较，若“=”成立，则说明成立，则说明 / 已找到已找到 rc 的插入位置的插入位置 s ，不需要继续往下调整，不需要继续往下调整 Rs = Rj; s = j; / 否则记录上移，尚需继续往下调整否则记录上移，尚需继续往下调整 if ( j m & H.rj.key 0; - - i ) HeapAdjust (H.r, i, H.length); / 建大顶堆建大顶堆 for ( i = H.le

47、ngth; i 1; - - i ) H.r1H.ri; / 将堆顶记录和当前未经排序子序列将堆顶记录和当前未经排序子序列 / H.r1.i中最后一个记录相互交换中最后一个记录相互交换 HeapAdjust (H.r, 1, i -1); / 对对 H.r1 进行筛选进行筛选 定义堆类型为：定义堆类型为： typedef SqList HeapType; / 堆用顺序表表示堆用顺序表表示 堆排序的时间复杂度和空间复杂度：堆排序的时间复杂度和空间复杂度： 1. 对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的次数至所需进行的关键字比较的次数至多多 为为 2(k-1)；3. 调

48、整调整“堆顶堆顶” n-1 次，总共进行的关键字比较的次数不超过次，总共进行的关键字比较的次数不超过 2 ( log2(n-1) + log2(n-2) + +log22) 2n( log2n ) 因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为 O(nlogn)，与简单选择排序，与简单选择排序 O(n2) 相比时间效率提高了很多。相比时间效率提高了很多。 2. 对对 n 个关键字，建成深度为个关键字，建成深度为 h(= log2n +1) 的堆，的堆，所需进行所需进行的关键字比较的次数至多的关键字比较的次数至多 4n； 空间复杂度：空间复杂度：S(n) = O(1) 堆排序是一种堆排序是

49、一种且且的排序方法。的排序方法。 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 4

50、9 65 76 97 看成是看成是 n 个有序的子个有序的子 序列（长度为序列（长度为 1），）， 然后两两归并。然后两两归并。 得到得到 n/2 个长度为个长度为 2 或或 1 的有序子序列。的有序子序列。 空间复杂度为：空间复杂度为：O(n)。 时间复杂度为：时间复杂度为：O(nlog2n)。 稳定。稳定。 每趟归并的时间复每趟归并的时间复杂度为杂度为O(n)，共需进，共需进行行 log2n 趟。趟。二路归并排序的效率分析二路归并排序的效率分析 二路归并排序的时间复杂度等于归并趟数与每一趟时间复二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。杂度的乘积。时间复杂度为时间复杂度

51、为O(nlogO(nlog2 2n)n)。 利用二路归并排序时，需要利用与待排序数组相同的辅助利用二路归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的数组作临时单元，故该排序方法的空间复杂度为空间复杂度为O(n)O(n)，比前面，比前面介绍的其它排序方法占用的空间大。介绍的其它排序方法占用的空间大。 由于二路归并排序中，每两个有序表合并成一个有序表时，由于二路归并排序中，每两个有序表合并成一个有序表时，若分别在两个有序表中出现有相同排序码，则会使前一个有序若分别在两个有序表中出现有相同排序码，则会使前一个有序表中相同排序码先复制，后一有序表中相同排序码后复制，从表中相同

52、排序码先复制，后一有序表中相同排序码后复制，从而保持它们的相对次序不会改变。所以，二路归并排序是一种而保持它们的相对次序不会改变。所以，二路归并排序是一种稳定的稳定的排序方法。排序方法。 归并的思想主要用于外部排序。归并的思想主要用于外部排序。 外部排序可分两步，待排序记录分批读入内存，用某种外部排序可分两步，待排序记录分批读入内存，用某种方法在内存排序，组成有序的子文件，再按某种策略存入方法在内存排序，组成有序的子文件，再按某种策略存入外存。子文件多路归并，成为较长有序子文件，再记入外存。子文件多路归并，成为较长有序子文件，再记入外存，如此反复，直到整个待排序文件有序。外存，如此反复，直到整

53、个待排序文件有序。 外部排序可使用外存、磁带、磁盘，最初形成有序子文件外部排序可使用外存、磁带、磁盘，最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略，归并长取决于内存所能提供排序区大小和最初排序策略，归并路数取决于所能提供排序的外部设备数。路数取决于所能提供排序的外部设备数。10.6 基数排序基数排序 基数排序是一种借助基数排序是一种借助“”的思想来实现的思想来实现“单关键单关键 字排序字排序”的内部排序算法。的内部排序算法。 10.6.1 多关键字的排序多关键字的排序 例：例：将右表所示的学生将右表所示的学生 成绩单按数学成绩成绩单按数学成绩 的等级由高到低排的等级由高到低排

54、 序，数学成绩相同序，数学成绩相同 的学生再按英语成的学生再按英语成 绩的高低等级排序。绩的高低等级排序。 学号学号数学数学英语英语其它其它 101 B C 102 A B 103 C D 104 B B 105 A A 106 D B 107 E A 108 C B105 A A 102 A B 104 B B 101 B C 108 C B 103 C D 106 D B 107 E A特点：特点：每个记录最终的每个记录最终的 位置由两个关键位置由两个关键 字字 k1 k2 决定。决定。 第二关键字第二关键字 K2 第一关键字第一关键字 K1 我们将它称之为我们将它称之为，即，即多关键字多

55、关键字 排序是按照复合关键字排序是按照复合关键字 的大小排序的大小排序。 例：例：扑克牌中扑克牌中 52 张牌，可按张牌，可按和和分成两个分成两个“关键字关键字”，其，其 大小关系为：花色：大小关系为：花色： 面值：面值： 2345678910JQKA 若对扑克牌按花色、面值进行升序排序，得到如下序列：若对扑克牌按花色、面值进行升序排序，得到如下序列： 2, 3, ., A, 2, 3, ., A, 2, 3, ., A, 2, 3, ., A 即两张牌，若花色不同，不论面值怎样，花色低的那张牌小即两张牌，若花色不同，不论面值怎样，花色低的那张牌小 于花色高的，只有在同花色情况下，大小关系才由

56、面值的大小确于花色高的，只有在同花色情况下，大小关系才由面值的大小确 定。这也是定。这也是按照复合关键字的大小排序，按照复合关键字的大小排序，即：即：。 多关键字排序的方法：多关键字排序的方法： n 个记录的序列个记录的序列 R1, R2, , Rn 对关键字对关键字 (Ki0, Ki1, , Kid-1) 有序是指：对于序列中任意两个记录有序是指：对于序列中任意两个记录 Ri 和和 Rj (1i jn) 都满都满 足下列（词典）有序关系：足下列（词典）有序关系：(Ki0, Ki1, , Kid-1) (Kj0, Kj1, , Kjd-1) 其中：其中： 被称为被称为 ， 被称为被称为。 多关

57、键字排序按照从最主位关键字到最次位关键字或从最次多关键字排序按照从最主位关键字到最次位关键字或从最次 位关键字到最主位关键字的顺序逐次排序，分两种方法：位关键字到最主位关键字的顺序逐次排序，分两种方法： 最高位优先法，简称最高位优先法，简称 MSD 法：法：先按先按 k 0 排序分组，同一组中排序分组，同一组中 记录，关键字记录，关键字 k 0 相等，再对各组按相等，再对各组按 k 1 排序分成子组，之后，对排序分成子组，之后，对 后面的关键字继续这样的排序分组，直到按最次位关键字后面的关键字继续这样的排序分组，直到按最次位关键字 k d 对对 各子组排序后，再将各组连接起来，便得到一个有序序

58、列。各子组排序后，再将各组连接起来，便得到一个有序序列。 3,1,201,2,152,3,181,2,15 无序序列无序序列 3,2,30 最低位优先法，简称最低位优先法，简称 LSD 法：法：先从先从 k d-1 开始排序，再对开始排序，再对 k d-2 进行排序，依次重复，直到对进行排序，依次重复，直到对 k 0 排序后便得到一个有序序列。排序后便得到一个有序序列。 例：例：学生记录含三个关键字：学生记录含三个关键字： 系别系别、和和班内的序列号班内的序列号， 其中以系别为最主位关键字。其中以系别为最主位关键字。对对K2排序排序 对对K1排序排序 对对K0排序排序 3,1,202,1,20

59、2,3,183,1,202,1,203,2,302,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下：的排序过程如下： 对对 Ki (0id -2) 进行排序时，只能用进行排序时，只能用 稳定稳定的排序方法。的排序方法。例例：先将学生记录按：先将学生记录按英语英语等级由高到低分成等级由高到低分成 A、B、C、D、E 五五 个组：个组： 关键字类别关键字类别 ABCDE各组成员各组成员 AAABBCCDEABBDBCB学号学号数学数学英语英语其它其它 101 B C 102 A B 103 C D 104 B B 10

60、5 A A 106 D B 107 E A 108 C B 然后按从左向右，从上向下的顺序将然后按从左向右，从上向下的顺序将 它们收集起来得到关键字序列：它们收集起来得到关键字序列： AA，EA，AB，BB，DB，CB，BC，CD 用用 LSD 法进行的排序，在一定的条件下（即对法进行的排序，在一定的条件下（即对 Ki 的不同值的不同值 Ki+1 均取相同值），可通过若干次均取相同值），可通过若干次“分配分配”和和“收集收集”来实现。来实现。 再按数学成绩由高到低分成再按数学成绩由高到低分成 A、B、C、D、E 五个组：五个组： 关键字类别关键字类别 ABCDE各组成员各组成员 AAABBCCDEABBDBCB关键字类别关键字类别 ABCDE各组成员各组成员 AA