第八章排序PPT课件VIP

1、8.1 概述 8.2 合并排序 8.3 用比较法进行排序的时间下界 8.4 选择排序和堆排序8.5 插入排序和希尔排序8.6 快速排序8.7 基数排序第八章 排序概述概述 排序：内部排序：全部记录都可以同时调入内存进行的排序。排序：内部排序：全部记录都可以同时调入内存进行的排序。 外部排序外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。：文件中的记录太大，无法全部将其同时调入内存进行的排序。 定义定义：设有记录序列：设有记录序列： R1、R2 . Rn 其相应的关键字序列为：其相应的关键字序列为： K1、K2 . Kn ; 若存在一种确定的关系若存在一种确定的关系： Kx =

2、Ky = = Kz 则将记录序列则将记录序列 R1、R2 . Rn 排成按该关键字有序的序列：排成按该关键字有序的序列： Rx、Ry . Rz 的操作，称之为排序的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系或任意的关系。关系是任意的，如通常经常使用的小于、大于等关系或任意的关系。 稳定与不稳定稳定与不稳定：若记录序列中的任意两个记录：若记录序列中的任意两个记录 Rx、Ry 的关键字的关键字 Kx = Ky ；如果在；如果在 排序之前和排序之后，它们的相对位置保持不变排序之前和排序之后，它们的相对位置保持不变，则这种排序方法，则这种排序方法 是稳定的，否则是不稳定的是稳定

3、的，否则是不稳定的。3合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个排序表。顺序比较两者的相应元素，小者移将下面两个已排序的顺序表合并成一个排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk4合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。

4、e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk75合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序

5、比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk76合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一

6、表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7137合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7138合并排序合并排序 M

7、erging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713499合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序

8、的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134910合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应

9、元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496511合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一

10、表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496512合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965761

11、3合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657614合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序

12、表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965768015合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺

13、序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965768016合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止

14、。移入另一表中，反复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576809717合并排序合并排序 Merging sort: 思想来源于合并两个已排序的顺序表。思想来源于合并两个已排序的顺序表。e.g: 将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。移入另一表中，反复如此，直至其中任一表都移入另一表为止。 1 2 3 4 549136597A76

15、7 8 976780B31 2 3 4 5 6 7 8 9 C491365977678037 实现很简单，实现很简单，A、B、C 三表分别设置指针三表分别设置指针p、q、k 初值为初值为 1,6,1 ，比较，比较 p、q 指针指向指针指向 的结点，将小者放入的结点，将小者放入 C 表表,相应指针加相应指针加1。如。如A、B表中一张表为空，则将另一张表的结点表中一张表为空，则将另一张表的结点 全部移入全部移入C表。表。 比较次数和移动次数和两张表的结点总数成正比。比较次数和移动次数和两张表的结点总数成正比。18合并排序合并排序 合并二张有序表合并二张有序表：template void Merge

16、( EType a , EType aa , int n, int low, int up, int m ) int p=low, q=low+m, r; / 合并alow至alow+m-1和alow+m至aup。 for (r=1; r=n; r+) aar = ar; r = low; / 数组 a 的初始指针。while ( p low + m & q up + 1 ) while ( p low + m & aap = aaq ) ar+ = aap+;if ( p low + m ) while ( q up + 1 & aaq aap ) ar+ = aaq

17、+; if ( p = = low + m )for ( ; q =up; q+ ) ar+ = aaq; if ( q = = up + 1 )for ( ; p n(表长表长)，那么，那么 up = n；即取二者小者作第二张表的终止地址。；即取二者小者作第二张表的终止地址。 2、当、当up + m = n 时，意味着下一次被合并的两张表中的第一张表的末地址大于等于最大下标时，意味着下一次被合并的两张表中的第一张表的末地址大于等于最大下标 n ，这说，这说 明被合并的第二张表不存在，意味着明被合并的第二张表不存在，意味着本趟结束。要过渡到下一趟合并本趟结束。要过渡到下一趟合并；m应增大一倍。

18、应增大一倍。 3、 当子表长当子表长 m = n 时，合并排序结束。时，合并排序结束。ij20合并排序合并排序 合并排序法：合并排序法：template void MergeSort( EType a , int n ) / 待排序的表为数组a, a0 不用，待排序的数组元素为 a1, a2, , an。 int low=1; / 被合并的二个表中的第一个表的首地址。 int up; / 被合并的二个表中的第二个表的末地址。 int m=1; / 被合并的二个表中的第一个表的表长。初始时为1。 EType * aa; aa = new ETypen+1 ; / 用于合并的辅助数组，aa0仍然不

19、用。 while ( m n ) up = min(low + 2 * m 1, n);Merge(a, aa, n, low, up,m); / 将alow 至 alow+m-1 和alow+m至aup进行合并。if ( up+m n ) low = up + 1; / up+m n 意味着被合并的另一张表不存在。else m *= 2; low = 1; / 过渡到下一次合并，子表长度增大一倍。 delete aa; 21合并排序合并排序时间复杂性分析：时间复杂性分析： 合并的过渡趟数：合并的过渡趟数： logn 每趟进行时，调用每趟进行时，调用 merge 过程过程 n / ( 2 *

20、len ) 次，次， 每次比较和数据移动都是每次比较和数据移动都是 (2 * len ) 次，因此每趟代价为次，因此每趟代价为 O( n )。 总的代价为总的代价为 T(n) = O ( nlogn ) 在递归的情况下：可通过下式求出时间复杂性的级别。在递归的情况下：可通过下式求出时间复杂性的级别。2 for n=2 T(n) = T( n/2 ) + T( n/2 ) + n else解上述的递归式，可知时间复杂性为解上述的递归式，可知时间复杂性为 T(n) = O ( nlogn )。当。当 n 是是 2 的整数幂时简化为的整数幂时简化为T(n) = O ( nlogn )22用比较法进行

21、排序的时间下界用比较法进行排序的时间下界 判定树模型：如下图所示，说明对判定树模型：如下图所示，说明对 a,b,c 进行分类的一颗判定树。当判断条件成立时，进行分类的一颗判定树。当判断条件成立时， 转向左，否则转向右。转向左，否则转向右。 比较法分类的下界：比较法分类的下界： ( n logn )a ba b ca cb ca cb ca c bc a bc b ab a cb c anoyesyesyesyesyesnononono 注意：树高代表比较的代价。因此只要知道了树高和结点数注意：树高代表比较的代价。因此只要知道了树高和结点数 n 的关系，就可以求出的关系，就可以求出 用比较法进行

22、排序时的时间代价。另外，用比较法进行排序时的时间代价。另外，n 个结点的分类序列，其叶子结点个结点的分类序列，其叶子结点 共有共有 n! 片。片。23用比较法进行排序的时间下界用比较法进行排序的时间下界 定理：高为定理：高为 H 的二叉树，最多具有的二叉树，最多具有 2(H-1)片叶子。片叶子。 证明：证明：H 1 时，最多时，最多 1 片叶子，定理成立。片叶子，定理成立。 H 2 时，最多时，最多 2 片叶子，定理成立。片叶子，定理成立。 设设 H n-1 时公式成立。则当时公式成立。则当 H n 时，时， 根结点有具有叶子结点最多的高为根结点有具有叶子结点最多的高为 n-1 的左的左 右子

23、树；叶子结点总数为：右子树；叶子结点总数为： 2(n-2)2 2(n-1) 公式成立。公式成立。 推论：具有推论：具有 N 片叶子的二叉树，高最少为片叶子的二叉树，高最少为 logN + 1。 或比较次数最少为或比较次数最少为 logN 。 比较法分类的下界：比较法分类的下界： ( n logn )高为高为 n-1具有具有2(n-2)片叶子片叶子高为高为 n-1具有具有2(n-2)片叶子片叶子H = 1H = 2H = n 定理：把定理：把 n 个不同的结点进行分类的任一判定树的高个不同的结点进行分类的任一判定树的高 度至少为度至少为 log(n!) + 1 。 证明：证明： n 个元素的排序

24、序列的总数共有个元素的排序序列的总数共有 n! 种，因此在种，因此在 相应的判定树上至少有相应的判定树上至少有 n! 片叶子。根据上述定片叶子。根据上述定 理，可证。理，可证。 推论：用比较的方法对推论：用比较的方法对 n 个元素的进行分类。在最坏个元素的进行分类。在最坏 情况下至少需要情况下至少需要 cnlogn 次比较，次比较， 或或 (nlogn)24用比较法进行排序的时间下界用比较法进行排序的时间下界 比较法分类的下界：比较法分类的下界： ( n logn )X轴轴Y轴轴求求 y=logx 的积分的示意图的积分的示意图211234y=logn11n-1nj=1nn1 log n! =

25、logj logx dx不难求出不难求出上述积分的值为：上述积分的值为：nlogn-nloge+loge nlogn-nloge。注意到：。注意到：loge = 1.44 。 25简单简单选择排序选择排序 执行过程：执行过程：1225492516834521254925168212549258162125492516218rprp1649252521816492525218rp1621252549816212525498rp1621252549816212525498rp16212525498626template void SelectSort( EType a , int n ) int

26、p, q; / p、q 为数组为数组a的指针。的指针。a1, a2 , ,an为待排序序列。为待排序序列。a0不用。不用。 int r; / 暂时保存具有最小键值的结点地址。暂时保存具有最小键值的结点地址。 for ( p = 1; p n; p+) r = p; for ( q = p+1; q = n; q+) if ( aq ar ) r = q; / 记住本趟挑选的最小结点的地址。记住本趟挑选的最小结点的地址。 if ( r !=p ) a0 = ap; ap = ar; ar = a0; / 若最小结点不是若最小结点不是ap, 则交换。则交换。 简单简单选择排序选择排序27有 n个元

27、素的数组的比较次数 (n-1) + (n-2) + . . . + 2 + 1 = O(n2)交换次数 3 (n-1) 因循环执行 (n-1) 次，最坏情况下每次都交换。 总的时间复杂性代价为：O(n2)简单简单选择排序选择排序树型选择排序树型选择排序 改进：简单选择排序没有利用上次选择的结果，是造成速度慢的主要原因。如果能够改进：简单选择排序没有利用上次选择的结果，是造成速度慢的主要原因。如果能够 加以改进，将会提高排序的速度。加以改进，将会提高排序的速度。381376276549974938651327133813选出最小者选出最小者 13树型选择排序树型选择排序 改进：简单选择排序没有利

28、用上次选择的结果，是造成速度慢的重要原因。如果，能改进：简单选择排序没有利用上次选择的结果，是造成速度慢的重要原因。如果，能 够加以改进，将会提高排序的速度。由于有更好的排序方法，所以本方法用的够加以改进，将会提高排序的速度。由于有更好的排序方法，所以本方法用的 很少。很少。381376276549974938651327133813选出次最小者，应利用上次比选出次最小者，应利用上次比较的结果。从被较的结果。从被 13 打败的结打败的结点点 27、76、38 中加以确定。中加以确定。堆排序堆排序 堆的定义：堆的定义：n 个元素的序列个元素的序列 k1， k2 ， ， kn ，当且仅当满足以下关

29、系时，称，当且仅当满足以下关系时，称 之为堆：之为堆： ki = k2i ki = k2i+1 ( i = 1,2, , n/2 ) 且分别称之为且分别称之为最小化堆最小化堆和和最大化堆最大化堆。 e.g: 序列序列 96,83,27,11,9 最大化堆最大化堆 12，36，24，85，47，30，53，91 最小化堆最小化堆 或或969118327 2 3 14512478591362453306273 184531 70 60403012 8最大堆的最大元素最大堆的最大元素 1032 1 2 3 4 5 6 7 7060124030 810 70 1 60 240 4 30 512 3 8

30、 6 root10 7数组表示的堆数组表示的堆 33建建堆堆 30 1 60 240 4 70 5 8 3 12 610 7 root 1 2 3 4 5 6 7 3060 840701210叶子结点，符合堆的的叶子结点，符合堆的的定义定义。不合堆的定义，需调整不合堆的定义，需调整。即建立小堆。建立的。即建立小堆。建立的第一个小堆的堆顶的下第一个小堆的堆顶的下标为标为 n/2数组数组 h34建建堆堆 30 1 60 240 4 70 58 3 12 610 7 root 1 2 3 4 5 6 7 306012 4070 810叶子结点，符合堆的的定义叶子结点，符合堆的的定义。不合堆的定义，需

31、调整。即建立大不合堆的定义，需调整。即建立大堆堆。建立的第一个小堆的堆顶的下。建立的第一个小堆的堆顶的下标为标为 n/2数组数组 h35建建堆堆 30 1 60 240 4 70 512 3 8 610 7 root 1 2 3 4 5 6 7 306012 4070 810不合堆的定义，需调整。不合堆的定义，需调整。建立以建立以 h 2 为堆顶的正为堆顶的正确的最大化小堆确的最大化小堆。数组数组 h36建建堆堆 30 1 70 240 4 60 512 3 8 610 7 root 1 2 3 4 5 6 7 307012 4060 810不合堆的定义，需调整。不合堆的定义，需调整。建立以建

32、立以 h 2 为堆顶的正为堆顶的正确的最大化小堆确的最大化小堆。数组数组 h37建建堆堆 30 1 70 240 4 60 512 3 8 610 7 root 1 2 3 4 5 6 7 307012 4060 810不合堆的定义，需调整。不合堆的定义，需调整。建立以建立以 h 1 为堆顶的正为堆顶的正确的最大化堆确的最大化堆。数组数组 h38建建堆堆 70 1 30 240 4 60 512 3 8 610 7 root 1 2 3 4 5 6 7 703012 4060 810不合堆的定义，需调整。不合堆的定义，需调整。建立以建立以 h 1 为堆顶的正为堆顶的正确的最大化堆确的最大化堆。

33、数组数组 h39建建堆堆 70 1 60 240 4 30 512 3 8 610 7 root 1 2 3 4 5 6 7 706012 4030 810不合堆的定义，需调整。不合堆的定义，需调整。建立以建立以 h 1 为堆顶的正为堆顶的正确的最大化堆确的最大化堆。数组数组 h40建建堆堆时间复杂性的分析：时间复杂性的分析： 时间耗费的代价：建堆的时间耗费时间耗费的代价：建堆的时间耗费 排序的时间耗费排序的时间耗费 建堆的时间耗费：设树根处于第建堆的时间耗费：设树根处于第 1 层，该堆共有层，该堆共有 h 层。建堆从第层。建堆从第 h-1 层开始进行。只层开始进行。只 要知道了每一层的结点数

34、（建的小堆的个数），和每建一个小堆所要知道了每一层的结点数（建的小堆的个数），和每建一个小堆所 需的比较次数，就可以求得建堆的时间耗费。需的比较次数，就可以求得建堆的时间耗费。 建的小堆的性质：第建的小堆的性质：第 i 层上小堆的个数层上小堆的个数 第第 i 层上结点的个数层上结点的个数 最多最多 2i-1 第第 i 层上小堆的高度层上小堆的高度 h-i+1 建第建第 i 层上每个小堆最多所需的比较次数层上每个小堆最多所需的比较次数 2（h-i）次）次 建堆的时间耗费：建堆的时间耗费： T(n) = 2i-1(h-i)2 = 2i(h-i) = 2h-jj = 2h j/2j注意：即使是注意：

35、即使是 高度为高度为 h 的完全的二叉树的完全的二叉树，满足以下式子：，满足以下式子： 2h1 = n = 2h-1 故：故： 2h = 2n 又：又： j/2j 2 所以所以：建堆的时间复杂性为：建堆的时间复杂性为 4n=O(n) 级级 i=h-1i=h-1j=1 h-1 1 1j=1 h-1j=11030406012708623 1745123=h41建建堆堆 建立最大化堆建立最大化堆template void MaxHeap : SiftDown( int j ) / heap1, ,heapn为存储堆的数组。为存储堆的数组。heap0不用。不用。 int MaxSon; / 用于记录大

36、儿子的下标地址。用于记录大儿子的下标地址。 heap0 = heapj; for ( ; j*2 heap MaxSon ) MaxSon+; if ( heapMaxSon heap0 ) heapj = heapMaxSon; else break;heap j = heap0; template void MaxHeap : BuildHeap( ) for ( int j= CurrentSize/2; j 0; j- ) SiftDown(j); 30 170 240 4 60 512 3 8 610 7j42 堆堆排序排序7060124030 810values 70 1 60 2

37、40 4 30 512 3 8 6 root10 7 1 2 3 4 5 6 7 43 堆堆排序排序values1060124030 870不需再考虑！不需再考虑！ 1 2 3 4 5 6 7 10 1 60 240 4 30 512 3 8 6 root70 744 堆堆排序排序values6040121030 870 1 2 3 4 5 6 7 60 1 40 210 4 30 512 3 8 6 root70 745 堆堆排序排序6040121030 870 1 2 3 4 5 6 7 60 1 40 210 4 30 512 3 8 6 root70 746 堆堆排序排序values

38、8401210306070不需再考虑！不需再考虑！ 1 2 3 4 5 6 7 8 1 40 210 4 30 512 3 60 6 root70 747 values40301210 86070堆堆排序排序 1 2 3 4 5 6 7 40 1 30 210 4 8 512 3 60 6 root70 748 values40301210 86070堆堆排序排序 1 2 3 4 5 6 7 40 1 30 210 4 8 512 3 60 6 root70 749 values堆堆排序排序 8301210406070不需再考虑！不需再考虑！ 1 2 3 4 5 6 7 8 1 30 210

39、4 40 512 3 60 6 root70 750 values301012 8406070堆堆排序排序 1 2 3 4 5 6 7 30 1 10 2 8 4 40 512 3 60 6 root70 751 values301012 8406070堆堆排序排序 1 2 3 4 5 6 7 30 1 10 2 8 4 40 512 3 60 6 root70 752 values堆堆排序排序 8101230406070不需再考虑！不需再考虑！ 1 2 3 4 5 6 7 8 1 10 230 4 40 512 3 60 6 root70 753 values1210 830406070堆堆

40、排序排序 1 2 3 4 5 6 7 12 1 10 230 4 40 58 3 60 6 root70 754 values1210 830406070堆堆排序排序 1 2 3 4 5 6 7 12 1 10 230 4 40 58 3 60 6 root70 755 values堆堆排序排序不需再考虑！不需再考虑！ 8101230406070 1 2 3 4 5 6 7 8 1 10 230 4 40 512 3 60 6 root70 756 values10 81230406070堆堆排序排序 1 2 3 4 5 6 7 10 1 8 230 4 40 512 3 60 6 root7

41、0 757 values10 81230406070堆堆排序排序 1 2 3 4 5 6 7 30 510 7 10 1 8 230 4 40 512 3 60 6 root70 758 数组数组 h堆堆排序排序 8101230406070不需再考虑！不需再考虑！ 1 2 3 4 5 6 7 10 230 4 40 512 3 60 6 root70 7 8 159 堆堆排序排序template void SiftDown( EType a , int j, int Size ) / a1, ,aSize为存储堆的数组。为存储堆的数组。a0不用。注意：本函数用于排序。不用。注意：本函数用于排序

42、。Size 为堆的最为堆的最 / 大下标，大下标，j 为当前要建立的最大化堆的堆顶结点的地址。为当前要建立的最大化堆的堆顶结点的地址。 int MaxSon; / 用于记录大儿子的下标地址。用于记录大儿子的下标地址。 a0 = aj; for ( ; j*2 aMaxSon ) MaxSon+;if ( aMaxSon a0 ) aj = aMaxSon; else break; aj = a0;template void MaxHeapSort( EType a , int Size ) for ( int j = Size/2; j 0; j- - ) / a1, a2 , ,aSize为

43、待排序的数组。为待排序的数组。a0不用。不用。 SiftDown(a, j, Size); / 将将 a1, a2 , ,aSize建成最大化堆。建成最大化堆。 for ( int k = Size; k 1; k- - ) Swap( a1, ak); / 交换交换 a1 和和 ak , 最大元素放在最大元素放在 ak。 SiftDown(a, 1, k-1); / 将将 a1, a2 , ,ak-1调整为最大化堆。调整为最大化堆。 60堆堆排序排序 时间复杂性的分析：建堆的时间耗费时间复杂性的分析：建堆的时间耗费 排序的时间耗费排序的时间耗费 排序的时间耗费：排序的时间耗费：结点个数结点个

44、数高度高度 比较次数最多比较次数最多 j=2log2 + 1= 2 log2j=3log3 + 1= 2 log3j=4log4 + 1= 2 log4j=n-1log(n-1) + 1= 2 log(n-1) 所以：所以：T(n) = 2( log2 + log3 + . + log(n-1) ) = 2log(n-1)! T(n) = O ( nlogn ) 时间复杂性的分析：时间复杂性的分析：1030406012708623 1745123=h61堆堆排序排序 堆排序的时间代价分析推导：堆排序的时间代价分析推导： O ( n logn )X轴轴Y轴轴求求 y=logx 的积分的示意图的积

45、分的示意图21234y=logx11n-1nj=2n-1n1 log(n-1)! = logj logx dx不难求出不难求出上述积分的值为：上述积分的值为：nlogn-nloge+loge nlogn-nloge。注意到：。注意到：loge = 1.44 。 62堆堆排序排序 最大化堆（最小化堆亦可）用以表示优先队列最大化堆（最小化堆亦可）用以表示优先队列 常用的基本操作：常用的基本操作： 1、 Inset：将具有给定优先数的新结点插入优先队列：将具有给定优先数的新结点插入优先队列 ，代价，代价 O(logn) 若分二步：若分二步：1、先找出新结点的插入位置，代价为、先找出新结点的插入位置，

46、代价为 O(logn) 2、通过移动，将新结点插入，代价、通过移动，将新结点插入，代价 O(logn) 总代价仍未改进，仍是总代价仍未改进，仍是 O(logn) 2、DeleteMax：删除具有最大优先数的结点，：删除具有最大优先数的结点， 代价代价 O(logn) 3、 Delete：删除任一结点，：删除任一结点， 代价代价 O(logn) 4、 IncreasePriority(DecreasePriority): 增大（或减少）结点的优先数增大（或减少）结点的优先数 代价代价 O(logn) 5、Merge： 合并二个优先队列为一个合并二个优先队列为一个 无法在无法在 O(logn) 内

47、做到内做到 改进：使用最左树改进：使用最左树9659518377 2 36 7899111415494110112921121379316171层层2层层3层层4层层5层层63最左树最左树最左树：是一棵二叉树。结点的最左树：是一棵二叉树。结点的 s 值值。设二叉树的外部结点。设二叉树的外部结点(空的儿子结点空的儿子结点)的的 s 值为值为0，其他，其他 每个结点的每个结点的 s 值为左、右儿子结点的值为左、右儿子结点的s 值的小者加值的小者加 1 。如果每个结点的左儿子的。如果每个结点的左儿子的 s 值不小于右儿子的值不小于右儿子的s值，而且父结点之值大于等于值，而且

48、父结点之值大于等于(或小于等于或小于等于)儿子结点儿子结点(如果存在的如果存在的 话话)之值的话，那末这棵二叉树被称之为最左树。之值的话，那末这棵二叉树被称之为最左树。 3111112211329015322010751211013182311112256816122464最左树最左树 定理：设定理：设x 是最左树的内部结点，那么是最左树的内部结点，那么1. 以以 x 为根的子树的结点的数目至少为为根的子树的结点的数目至少为 2S(x) 1。2. 如果子树如果子树 x 有有m 个结点，个结点，S(x) 至多为至多为 log2(m+1)。3. 通过最右路径，从通过最右路径，从 x 到达外部结点的

49、路径长度为到达外部结点的路径长度为 S(x)。证明：证明：1. 设设x 所在结点的层次为所在结点的层次为 0，儿子结点的层次为，儿子结点的层次为1，以下依次加，以下依次加1，。 则根据定义，则根据定义，x 的后代中，如果的后代中，如果 s 值为值为1，则该后代的儿子中必有一个为，则该后代的儿子中必有一个为 空。换句话说，由空。换句话说，由 x 到达最到达最“近近”的且的且s 值为值为1 的后代之前，的后代之前，x 及其后代及其后代的的 儿子数儿子数2都为两个。因此，直至第都为两个。因此，直至第 S(x ) 1 层没有外部结点，第层没有外部结点，第 S(x ) 层层 才有外部结点。所以，结点总数

50、至少为：才有外部结点。所以，结点总数至少为：1+2+2 S(x ) - 1 = 2S(x) -1个结个结 点。注意，从第点。注意，从第S(x )层起，开始出现外部结点，同时还可能有内部结层起，开始出现外部结点，同时还可能有内部结 点。点。 2由由 1. 可知，结点数至少为可知，结点数至少为2s(x) -1 = m 时，时，x的的s值为值为S(x)。S(x)的值至多的值至多 为为log(m +1)。 3. 根据定义，每个内部结点的右儿子的根据定义，每个内部结点的右儿子的 s 值小于等于左儿子的值小于等于左儿子的 s 值，故值，故 通过最右路径，从通过最右路径，从x到达外部结点的路径长度为到达外部

51、结点的路径长度为S(x)。很明显，任意结。很明显，任意结 点的点的s值为本结点到它的度为值为本结点到它的度为0或或1的子孙结点的最短路径长度加的子孙结点的最短路径长度加1。 2311112256816122431111122113290153220107512110131865最左树最左树23111122568161224311111221132901532201075121101318 合并最左树示例合并最左树示例 1121075112122472 合并中涉及到的最左树合并中涉及到的最左树66最左树最左树 合并过程合并过程 1172117212105a、b、1172c、12124121051

52、17212124121051172232225681612124121051172d、f、e、 67最左树最左树 最后得到的最左树最后得到的最左树 14111112239015322012110830231125681612124111051172g、 68a0 用作哨兵。共执行用作哨兵。共执行 5 遍操作。遍操作。每遍操作：先将元素复制内容放入每遍操作：先将元素复制内容放入a0，再将本元素同已排序的序列，从尾，再将本元素同已排序的序列，从尾开始进行比较。在已排序的序列中寻找自己的位置，进行插入。或者寻找不开始进行比较。在已排序的序列中寻找自己的位置，进行插入。或者寻找不到，则一直进行到哨兵为

53、止到，则一直进行到哨兵为止。意味着本元素最小，应该放在。意味着本元素最小，应该放在 a1 。每一遍，排序的序列将增加一个元素。如果序列中有每一遍，排序的序列将增加一个元素。如果序列中有 n 个元素个元素，那么最多，那么最多进行进行n 遍即可。遍即可。直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序其排序。结果仍保存在下标为。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。01236241061234569直接直接插入排序插入排序e.g: 36、24、10、

54、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序其排序。结果仍保存在下标为。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。0123624106123453624j70直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序其排序。结果仍保存在下标为。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。0123624106123453624j71直接直接插入排序插入排序e.g: 3

55、6、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序其排序。结果仍保存在下标为。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。0123624106123453624j2472直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。0123624106123453610j2473直接直接插入

56、排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。0123624106123453610j2474直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。012362410612345361

57、0j2475直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。0123624106123453610j241076直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。0123

58、6241061234536246j1077直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。01236241061234536246j1078直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元

59、素之中。的元素之中。01236241061234536246j1079直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。01236241061234536246j10680直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保

60、存在下标为 1 至至 5 的元素之中。的元素之中。0123624106345362412j1061281直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。0123624106345362412j1061282直接直接插入排序插入排序e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其