成果数据结构ds

1、第10章 排序Sort主讲：顾为兵主讲：顾为兵作者声明：课件仅限本班教学参考用，不对外发布作者声明：课件仅限本班教学参考用，不对外发布第十章 排序(Sort)目录10.1 10.1 排序概述排序概述10.2 10.2 插入排序插入排序10.3 10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序排序排序10.1 排序概述操作对象：同类型数据元素的集合。同类型数据元素的集合。操作目标：将无序的数据元素序列排列成按关将无序的数据元素序列排列成按关键字值有序的序列。键字值有序的序列。排序概述排序概述稳定排序与非稳定排序

2、： 设：设：Ri.key=Rj.key 假设假设排序前排序前Ri的位置排列在的位置排列在Rj之前之前； 经排序后若经排序后若Ri的位置仍然排列在的位置仍然排列在Rj之前，则是之前，则是稳定稳定排序算法排序算法； 若不能保证这一点则是若不能保证这一点则是非稳定排序算法非稳定排序算法。排序概述排序概述内部排序与外部排序： 内部排序-待排序的记录全部存放在内存待排序的记录全部存放在内存; ; 外部排序-一部分放在内存，一部分在外存。一部分放在内存，一部分在外存。 排序过程中存在着内、外存的数据排序过程中存在着内、外存的数据 交换。交换。排序概述排序概述排序的基本动作： 比较比较 移动移动排序性能的评

3、价： 对比较次数和移动次数的评估对比较次数和移动次数的评估, 空间消耗的评估空间消耗的评估先进排序算法：时间复杂度时间复杂度-O(nlogn)一般排序算法时间复杂度时间复杂度-O(n2)排序概述排序概述排序方法： 插入排序 直接插入排序、希尔排序 交换排序 冒泡排序、快速排序 选择排序 简单选择排序、堆排序 归并排序 归并排序 基数排序 LSD算法排序概述排序概述第十章 排序(Sort)目录10.1 排序概述10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序10.6 基数排序排序排序10.2 插入排序10.2.1 直接插入排序10.2.2 折半插入排序10.2.3 二路插

4、入排序10.2.4 表插入排序10.2.5 希尔排序插入排序插入排序直接插入排序算法思想：c 排序区间排序区间R1.n；c 在排序的过程中，整个排序区间被分为两个子区间：在排序的过程中，整个排序区间被分为两个子区间： 有序区有序区R1.i-1和无序区和无序区Ri.n；c 共进行共进行n1趟排序，每趟排序都是把无序区的趟排序，每趟排序都是把无序区的第第一条记录一条记录Ri插到有序区的合适位置上。插到有序区的合适位置上。RR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1nRR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1n插入排序插入排序 直接插入排序直接插入排

5、序初态：有序区为R158 15 46 45 90 08 32R12345670监视哨15 58R46 45 90 08 3212345670第一趟，第一趟，i2；1558，15赋给监视哨；赋给监视哨；有序区中所有大于有序区中所有大于15的记录右移一位的记录右移一位将将15放入腾出的空位放入腾出的空位i=258 15 46 45 90 08 32R12345670初态：第一趟后：4658 15 46 45 90 08 32R12345670R45 90 08 3212345670第二趟，第二趟，i3；4658，46赋给监视哨；赋给监视哨；有序区中所有大于有序区中所有大于46的记录右移一位的记录右

6、移一位将将46放入腾出的空位放入腾出的空位i=3155815 58 46 45 90 08 32R12345670初态：第一趟后：第二趟后：45R90 08 3212345670第三趟，第三趟，i4；4558，没有移动发生；，没有移动发生；i=558 15 46 45 90 08 32R1234567015 58 46 45 90 08 32R1234567015 46 58 45 90 08 32R1234567015 45 46 58 90 08 32R123456709015 45 46 5808 32R12345670初态：第一趟后：第二趟后：第三趟后：第四趟后：第五趟，第五趟，i6；

7、i=608 15 4546 58 90R321234567058 15 46 45 90 08 32R1234567015 58 46 45 90 08 32R1234567015 46 58 45 90 08 32R1234567015 45 46 58 90 08 32R1234567015 45 46 58 90 08 32R12345670初态：第一趟后：第二趟后：第三趟后：第四趟后：第五趟后：第六趟，第六趟，i7；i=732 45 46 58R901234567008 1558 15 46 45 90 08 32R1234567015 58 46 45 90 08 32R123456

8、7015 46 58 45 90 08 32R1234567015 45 46 58 90 08 32R1234567015 45 46 58 90 08 32R1234567008 15 45 46 58 90 32R12345670初态：第一趟后：第二趟后：第三趟后：第四趟后：第五趟后：第六趟后：存储结构-以顺序存储结构为例#define MAXSIZE 200typedef struct /结点类型结点类型KeyTypekey;InfoTypeotherinfo;RecordType;typedef struct /排序表类型排序表类型RecordTypeRMAXSIZE+1;intle

9、ngth;SqList; keyotherinfoR length插入排序插入排序 直接插入排序直接插入排序直接插入排序算法：void InsertSort( SqList &L) /对顺序表对顺序表L作直接插入排序作直接插入排序 for(i=2; i=L.length; i+) if(L.Ri.keyL.R0.key; j-) L.Rj+1=L.Rj; /将大于哨兵的记录右移将大于哨兵的记录右移 L.Rj+1=L.R0; /将将Ri放入有序区的正确位置放入有序区的正确位置 /end if R0R0有两个作用：有两个作用：(1)(1)保留保留RiRi的副本的副本(2)(2)监视哨，监视

10、监视哨，监视j j是否越界是否越界插入排序插入排序 直接插入排序直接插入排序直接插入排序性能分析：最好的情况：表的初态恰好是正序排列 比较次数： 移动次数：Mmin0最坏的情况：表的初态恰好是逆序排列 比较次数： 移动次数：11min2nCni2) 1)(2(max2nniCni2) 1)(4() 1(max2nniMni插入排序插入排序 直接插入排序直接插入排序等概条件下平均情况：2minmax CCC平均比较次数：2minmaxMMM平均移动次数：时间复杂度：O(n2)直接插入排序是一种稳定的排序方法插入排序插入排序 直接插入排序直接插入排序10.2 插入排序10.2.1 直接插入排序10

11、.2.2 折半插入排序10.2.3 二路插入排序10.2.4 表插入排序10.2.5 希尔排序插入排序插入排序c 考察直接插入排序，当 n较小时 序列基本有序时 直接插入排序的效果比较好。c 希尔排序正是基于这两点对直接插入排序 做改进的。c 希尔排序又称为缩小增量排序插入排序插入排序 希尔排序希尔排序希尔排序算法思想：c 在排序的过程中，整个排序区间被分为几个子表在排序的过程中，整个排序区间被分为几个子表;c 对每个子表分别进行直接插入排序对每个子表分别进行直接插入排序c 由于由于n2n12+n22+nk2 ( n=n1+n2+nk ) 所以对每个子表排序所耗费的时间之和要小于对整所以对每个

12、子表排序所耗费的时间之和要小于对整个区间排序所耗费的时间个区间排序所耗费的时间c 通过对子表小范围的排序通过对子表小范围的排序,将排序区间调整成基本有将排序区间调整成基本有序的序列序的序列;c 不断减少子表的个数不断减少子表的个数(即扩大子表的长度即扩大子表的长度), 直至子表直至子表的个数为的个数为1, 完成整个排序操作完成整个排序操作.插入排序插入排序 希尔排序希尔排序举例：希尔排序，增量序列取为5,3,1第第1 1趟排序，增量趟排序，增量dkdk5 5R123456708910dk=5:94387625619372648651i插入排序插入排序 希尔排序希尔排序第一趟排序后：第一趟排序后

13、：R123456708910dk=5:49386725164362198756i插入排序插入排序 希尔排序希尔排序R123456708910dk=3:42436219875 6i86317695插入排序插入排序 希尔排序希尔排序第第2 2趟排序，增量趟排序，增量dkdk3 3R123456708910dk=3:242154366798i68137569插入排序插入排序 希尔排序希尔排序第第2 2趟排序后：趟排序后：R123456708910dk=1:215436679 8i插入排序插入排序 希尔排序希尔排序第第3 3趟排序，增量趟排序，增量dkdk1 1R1234567089101234566

14、78 9i第十章 排序(Sort)目录10.1 排序概述10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序10.6 基数排序排序排序交换排序概述8 交换排序的基本思路是：交换排序的基本思路是： 比较两条记录比较两条记录Ri与与Rj(iRj.key-逆序排列，则交换逆序排列，则交换Ri与与Rj的位置的位置8 根据根据Ri与与Rj的取法不同，分为的取法不同，分为冒泡排序冒泡排序和和快速排序快速排序RR1R2 Ri-1Ri+1Rn012i-1ii+1jn-1nRiRj交换排序交换排序10.3 交换排序10.3.1 冒泡排序10.3.2 快速排序 交换排序交换排序 10.3.1

15、冒泡排序( Bubble Sort ) 自下而上自下而上(或上而下或上而下)扫描记录序列，扫描记录序列， 相邻的两条记录相邻的两条记录Ri与与Ri1(或或Ri+1)如果是逆序，如果是逆序， 则交换位置则交换位置交换排序交换排序 冒泡排序冒泡排序87654333452121067585145218765432104567215851123345初态第一趟经过一趟排序，键值最小的记录象气泡一样浮到了最上面。交换排序交换排序 冒泡排序冒泡排序876543210初态4567215851123345第二趟8765432106758514521334512第一趟交换排序交换排序 冒泡排序冒泡排序87654

16、321067514533452112588765432106758455145332112第四趟8765432106751453345211258第三趟交换排序交换排序 冒泡排序冒泡排序注意：在第四趟扫描过程中没有移动发生，表明所有记录已经排序完毕，算法可以提前结束了。冒泡排序算法：void BubbleSort( SqList &L ) /对顺序表对顺序表L L作冒泡排序作冒泡排序 for(i=2; i=L.length; i+) /进行进行n n1 1趟扫描趟扫描 move=False ; /move /move是交换与否的标志是交换与否的标志 for( j=n; j=i; j-

17、- ) if( L.R j L.R j-1 ) L.R j L.R j-1; move=True; /如逆序则交换如逆序则交换 if ( !move ) return; / /如果没有移动发生，则结束如果没有移动发生，则结束 交换排序交换排序 冒泡排序冒泡排序冒泡排序性能分析：最好的情况：表的初态恰好是正序排列，第一趟扫描 没有移动发生 比较次数：Cminn-1 移动次数：Mmin0最坏的情况：表的初态恰好是逆序排列，需要进行n-1 趟排序，每趟都要移动整个区间 比较次数： 移动次数：2) 1-(=) 1+-(=max2=nninCni2) 1-(3=3) 1+-(=max2=nninMni交

18、换排序交换排序 冒泡排序冒泡排序等概条件下平均情况：2minmax CCC平均比较次数：2minmaxMMM平均移动次数：时间复杂度：O(n2)冒泡排序是一种稳定的排序方法交换排序交换排序 冒泡排序冒泡排序10.3 交换排序10.3.1 冒泡排序10.3.2 快速排序 交换排序交换排序 10.3.2 快速排序(Quick Sort) 一种速度很快的排序算法交换排序交换排序 快速排序快速排序 快速排序算法思想快速排序算法思想:c设排序区间为设排序区间为R low . . high R low . . high ；c在排序区间任选一个记录在排序区间任选一个记录RxRx做为基准；做为基准；c经过一趟

19、排序后，将排序区间分为左、右两个子经过一趟排序后，将排序区间分为左、右两个子区间：区间： Rlow.i-1Rlow.i-1 RxRx Ri+1.highRi+1.high使得：使得：Rlow.i-1.keyRlow.i-1.keyRx.keyRx.keyRi+1.high.keyRi+1.high.keyc然后再用相同的方法分别对左、右区间进行排序，然后再用相同的方法分别对左、右区间进行排序，直至每个区间长度都是直至每个区间长度都是1 1为止。为止。交换排序交换排序 快速排序快速排序8765432104567215851123345基准c初态：初态：low=1， high=n；c取区间的第一个

20、元素为基准；取区间的第一个元素为基准；c在区间的两端各设一个指针在区间的两端各设一个指针i和和j，两个指针交替地向中间扫，两个指针交替地向中间扫描；描；c首先，指针首先，指针j向左扫描，当遇到键值小于基准的记录向左扫描，当遇到键值小于基准的记录Rj，就做一次交换就做一次交换RiRj；c然后然后i指针向右扫描，当遇到键值大于基准的记录指针向右扫描，当遇到键值大于基准的记录Ri，就，就做一次交换做一次交换RiRj；c当两个指针相遇时，分区结束。当两个指针相遇时，分区结束。ji8765432104567215851123345ji 第一次分区前第一次分区前: :交换排序交换排序 快速排序快速排序87

21、65432104545581251673321 第一次分区后第一次分区后: :jiji 第二次分区前第二次分区前: :交换排序交换排序 快速排序快速排序8765432106745583345512112 第二次分区后第二次分区后: :ji8765432104545581251673321jiji 第三次分区前第三次分区前: :交换排序交换排序 快速排序快速排序 第三次分区后第三次分区后: :jiji87654321067455833455121128765432106745583345512112快速排序算法：1. 分区算法(P274, 算法10.6a)int Partition( SqLis

22、t &L, int low, int high ) /对排序区间对排序区间L.Rlow.highL.Rlow.high进行一次分区，返回基准位置下标进行一次分区，返回基准位置下标 pivotkey=L.Rlow.key; i=low; j=high; while( ii & L.R j .key=pivotkey) j-; / i/ i指向基准，指向基准，j j向左扫描向左扫描 L.R i L.R j ; / / 交换基准交换基准 while( ij & L.R i .key=pivotkey) i+; / j/ j指向基准，指向基准，i i向右扫描向右扫描 L.R i

23、 L.R j ; / / 交换基准交换基准 return i； /返回基准的位置下标返回基准的位置下标 交换排序交换排序 快速排序快速排序对分区算法还可以改进：对分区算法还可以改进： 基准暂存在基准暂存在L.R0位置上，在分区过程中基位置上，在分区过程中基准不参加移动，只是准不参加移动，只是L.Ri或或L.Rj单向移动。单向移动。当分区结束时，将基准移到正确位置上。当分区结束时，将基准移到正确位置上。交换排序交换排序 快速排序快速排序1. 分区算法的改进(P274, 算法10.6b)int Partition( SqList &L, int low, int high ) / /对排序

24、区间对排序区间L.Rlow.highL.Rlow.high进行一次分区，返回基准位置下标进行一次分区，返回基准位置下标 pivotkey=L.Rlow.key; i=low; j=high; L.R0=L.Rlow; while( ii & L.R j =pivotkey) j-; /i/i指向基准指向基准,j,j向右扫描向右扫描 L.R i = L.R j ; / / 比基准小的记录左移比基准小的记录左移 while( ij & L.R i =pivotkey) i+; / j指向基准，i向左扫描 L.R j = L.R i ; / / 比基准大的记录右移比基准大的记录右移

25、L.R i = L.R0; / /基准到位基准到位 return i； /返回基准的位置下标返回基准的位置下标 交换排序交换排序 快速排序快速排序2. 对Low.high区间的快速排序算法(P276, 算法10.7)void QSort( SqList &L, int low, int high ) /对排序区间对排序区间L.Rlow.highL.Rlow.high进行快速排序进行快速排序 if( low high ) pivotloc=partition( L, low, high ); /进行分区，返回基准下标进行分区，返回基准下标 QSort(L, low, pivotloc-1

26、) ; / / 对左半区进行快速排序对左半区进行快速排序 QSort(L, pivotloc+1, high) ; / / 对右半区进行快速排序对右半区进行快速排序 交换排序交换排序 快速排序快速排序3. 对整个顺序表的快速排序算法(P276, 算法10.8)void QuickSort( SqList &L) / / 对整个顺序表进行快速排序对整个顺序表进行快速排序 Qsort( L, 1, L.length ); 交换排序交换排序 快速排序快速排序快速排序性能分析：最坏的情况：最坏的情况： 表的初态恰好是正序或逆序排列。每次分区时，表的初态恰好是正序或逆序排列。每次分区时，基准都恰

27、好是区间的最大或最小键值，分区的结果是基准都恰好是区间的最大或最小键值，分区的结果是有一个区间为空。有一个区间为空。交换排序交换排序 快速排序快速排序 对于初态是正序或逆序排列的表，需要进行对于初态是正序或逆序排列的表，需要进行n-1n-1趟排序，每趟要进行趟排序，每趟要进行n-in-i次比较次比较: :快速排序退化成冒泡排序，时间复杂度达到快速排序退化成冒泡排序，时间复杂度达到O(nO(n2 2).).2) 1-(=)-(=max1 -1=nninCni最好的情况：最好的情况：每次分区时，基准都恰好是区间的中间每次分区时，基准都恰好是区间的中间 值，分区的结果使得左、右两个区间长度一样，同步

28、地值，分区的结果使得左、右两个区间长度一样，同步地收敛到收敛到1 1。不妨设表长不妨设表长n n2 2k k，用，用C(m)C(m)表示对长度为表示对长度为m m的表进行快速的表进行快速排序所需要的比较次数：排序所需要的比较次数： Cmin=C(n) n+2C(n/2) n+2(n/2+2C(n/22)=2n+22C(n/22) 2n+22(n/22+2C(n/23)=3n+23C(n/23). kn+2kC(n/2k)=nlog2n+nC(1) =O(nlog2n)交换排序交换排序 快速排序快速排序c就平均性能而言，快速排序的时间复杂度是就平均性能而言，快速排序的时间复杂度是O(nlogn)

29、。c快速排序被认为是所有快速排序被认为是所有O(nlogn)级别的排序级别的排序方法中平均性能最好的。方法中平均性能最好的。c快速排序由于是递归实现的，需要消耗运行快速排序由于是递归实现的，需要消耗运行栈的空间栈的空间c快速排序是非稳定的排序方法：快速排序是非稳定的排序方法： 2 2 1 1 2 2 交换排序交换排序 快速排序快速排序第十章 排序(Sort)目录10.1 排序概述10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序排序排序10.4 选择排序10.4.1 简单选择排序10.4.2 堆排序选择排序选择排序简单选择排序算法思想：8 设：排序区间设：排序区间R1.n

30、;8 在排序的过程中，整个排序区间被分为两个子区间：有序在排序的过程中，整个排序区间被分为两个子区间：有序区区R1.i-1和无序区和无序区Ri.n;8 共进行共进行n1趟排序，每趟排序都是选择无序区的最小记录趟排序，每趟排序都是选择无序区的最小记录Rmin；将将Rmin 放置在无序区首元的位置放置在无序区首元的位置(i号下标），号下标），使得无序区长度减使得无序区长度减1，有序区长度增，有序区长度增1。RR1R2 Ri-1RiRi+1RminRn012i-1ii+1n-1n选择排序选择排序 简单选择排序简单选择排序有序区无序区8765432104567215851123345j 第一趟第一趟i

31、=1i选择排序选择排序 简单选择排序简单选择排序此时，有序区为空，无序区为整个待排序区间。此时，有序区为空，无序区为整个待排序区间。最小值最小值12与与45交换交换8765432107367455851213312j 第二趟第二趟i=2i选择排序选择排序 简单选择排序简单选择排序无序区的最小值无序区的最小值21与与33交换交换8765432107367455851332112j 第三趟第三趟i=3i选择排序选择排序 简单选择排序简单选择排序无序区的最小值无序区的最小值33与与58交换交换8765432107367583351452112j 第四趟第四趟i=4i选择排序选择排序 简单选择排序简单

32、选择排序无序区的最小值无序区的最小值45与与67交换交换简单选择排序算法（方法一，不稳定的算法） ：void SelectSort( SqList &L ) /对顺序表对顺序表L作简单选择排序作简单选择排序 for(i=1; iL.length; i+) min=i; for(j=i+1;j=L.length;j+) /选最小的记录选最小的记录 if(L.Rj.keyL.Rmin.key)min=j; if(i!=min)L.RminL.Ri;/最小记录与无序区第一条记录交换最小记录与无序区第一条记录交换 /end for 选择排序选择排序 简单选择排序简单选择排序简单选择排序算法（方

33、法二，有稳定性的算法）：void SelectSort( SqList &L ) /对顺序表对顺序表L作简单选择排序作简单选择排序 for(i=1; iL.length; i+)for(min=i,j=i+1;j=L.length;j+) /选最小记录选最小记录 if(L.Rj.keyL.Rmin.key)min=j; if(i!=min) Rtemp=L.Rmin; /保留最小记录的副本保留最小记录的副本 for(j=min;ji;j+) L.Rj=L.Rj-1 /将将L.Ri.min-1右移一位右移一位 L.Ri=Rtemp; /将最小记录放入无序区的首元素处将最小记录放入无序区的

34、首元素处 /移动次数比方法一多移动次数比方法一多选择排序选择排序 简单选择排序简单选择排序简单选择排序性能分析：比较次数与表的初态无关： 最好的情况：表的初态恰好是正序排列 移动次数：Mmin0最坏的情况：每趟都有移动发生 移动次数：Mmax3(n-1) （注（注: 方法一）方法一）平均O(n2), 算法一不稳定，算法二稳定2111)/n(n-i)(nCCn-i maxmin选择排序选择排序 简单选择排序简单选择排序10.4 选择排序10.4.1 简单选择排序10.4.2 堆排序选择排序选择排序 10.4.2 堆排序(Heap Sort ) 用建堆的方法来选择待排序区间的最大或最小用建堆的方法

35、来选择待排序区间的最大或最小键值。键值。 一、堆定义一、堆定义 二、筛选操作二、筛选操作 三、建堆算法三、建堆算法 四、堆排序算法四、堆排序算法选择排序选择排序 堆排序堆排序 一、堆定义 设设n个元素的有限序列：个元素的有限序列：K1, K2, K3, . , Kn如果满足如果满足 KiK2i & KiK2i+1 其中其中1i1i n/2n/2 则称这个序列为则称这个序列为小根堆小根堆或或小顶堆小顶堆；如果满足如果满足 KiK2i & KiK2i+1 其中其中1i 1i n/2n/2 则称这个序列为则称这个序列为大根堆大根堆或或大顶堆大顶堆；选择排序选择排序 堆排序堆排序8 回

36、顾完全二叉树的性质,8 编号为i的结点, 其左孩子的编号为2i, 右孩子的编号为2i+18 如果将堆序列看成完全二叉树的按层次遍历序列 则这棵完全二叉树上每个结点的值比左孩子和右孩子值都要大(大根堆), 或比左孩子和右孩子值都要小(小根堆)。选择排序选择排序 堆排序堆排序例：大根堆 75, 38, 62, 25, 16, 49 小根堆 15, 36, 39, 45, 36, 60, 48, 93, 53 3862251649752639264560154893536543210256216 4938757654321026483945 602615893953选择排序选择排序 堆排序堆排序 二

37、、筛选操作8 前提：根结点的左、右子树都是堆，而根结点不满足堆条件;8 将根调整到合适的位置，使得整个序列成为堆。263926456072489353选择排序选择排序 堆排序堆排序 对对小根堆小根堆来说，筛选就是不断地将树根与来说，筛选就是不断地将树根与较小较小的孩子的孩子交换位置，直至整个序列都满足堆定义。交换位置，直至整个序列都满足堆定义。392645607248935326392645602648935372397245602648935326395345602648937226 对对大根堆大根堆来说，筛选就是将树根与来说，筛选就是将树根与较大的孩较大的孩子子交换位置，直至整个序列都满足

38、堆定义。交换位置，直至整个序列都满足堆定义。305348264518261572305348267218261545304548267218261553筛选算法筛选算法,P281-282, ,P281-282, 算法算法10.1010.10void HeapAdjustn ( SqList &H, int s, int m ) /已知已知H.Rs+1.mH.Rs+1.m满足大顶堆定义满足大顶堆定义 /调整调整H.Rs,H.Rs,使得使得H.Rs.mH.Rs.m成为大顶堆成为大顶堆 rc=H.Rs; /辅助变量辅助变量rcrc保留保留H.RsH.Rs的副本的副本 for(j=2*s; j

39、=m; j*=2) if(jm & H.Rj.keyH.Rj.key) break; /调整结束调整结束 H.Rs=H.Rj; s=j; H.Rs=rc;三、建堆8 将一个任意序列建成一个小根堆或大根堆；将一个任意序列建成一个小根堆或大根堆；8 自下而上、自右向左地进行筛选，将以每一个非终自下而上、自右向左地进行筛选，将以每一个非终端结点为根的子树筛选成堆；端结点为根的子树筛选成堆；8 具有具有n n个结点的完全二叉树有个结点的完全二叉树有 n/2n/2 个叶子结点，一个叶子结点，一个叶子就是一个堆。个叶子就是一个堆。8 完全二叉树最后一个非终端结点的编号为完全二叉树最后一个非终端结点

40、的编号为 n/2n/2 ；选择排序选择排序 堆排序堆排序53481836 303693 15457654321089107236185336459315723048举例：将10个元素的序列建成一个大顶堆：叶子非终端结点逐个进行筛选选择排序选择排序 堆排序堆排序36485336451593723018建大根堆选择排序选择排序 堆排序堆排序3648537245159336301845 36 48 5330369315187201234659871045 36 48 5330729315183601234659871036485372451593363018建大根堆选择排序选择排序 堆排序堆排序36

41、48937245155336301845 36 48 5330729315183601234659871045 36 48 9330725315183601234659871036489372451553363018建大根堆选择排序选择排序 堆排序堆排序9348537245153636301845 36 48 9330725315183601234659871045 93 48 53307236151836012346598710121293485372451536363018建大根堆选择排序选择排序 堆排序堆排序7248534593153636301845 93 48 53307236151

42、83601234659871093 72 48 533045361518360123465987101212四、堆排序以大顶堆为例：以大顶堆为例：8堆顶是排序区间最大的元素堆顶是排序区间最大的元素8去掉堆顶，将堆顶与堆的最后一个元素交换位置：去掉堆顶，将堆顶与堆的最后一个元素交换位置： 最大元素归位；最大元素归位； 新树根不满足堆定义，需要通过筛选调整为堆新树根不满足堆定义，需要通过筛选调整为堆选择排序选择排序 堆排序堆排序堆排序选择排序选择排序 堆排序堆排序7248534593153636301893 72 48 533045361518360123465987105348364593153

43、672301872 53 48 36304536151893012346598710第第1 1步：将堆顶步：将堆顶9393与堆的最后一个元素与堆的最后一个元素3636交换位交换位置（置（9393的位置被确定）；的位置被确定）；第第2 2步：将步：将3636筛选到合适的位置，恢复大根堆筛选到合适的位置，恢复大根堆堆排序选择排序选择排序 堆排序堆排序45483636931553301853 45 48 36303672151893012346598710第第1 1步：将堆顶步：将堆顶7272与堆的最后一个元素与堆的最后一个元素3636交换位交换位置（置（7272的位置被确定）；的位置被确定）；第第

44、2 2步：将步：将3636筛选到合适的位置，恢复大根堆筛选到合适的位置，恢复大根堆53483645153672301872 53 48 3630453615189301234659871072堆排序选择排序选择排序 堆排序堆排序45303636935348151848 45 30 36153672531893012346598710第第1 1步：将堆顶步：将堆顶5353与堆的最后一个元素与堆的最后一个元素1515交换位交换位置（置（5353的位置被确定）；的位置被确定）；第第2 2步：将步：将1515筛选到合适的位置，恢复大根堆筛选到合适的位置，恢复大根堆7245483636155330185

45、3 45 48 36303672151893012346598710堆排序选择排序选择排序 堆排序堆排序36301836935345154845 36 30 18153672534893012346598710第第1 1步：将堆顶步：将堆顶4848与堆的最后一个元素与堆的最后一个元素1818交换位交换位置（置（4848的位置被确定）；的位置被确定）；第第2 2步：将步：将1818筛选到合适的位置，恢复大根堆筛选到合适的位置，恢复大根堆724530363648151848 45 30 36153672531893012346598710堆排序选择排序选择排序 堆排序堆排序363018159353

46、3645 4836 36 30 18451572534893012346598710第第1 1步：将堆顶步：将堆顶4545与堆的最后一个元素与堆的最后一个元素1515交换位交换位置（置（4545的位置被确定）；的位置被确定）；第第2 2步：将步：将1515筛选到合适的位置，恢复大根堆筛选到合适的位置，恢复大根堆7236301836451545 36 30 18153672534893012346598710堆排序特点：c时间复杂度：时间复杂度：O(nlogO(nlog2 2n)n)c时间复杂度的数量级于数据集原始状态无关时间复杂度的数量级于数据集原始状态无关c不稳定的排序算法不稳定的排序算法c空间耗费少，只消耗了一个辅助记录结点空间耗费少，只消耗了一个辅助记录结点选择排序选择排序 简单选择排序简单选择排序第十章 排序(