经典排序算法五 堆排序（JAVA实现）
互联网编程思想2019-04-20 15:44
堆排序基本原理
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。
首先我们来了解下什么是堆。
堆分为两种：大顶堆和小顶堆，两者的差别主要在于排序方式。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
大顶堆&小顶堆大顶堆的存储结构为：{19,16,15,9,8,1}
小顶堆的存储结构为：{1,8,9,15,16,19}
我举的是两个有序的例子，当然，大顶堆和小顶堆的存储结构未必是有序的，只要父节点大于他的左右孩子节点就是大顶堆了，父节点小于他的孩子左右孩子节点就是小顶堆。
堆排序的基本思想和步骤
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
下面我们举例来说明堆排序的步骤。
给定序列{15,8,1,19,16,9}
首先根据序列构造一个完全二叉树。
构造好的完全二叉树根据大顶堆的原理，我们构造一个大顶堆，此时我们从最后一个非叶子节点开始，如下图。
构造大顶堆大顶堆的存储结构为{19,16,9,8,15,1}
然后我们将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换，步骤如下。
第一步：将堆顶元素19和堆底元素1交换，然后再重建，得到新的大顶堆，存储结构为：{16,15,9,8,1,19}。
堆排序第一步第二步：将堆顶元素16和新的无序堆的堆底元素1交换，然后再重建，得到新的大顶堆，存储结构为：{15,8,9,1,16,19}
堆排序第二步第三步：将堆顶元素15和新的无序堆的堆底元素1交换，然后再重建，得到新的大顶堆，存储结构为：{9,8,1,15,16,19}
堆排序第三步第四步：将堆顶元素9和新的无序堆的堆底元素1交换，然后再重建，得到新的大顶堆，存储结构为：{8,1,9,15,16,19}
堆排序第四步第五步，将堆顶元素8和新的无序堆的堆底元素1交换，交换后整个堆为有序，存储结构为:{1,8,9,15,16,19}。
堆排序第五步代码实现
堆排序代码下面为错过前几期的小伙伴给上链接，有问题的小伙伴在评论区留言哦～
经典排序算法四 插入排序（JAVA实现）
经典排序算法三 选择排序（JAVA实现）
经典排序算法二 快速排序（JAVA实现）
经典排序算法一 冒泡排序（JAVA实现）
举报/反馈
0
0
收藏
分享
