《详细的堆排序》由会员分享，可在线阅读，更多相关《详细的堆排序（3页珍藏版）》请在装配图网上搜索。
1、2012.2.21关于堆排序的理解堆排序的原理及分极：1. 什么叫堆？它所具有的几大特性？ 堆它在逻辑上是是符合完全二叉树的特性，存储上它是数组对象(二叉堆)，它必需在满 足完全二叉树的基础上还符合以下一个特性： 如果是小根堆：该树的任何非叶节点的值的大小必需小于它的左右节点。如果是大根堆：该树的任何非叶节点的值的大小必需大小它的左右节点。2. 程序过程分解：主要有以下三个步骤：先建立逻辑二叉树 再根据堆的条件先建立堆，然后再筛选。 假如有以下数组元素：15,14,13,12,19,20,31先建立逻辑二叉树：编号()里索引编号 假设从 1 开始15 (1)14(2) 13(3)12(4) 1
2、9(5) 20(6) 31(7)根据条件建堆： 根据数组可知道数组长度为：7 可知我们要从索引为 index=7/2=3 开始 因为要是保证当前节点它有子节点，如果 没有子节点，则没有可比性。在索引 3 号位置上看它是不是只有左节点还是左右节点都有。 如果有左右节点 则先比较左右节点，再拿左右节点里最大的与父节点比较。 如果只有右节点，则父节点直接与它的左节点相比较。15 (1)14(2) 13(3)/在索引 3 上比较后调整12(4) 19(5) 20(6) 31(7)15 (1)/在索引 2 上比较后调整12(2) 13(3)14(4) 19(5) 20(6) 31(7)12 (1)15(
3、2) 13(3)/在索引 1 上比较后调整14(4) 19(5) 20(6) 31(7)进入筛选步骤：至此该树已经满足堆的特性，索引 1 上的数字已经是最小的则将 12 踢除，将数组的最 后一个值来代替它。所以该树变成：31 (1)15(2)13(3)/在索引 1 上比较后调整14(4) 19(5) 20(6)再进行建堆的操作如上则变成：31 (1)/在索引 3 上比较后调整15(2) 13(3)14(4) 19(5) 20(6)31 (1)142) 13(3)/在索引 2 上比较后调整15(4) 19(5) 20(6)13 (1)14(2) 31(3)/在索引 1 上比较后调整15(4) 1
4、9(5) 20(6)比较完之后它已经又是一个堆了则将13踢除，将数组的最后一个代替数组首位。再进行建堆操作：20 (1)14(2) 31(3)15(4) 19(5)14 (1)20(2) 31(3)15(4) 19(5)/在索引 2 上比较后调整/在索引 1 上比较后调整比较完之后它已经又是一个堆了则将14踢除， 将数组的最后一个代替数组首位。 再进行建堆操作：19 (1)15(2) 31(3)20(4)/在索引 2 上比较后调整15 (1)19(2) 31(3)20(4)比较完之后它已经又是一个堆了则将 15踢除 再进行建堆操作：/在索引 1 上比较后调整将数组的最后一个代替数组首位。19 (1)20(2) 31(3)/在索引 1 上比较后调整比较完之后它已经又是一个堆了则将19踢除， 将数组的最后一个代替数组首位。 再进行建堆操作：20 (1)/在索引 1 上比较后调整31(2)比较完之后它已经又是一个堆了则将 20 踢除， 将数组的最后一个代替数组首位。 再进行建堆操作：31(1)小袁
详细的堆排序
