资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：丁慧,堆排序,常州信息职业技术学院,02,13,堆排序,8,、建立初始大根堆实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),建立大根堆。,88,24,16,23,91,13,42,05,第,1,步：,调整,R4,。由于,R4R8,，所以交换,R4,与,R8,，调整结果如,右图,。,7,23,24,16,88,91,13,42,05,1,2,3,4,5,6,8,14,堆排序,8,、建立初始大根堆实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),建立大根堆。,88,24,16,23,91,13,42,05,第,2,步：,调整,R3,。由于,R3,不小于其较大孩子结点,R6,，所以无需调整，结果如,右,图,。,7,88,24,16,23,91,13,42,05,1,2,3,4,5,6,8,15,堆排序,8,、建立初始大根堆实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),建立大根堆。,23,24,16,13,91,88,42,05,第,3,步：,调整,R2,。由于,R2R4,，所以交换,R2,与,R4,；交换后,R4,又违反堆性质，即,R4R8,，再交换,R4,与,R8,，调整结果如,右,图。,7,88,24,16,23,91,13,42,05,1,2,3,4,5,6,8,13,88,13,23,16,堆排序,8,、建立初始大根堆实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),建立大根堆。,23,24,16,13,42,88,91,05,第,4,步：,调整,R1,。由于,R1R3,，所以交换,R1,与,R3,。交换后,R3,不违反堆性质，初始堆建立完毕，如,右,图。,7,23,24,16,13,91,88,42,05,1,2,3,4,5,6,8,91,42,17,堆排序,8,、建立初始大根堆实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),建立大根堆。,下标,1,2,3,4,5,6,7,8,调整,R4,42,13,91,23,24,16,05,88,调整,R3,42,13,91,88,24,16,05,23,调整,R2,42,13,91,88,24,16,05,23,调整,R1,42,88,91,23,24,16,05,13,初始大根堆,91,88,42,23,24,16,05,13,18,堆排序,9,、大根堆排序实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),所建立的初始大根堆基础上进行大根堆排序。,23,24,16,13,42,88,91,05,1,2,3,4,5,6,8,7,91,13,第,1,趟：,先将堆顶记录,R1,与堆底记录,R8,交换；再对无序区为,R17,重建堆，得新的无序区,R17,为,88,，,24,，,42,，,23,，,13,，,16,，,05,，新的有序区,R8,为,91,，如,右,图。,13,88,13,24,23,13,16,91,42,24,88,05,19,堆排序,9,、大根堆排序实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),所建立的初始大根堆基础上进行大根堆排序。,23,13,16,91,42,24,88,05,1,2,3,4,5,6,8,05,05,第,2,趟：,先将堆顶记录,R1,与堆底记录,R7,交换；再对无序区为,R16,重建堆，得新的无序区,R16,为,42,，,24,，,16,，,23,，,13,，,05,，新的有序区,R7,8,为,88,91,，,结果,如,右,图。,42,88,05,16,23,13,05,91,16,24,42,88,7,20,堆排序,9,、大根堆排序实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),所建立的初始大根堆基础上进行大根堆排序。,23,13,05,91,16,24,42,88,1,2,3,4,5,6,8,7,05,05,第,3,趟：,先将堆顶记录,R1,与堆底记录,R6,交换；再对无序区为,R15,重建堆，得新的无序区,15,为,24,，,23,，,16,，,05,，,13,，新的有序区,R68,为,42,88,91,，如,右,图。,23,42,05,24,05,13,42,91,16,23,24,88,21,堆排序,9,、大根堆排序实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),所建立的初始大根堆基础上进行大根堆排序。,05,13,42,91,16,23,24,88,1,2,3,4,5,6,8,7,13,第,4,趟：,先将堆顶记录,R1,与堆底记录,R5,交换；再对无序区为,R14,重建堆，得新的无序区,14,为,23,，,13,，,16,，,05,，新的有序区,R58,为,24,，,42,，,88,，,91,，如,右,图。,13,23,24,05,24,42,91,16,13,23,88,22,堆排序,9,、大根堆排序实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),所建立的初始大根堆基础上进行大根堆排序。,05,24,42,91,16,13,23,88,1,2,3,4,5,6,8,7,第,5,趟：,先将堆顶记录,R1,与堆底记录,R4,交换；再对无序区为,R13,重建堆，得新的无序区,13,为,16,，,13,，,05,，新的有序区,R48,为,23,，,24,，,42,，,88,，,91,，如,右,图。,23,05,23,24,42,91,05,13,16,88,05,16,23,堆排序,9,、大根堆排序实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),所建立的初始大根堆基础上进行大根堆排序。,23,24,42,91,05,13,16,88,1,2,3,4,5,6,8,7,第,6,趟：,先将堆顶记录,R1,与堆底记录,R3,交换；再对无序区为,R12,重建堆，得新的无序区,12,为,13,，,05,，新的有序区,R38,为,16,，,23,，,24,，,42,，,88,，,91,，如,右,图。,05,23,24,42,91,16,05,13,88,05,16,13,24,堆排序,9,、大根堆排序实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),所建立的初始大根堆基础上进行大根堆排序。,23,24,42,91,16,05,13,88,1,2,3,4,5,6,8,7,第,7,趟：,先将堆顶记录,R1,与堆底记录,R2,交换，得新的无序区,R1,为,05,，新的有序区,R28,为,13,，,16,，,23,，,24,，,42,，,88,，,91,，由于无序区只有一条记录，归入有序区，有序区,R18,为,05,，,13,，,16,，,23,，,24,，,42,，,88,，,91,，至此，排序完成，如,右,图。,05,23,24,42,91,16,13,05,88,13,25,堆排序,9,、大根堆排序实例,实例：,对关键字序列,(42,，,13,，,91,，,23,，,24,，,16,，,05,，,88),所建立的初始大根堆基础上进行大根堆排序。,下标,1,2,3,4,5,6,7,8,初始关键字,42,13,91,23,24,16,05,88,初始堆,91,88,42,23,24,16,05,13,第,1,趟,88,24,42,23,13,16,05, 91 ,第,2,趟,42,24,16,23,13,05, 88,91 ,第,3,趟,24,23,16,05,13, 42,88,91 ,第,4,趟,23,13,16,05, 24,42,88,91 ,第,5,趟,16,13,05, 23,24,42,88,91 ,第,6,趟,13,05, 16,23,24,42,88,91 ,第,7,趟, 05,13,16,23,24,42,88,91 ,THANKS,
展开阅读全文