时间:2021-05-19
对于堆排序会涉及一些完全二叉树知识。对于待排序列{10, 2, 11, 8, 7},把它看成是一颗完全二叉树,如下图所示。
堆分为大根堆和小根堆:大根堆表示每个根节点均大于其子节点(L(i) >= L(2i) && L(i) >= L(2i + 1)),小根堆表示每个根节点均小于其子节点(L(i) <= L(2i) && L(i) <= L(2i + 1))。(在完全二叉树中第i个节点的左子节点为2i,其右字节点为2i + 1)
本文将以大根堆的构建作为示例进行讲解。
堆排序的第一步——构建初始堆。如何构建初始堆呢?根据定义,关键点在于每个根节点。观察上述待排序列的完全二叉树,不难发现存在节点2和节点10有子节点,它们是需要关注的节点。
如何定位节点2呢?发现它是叶子节点,或者最后一个节点的父节点,根据完全二叉树的性质可知,除根节点外任意节点的父节点的编号为⌊n / 2⌋。已知n = 5,易知节点2的编号为⌊5 / 2⌋ = ②。比较它与左右子节点的大小并调整。
最后剩下根节点10,已知节点2的编号为②,② - 1 = ①即得到根节点10的编号。比较它与左右子节点的大小并调整。
调整完毕后发现已经构成了一个“大根堆”,示例中的待排序列较为简单,再给出一个较为复杂的待排序列,观察其构建大根堆的过程。对于待排序列{53, 17, 78, 09, 45, 65, 87, 32},将它看成一颗完全二叉树。
同样我们来看它所需要关注的节点有哪些。
根据第一个例子,我们很容易能定位节点09的编号为⌊8 / 2⌋ = ④,节点78的编号为④ - 1 = ③……,依次类推,发现了一定的规律,即需要调整的节点位置从⌊n / 2⌋开始依次递减直到根节点①结束(⌊n / 2⌋ ~ 1)。现在开始调整。
在第四次调整结束后发现节点53不满足大根堆的定义,其右子节点大于它,此时需要做进一步的向下调整。
注意向下调整是每次向上调整的时候都需要做的判断是否需要向下调整,而不是在所有的向上调整结束过后再回过头来向下调整。这样大根堆就建立好了,此时待排序列数组情况已经发生了改变:{87, 45, 78, 32, 17, 65, 53, 09}。接下来是如何进行排序的问题。将大根堆的根节点与最后一个节点互换,并调整二叉树使其仍然满足大根堆。
可以看到将根节点与最后一个节点呼唤后,待排序列的最大值已经放到了数组的最后一个位置{……, 87},此时完成了第一趟排序,但这第一趟排序还没有结束,此时除节点87外,其余节点并不满足大根堆的条件,所以需要对其余节点进行调整为大根堆。排序过程不再给出,Java和Python3的代码实现如下。
Java
package com.algorithm.sort.heap;import java.util.Arrays;/** * 堆排序 * Created by yulinfeng on 6/20/17. */public class Heap { public static void main(String[] args) { int[] nums = {53, 17, 78, 09, 45, 65, 87, 32}; nums = heapSort(nums); System.out.println(Arrays.toString(nums)); } /** * 堆排序 * @param nums 待排序数组序列 * @return 排好序的数组序列 */ private static int[] heapSort(int[] nums) { for (int i = nums.length / 2 - 1; i >= 0; i--) { heapAdjust(nums, i, nums.length); } for (int i = nums.length - 1; i > 0; i--) { int temp = nums[i]; nums[i] = nums[0]; nums[0] = temp; heapAdjust(nums, 0, i); } return nums; } /** * 调整堆 * * @param nums 待排序序列 * @param parent 待调整根节点 * @param length 数组序列长度 */ private static void heapAdjust(int[] nums, int parent, int length) { int temp = nums[parent]; int childIndex = 2 * parent + 1; //完全二叉树节点i从编号1开始的左子节点位置在2i,此处数组下标从0开始,即左子节点所在数组索引位置为:2i + 1 while (childIndex < length) { if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) { childIndex++; //节点有右子节点,且右子节点大于左子节点,则选取右子节点 } if (temp > nums[childIndex]) { break; //如果选中节点大于其子节点,直接返回 } nums[parent] = nums[childIndex]; parent = childIndex; childIndex = 2 * parent + 1; //继续向下调整 } nums[parent] = temp; }}Python3
#堆排序def heap_sort(nums): for i in range(int(len(nums) / 2 - 1), -1, -1): heap_adjust(nums, i, len(nums)) for i in range(len(nums) - 1, -1, -1): temp = nums[i] nums[i] = nums[0] nums[0] = temp heap_adjust(nums, 0, i) return nums#调整堆def heap_adjust(nums, parent, length): temp = nums[parent] childIndex = 2 * parent + 1 while childIndex < length: if childIndex + 1 < length and nums[childIndex] < nums[childIndex + 1]: childIndex += 1 if temp > nums[childIndex]: break nums[parent] = nums[childIndex] parent = childIndex childIndex = 2 * parent + 1 nums[parent] = temp nums = [53, 17, 78, 09, 45, 65, 87, 32]nums = heap_sort(nums)print(nums)以上这篇老生常谈比较排序之堆排序就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例总结了php一维二维数组键排序方法。分享给大家供大家参考。具体方法如下:在php中数组排序一直是一个老生常谈的问题,下面我们来集中讲一下关于在php中一
本文实例讲述了Python排序搜索基本算法之堆排序。分享给大家供大家参考,具体如下:堆是一种完全二叉树,堆排序是一种树形选择排序,利用了大顶堆堆顶元素最大的特点
java实现计数排序和桶排序实例代码目录比较和非比较的区别常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们
从堆排序的简介到堆排序的算法实现等如下:1.简介 堆排序是建立在堆这种数据结构基础上的选择排序,是原址排序,时间复杂度O(nlogn),堆排序并不是一种稳定的
本文实例为大家分享了C语言堆排序源代码,供大家参考,具体内容如下1.堆排序堆排序的定义及思想可以参考百度百科:用一句概括,堆排序就是一种改进的选择排序,改进的地