排序算法之堆排序

概述

介绍堆排序之前, 要先介绍什么是堆以及最大堆最小堆

什么是堆

这里的堆指的不是堆栈中的堆, 而是一种数据结构.

堆可以视为一棵完全的二叉树,完全二叉树的一个"优秀"的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素, 如下所示:

排序算法之堆排序

最大堆

最大堆就是堆中每个父节点的元素值都大于等于其孩子结点(如果存在),这样的堆就是一个最大堆

显而易见, 最大堆中的最大元素值出现在根结点(堆顶)

最小堆

最小堆就是堆中每个父节点的元素值都小于等于其孩子结点(如果存在),这样的堆就是一个最小堆

因此,最小堆中的最小元素值出现在根结点(堆顶)

数组的索引与节点的关系

parent(i) = (i-1)/2 向下取整
left(i) = 2i+1
rigth(i) = 2i+2

堆排序的思路

将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

img

堆排序的时间空间复杂度如下:

1537259455310f242a1c404 (603×95)

Java代码实现

代码如下, 就是上边思路的实现.注释已经很详细了.

153725949533469455a7504 (640×754)

15372599303395932d9e1e7 (637×474)

------------

原文地址 https://hujingnb.com/archives/174

转载请保留原文连接: 排序算法之堆排序 | 烟草的香味

guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请发表评论。x