讨论/《排序算法全解析》 - 堆排序/
《排序算法全解析》 - 堆排序

总结一下:
利用大顶堆的特性:根节点的值大于等于左右子节点。当数组呈大顶堆排列时,交换堆顶节点和最大索引节点,将堆顶数字置换到数组尾部,这个数一定是最大的。再次调整剩余堆(除去最后一个数字),使堆顶三角(堆顶三角一定包含堆中最大的数)中最大数位于根节点,找到剩余堆中最大索引节点,并与根节点交换……这样,不断找出最大数,并与最大索引数字交换将最大数放置于数组末尾,并且缩小堆范围,选出堆顶三角中的最大数与末尾数字交换位置,最后实现数组的升序排列。

仔细一点可以看出,最大数与堆中最大索引对应数字交换,跨越了中间多个数字,可以免除相邻数字间不必要的比较(因为大顶堆在宏观上是从大到小排序的),和希尔排序章节中提到的思想一致。

展开全部 10 讨论