《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件6-10堆排序3

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：丁慧 堆排序常州信息職業(yè)技術(shù)學(xué)院0213堆排序8、建立初始大根堆實(shí)例實(shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)建立大根堆。8824162391134205第1步：調(diào)整R4。由于R4R8，所以交換R4與R8，調(diào)整結(jié)果如右圖。72324168891134205123456814堆排序8、建立初始大根堆實(shí)例實(shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)建立大根堆。8824162391134205第2步：調(diào)整R3 。由于R3不小于其較大孩子結(jié)點(diǎn)R6，所以無需調(diào)整，結(jié)果如右圖。78824162391

2、134205123456815堆排序8、建立初始大根堆實(shí)例實(shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)建立大根堆。2324161391884205第3步：調(diào)整R2 。由于R2R4，所以交換R2與R4；交換后R4又違反堆性質(zhì)，即R4R8，再交換R4與R8，調(diào)整結(jié)果如右圖。7882416239113420512345681388132316堆排序8、建立初始大根堆實(shí)例實(shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)建立大根堆。2324161342889105第4步：調(diào)整R1 。由于R1R3，所以交換R1與R3。交換后R3不違反堆性質(zhì)，初始堆建立完

3、畢，如右圖。723241613918842051234568914217堆排序8、建立初始大根堆實(shí)例實(shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)建立大根堆。下標(biāo)12345678調(diào)整R44213912324160588調(diào)整R34213918824160523調(diào)整R24213918824160523調(diào)整R14288912324160513初始大根堆918842232416051318堆排序9、大根堆排序?qū)嵗龑?shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基礎(chǔ)上進(jìn)行大根堆排序。232416134288910512345687911

4、3第1趟：先將堆頂記錄R1與堆底記錄R8交換；再對無序區(qū)為R17重建堆，得新的無序區(qū)R17為88，24，42，23，13，16，05，新的有序區(qū)R8 為91，如右圖。13881324231316914224880519堆排序9、大根堆排序?qū)嵗龑?shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基礎(chǔ)上進(jìn)行大根堆排序。231316914224880512345680505第2趟：先將堆頂記錄R1與堆底記錄R7交換；再對無序區(qū)為R16重建堆，得新的無序區(qū)R16為42，24，16，23，13，05，新的有序區(qū)R7,8為88,91，結(jié)果如右圖。42880516231

5、3059116244288720堆排序9、大根堆排序?qū)嵗龑?shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基礎(chǔ)上進(jìn)行大根堆排序。2313059116244288123456870505第3趟：先將堆頂記錄R1與堆底記錄R6交換；再對無序區(qū)為R15重建堆，得新的無序區(qū)15為24，23，16，05，13，新的有序區(qū)R68為42,88,91，如右圖。23420524051342911623248821堆排序9、大根堆排序?qū)嵗龑?shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基礎(chǔ)上進(jìn)行大根堆排序。0513429116232

6、4881234568713第4趟：先將堆頂記錄R1與堆底記錄R5交換；再對無序區(qū)為R14重建堆，得新的無序區(qū)14為23，13，16，05，新的有序區(qū)R58為24，42，88，91，如右圖。132324052442911613238822堆排序9、大根堆排序?qū)嵗龑?shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基礎(chǔ)上進(jìn)行大根堆排序。052442911613238812345687第5趟：先將堆頂記錄R1與堆底記錄R4交換；再對無序區(qū)為R13重建堆，得新的無序區(qū)13為16，13，05，新的有序區(qū)R48為23，24，42，88，91，如右圖。230523244

7、29105131688051623堆排序9、大根堆排序?qū)嵗龑?shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基礎(chǔ)上進(jìn)行大根堆排序。232442910513168812345687第6趟：先將堆頂記錄R1與堆底記錄R3交換；再對無序區(qū)為R12重建堆，得新的無序區(qū)12為13，05，新的有序區(qū)R38為16，23，24，42，88，91，如右圖。05232442911605138805161324堆排序9、大根堆排序?qū)嵗龑?shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基礎(chǔ)上進(jìn)行大根堆排序。2324429116051388

8、12345687第7趟：先將堆頂記錄R1與堆底記錄R2交換，得新的無序區(qū)R1為05，新的有序區(qū)R28為13，16，23，24，42，88，91，由于無序區(qū)只有一條記錄，歸入有序區(qū)，有序區(qū)R18為05，13，16，23，24，42，88，91，至此，排序完成，如右圖。0523244291161305881325堆排序9、大根堆排序?qū)嵗龑?shí)例：對關(guān)鍵字序列(42，13， 91，23， 24，16，05，88)所建立的初始大根堆基礎(chǔ)上進(jìn)行大根堆排序。下標(biāo)12345678初始關(guān)鍵字4213912324160588初始堆9188422324160513第1趟88244223131605 91 第2趟422