堆排序

上次写了个快排的文章,果不其然被大家鄙视了。大概平时是一个写脚本的,这东西也不会了,大学时代还能帮别人替考c语言,现在连c都不写了。

回归正题,这里使用二叉堆,二叉堆是一个近似的完全二叉树,在很多地方都会用到这个结构。

通常使用数组来表示一个堆:假设数组第一个元素为根节点,那么它的左孩子节点就是第二个元素,右孩子节点为第三个元素。以此类推,假设一个节点是数组的第n个元素,它的左孩子节点就是第2n个元素,右孩子节点就是2n+1,可以使用floor(n/2)来获取其父节点。

二叉堆分为最大堆(MAX-HEAP,大顶堆)和最小堆(MIN-HEAP,小顶堆),最大堆就是父节点的值大于或等于子节点值的堆,所以根节点应该是最大的节点,最小堆反之。这里使用了最大堆。

堆排序主要思路是建立一个有n个元素的最大堆,此时最大的数字为根节点,将根节点和数组最后一个元素交换,重新对前n-1个元素调整,使之成为一个新的最大堆,然后拿出根节点放到后面,如此反复。所以主要涉及三个方法:

  1. 堆调整:最大堆最重要的部分,主要任务是维护一个堆的性质。给定一个节点,调整这个节点和其子节点的位置,使最大的数值在根节点,但是因为被调整的子节点值变小了,可能无法继续当大哥,所以对其进行调整,如此反复,一直调整到指定节点的值放到合适的位置。这个算法并不是建立最大堆,而是调整一个节点到合适的位置。
  2. 建堆:给定一个无序的树,通过建堆算法建立一个最大堆。通过对所有父节点进行堆调整算法,就会产生一个最大树。因为是一个完全二叉树,所以m层n个元素的树,最多有2^m个节点,最少2^(m-1)+1个节点,此时父节点应该是最多有n/2个父节点。
  3. 排序:排序如上面所讲,建立最大堆,此时的数组第一个元素是最大的,将此元素和尾元素交换。交换以后,堆的根节点虽然变化,但是其他节点的堆序并无变化,所以只需对根节点进行调整就又是一个最大堆了。重复以上过程一直到需要排序的元素只有一个的时候,就排好序了。

下面是堆排序的c代码: 头文件:

排序代码:

参考资料:

堆排序》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注