希尔排序
待排序区间划分成若干个有跨度的子区间,然后进行插入排序,当最后跨度缩小到1的时候来一次完整的插入排序。
...第一次排序:length = 10; gap = a.length / 2 = 5; 将待排序的区间分成五个相同跨度的子区间。...得到{49,13} {38,27} {65,49*} {97,55} {76,4}五个子区间,进行插入排序,得到排序后的区间为:{13,49} {27,38} {49*,65} {97,55} {4,76...*,65,97,76}
第三次排序:gap = gap / 2 = 1; 所以直接对{4,27,13,49,38,55,49*,65,97,76}进插入排序,就可以得到排序后的区间为{4,13,27,38,49,49...用数组存储,第i个节点的叶子分别是2i+1和2i+2
(2)根的值小于(或者大于)左右子树,子树也需要满足这个定义
(3)堆看起来是一棵完全二叉树,存储却只需要用到数组即可
(4)开始建堆的时候数组顺序与二叉树层次遍历对应