《数据结构（C语言描述）（第2版）》教学课件6-10堆排序3

1、2016数据结构Data structure讲授：丁慧 堆排序常州信息职业技术学院0213堆排序8、建立初始大根堆实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)建立大根堆。8824162391134205第1步：调整R4。由于R4R8，所以交换R4与R8，调整结果如右图。72324168891134205123456814堆排序8、建立初始大根堆实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)建立大根堆。8824162391134205第2步：调整R3 。由于R3不小于其较大孩子结点R6，所以无需调整，结果如右图。78824162391

2、134205123456815堆排序8、建立初始大根堆实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)建立大根堆。2324161391884205第3步：调整R2 。由于R2R4，所以交换R2与R4；交换后R4又违反堆性质，即R4R8，再交换R4与R8，调整结果如右图。7882416239113420512345681388132316堆排序8、建立初始大根堆实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)建立大根堆。2324161342889105第4步：调整R1 。由于R1R3，所以交换R1与R3。交换后R3不违反堆性质，初始堆建立完

3、毕，如右图。723241613918842051234568914217堆排序8、建立初始大根堆实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)建立大根堆。下标12345678调整R44213912324160588调整R34213918824160523调整R24213918824160523调整R14288912324160513初始大根堆918842232416051318堆排序9、大根堆排序实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基础上进行大根堆排序。232416134288910512345687911

4、3第1趟：先将堆顶记录R1与堆底记录R8交换；再对无序区为R17重建堆，得新的无序区R17为88，24，42，23，13，16，05，新的有序区R8 为91，如右图。13881324231316914224880519堆排序9、大根堆排序实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基础上进行大根堆排序。231316914224880512345680505第2趟：先将堆顶记录R1与堆底记录R7交换；再对无序区为R16重建堆，得新的无序区R16为42，24，16，23，13，05，新的有序区R7,8为88,91，结果如右图。42880516231

5、3059116244288720堆排序9、大根堆排序实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基础上进行大根堆排序。2313059116244288123456870505第3趟：先将堆顶记录R1与堆底记录R6交换；再对无序区为R15重建堆，得新的无序区15为24，23，16，05，13，新的有序区R68为42,88,91，如右图。23420524051342911623248821堆排序9、大根堆排序实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基础上进行大根堆排序。0513429116232

6、4881234568713第4趟：先将堆顶记录R1与堆底记录R5交换；再对无序区为R14重建堆，得新的无序区14为23，13，16，05，新的有序区R58为24，42，88，91，如右图。132324052442911613238822堆排序9、大根堆排序实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基础上进行大根堆排序。052442911613238812345687第5趟：先将堆顶记录R1与堆底记录R4交换；再对无序区为R13重建堆，得新的无序区13为16，13，05，新的有序区R48为23，24，42，88，91，如右图。230523244

7、29105131688051623堆排序9、大根堆排序实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基础上进行大根堆排序。232442910513168812345687第6趟：先将堆顶记录R1与堆底记录R3交换；再对无序区为R12重建堆，得新的无序区12为13，05，新的有序区R38为16，23，24，42，88，91，如右图。05232442911605138805161324堆排序9、大根堆排序实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基础上进行大根堆排序。2324429116051388

8、12345687第7趟：先将堆顶记录R1与堆底记录R2交换，得新的无序区R1为05，新的有序区R28为13，16，23，24，42，88，91，由于无序区只有一条记录，归入有序区，有序区R18为05，13，16，23，24，42，88，91，至此，排序完成，如右图。0523244291161305881325堆排序9、大根堆排序实例实例：对关键字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基础上进行大根堆排序。下标12345678初始关键字4213912324160588初始堆9188422324160513第1趟88244223131605 91 第2趟422