摘要：概述堆排序是一种树形选择排序，是对直接选择排序的有效改进。称这个过程为堆排序。步骤实例实现堆排序需解决两个问题如何将个待排序的数建成堆输出堆顶元素后，怎样调整剩余个元素，使其成为一个新堆。
概述
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：具有n个元素的序列(k1,k2,...,kn), 当且仅当满足:
时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）或最大项（大顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点（有子女的结点）的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。
(a)大顶堆序列：(96, 83, 27, 38, 11, 09)
(b)小顶堆序列：(12, 36, 24, 85, 47, 30, 53, 91)
初始时把要排序的n 个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素。然后对剩下的n-1个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到最后得到有n个节点的有序序列。称这个过程为堆排序。
步骤&实例实现堆排序需解决两个问题：
如何将n 个待排序的数建成堆；
输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。
建堆方法（小顶堆）：
对初始序列建堆的过程，就是一个反复进行筛选的过程。
n 个结点的完全二叉树，则最后一个结点是第n/2个结点的子树。
筛选从第n/2个结点为根的子树开始（n/2是最后一个有子树的结点），使该子树成为堆。
之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。
如图建堆初始过程
无序序列：(49, 38, 65, 97, 76, 13, 27, 49)
(a) 无序序列，初始二叉树，97（第8/2=4个结点）为最后一个结点（49）的父结点。
(b) 97>=49,替换位置，接下来对n/2的上一个结点65进行筛选。
(c) 13<=27且65>=13,替换65和13的位置，接下来对38进行替换（都大于它，不需操作），对49进行筛选。
(d) 13<=38且49>=13,替换49和13的位置，49>=27,替换49和27的位置。
(e) 最终得到一个堆，13是我们得到的最小数。
调整堆的方法（小顶堆）：
设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶，堆被破坏，其原因仅是根结点不满足堆的性质。
将根结点与左、右子树中较小元素的进行交换。
若与左子树交换：如果左子树堆被破坏，则重复方法(2).
若与右子树交换，如果右子树堆被破坏，则重复方法(2).
继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。
调整堆只需考虑被破坏的结点，其他的结点不需调整。
代码实现(Java)运行代码结合注释与上面的实例步骤进行对比思考。
package com.coder4j.main;
public class HeapSort {
/**
* 调整为小顶堆（排序后结果为从大到小）
*
* @param array是待调整的堆数组
* @param s是待调整的数组元素的位置
* @param length是数组的长度
*
*/
public static void heapAdjustS(int[] array, int s, int length) {
int tmp = array[s];
int child = 2 * s + 1;// 左孩子结点的位置
System.out.println("待调整结点为：array[" + s + "] = " + tmp);
while (child < length) {
// child + 1 是当前调整结点的右孩子
// 如果有右孩子且小于左孩子，使用右孩子与结点进行比较，否则使用左孩子
if (child + 1 < length && array[child] > array[child + 1]) {
child++;
}
System.out.println("将与子孩子 array[" + child + "] = " + array[child] + " 进行比较");
// 如果较小的子孩子比此结点小
if (array[s] > array[child]) {
System.out.println("子孩子比其小，交换位置");
array[s] = array[child];// 把较小的子孩子向上移动，替换当前待调整结点
s = child;// 待调整结点移动到较小子孩子原来的位置
array[child] = tmp;
child = 2 * s + 1;// 继续判断待调整结点是否需要继续调整
if (child >= length) {
System.out.println("没有子孩子了，调整结束");
} else {
System.out.println("继续与新的子孩子进行比较");
}
// continue;
} else {
System.out.println("子孩子均比其大，调整结束");
break;// 当前待调整结点小于它的左右孩子，不需调整，直接退出
}
}
}
/**
* 调整为大顶堆（排序后结果为从小到大）
*
* @param array是待调整的堆数组
* @param s是待调整的数组元素的位置
* @param length是数组的长度
*
*/
public static void heapAdjustB(int[] array, int s, int length) {
int tmp = array[s];
int child = 2 * s + 1;// 左孩子结点的位置
System.out.println("待调整结点为：array[" + s + "] = " + tmp);
while (child < length) {
// child + 1 是当前调整结点的右孩子
// 如果有右孩子且大于左孩子，使用右孩子与结点进行比较，否则使用左孩子
if (child + 1 < length && array[child] < array[child + 1]) {
child++;
}
System.out.println("将与子孩子 array[" + child + "] = " + array[child] + " 进行比较");
// 如果较大的子孩子比此结点大
if (array[s] < array[child]) {
System.out.println("子孩子比其大，交换位置");
array[s] = array[child];// 把较大的子孩子向上移动，替换当前待调整结点
s = child;// 待调整结点移动到较大子孩子原来的位置
array[child] = tmp;
child = 2 * s + 1;// 继续判断待调整结点是否需要继续调整
if (child >= length) {
System.out.println("没有子孩子了，调整结束");
} else {
System.out.println("继续与新的子孩子进行比较");
}
// continue;
} else {
System.out.println("子孩子均比其小，调整结束");
break;// 当前待调整结点大于它的左右孩子，不需调整，直接退出
}
}
}
/**
* 堆排序算法
*
* @param array
* @param inverse true 为倒序排列，false 为正序排列
*/
public static void heapSort(int[] array, boolean inverse) {
// 初始堆
// 最后一个有孩子的结点位置 i = (length - 1) / 2, 以此向上调整各结点使其符合堆
System.out.println("初始堆开始");
for (int i = (array.length - 1) / 2; i >= 0; i--) {
if (inverse) {
heapAdjustS(array, i, array.length);
} else {
heapAdjustB(array, i, array.length);
}
}
System.out.println("初始堆结束");
for (int i = array.length - 1; i > 0; i--) {
// 交换堆顶元素H[0]和堆中最后一个元素
int tmp = array[i];
array[i] = array[0];
array[0] = tmp;
// 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
if (inverse) {
heapAdjustS(array, 0, i);
} else {
heapAdjustB(array, 0, i);
}
}
}
public static void main(String[] args) {
int[] array = { 49, 38, 65, 97, 76, 13, 27, 49 };
heapSort(array, false);
for (int i : array) {
System.out.print(i + " ");
}
}
}
运行结果：
初始堆开始 待调整结点为：array[3] = 97 将与子孩子 array[7] = 49 进行比较 子孩子比其小，交换位置 没有子孩子了，调整结束 待调整结点为：array[2] = 65 将与子孩子 array[5] = 13 进行比较 子孩子比其小，交换位置 没有子孩子了，调整结束 待调整结点为：array[1] = 38 将与子孩子 array[3] = 49 进行比较 子孩子均比其大，调整结束 待调整结点为：array[0] = 49 将与子孩子 array[2] = 13 进行比较 子孩子比其小，交换位置 继续与新的子孩子进行比较 将与子孩子 array[6] = 27 进行比较 子孩子比其小，交换位置 没有子孩子了，调整结束 初始堆结束 待调整结点为：array[0] = 97 将与子孩子 array[2] = 27 进行比较 子孩子比其小，交换位置 继续与新的子孩子进行比较 将与子孩子 array[6] = 49 进行比较 子孩子比其小，交换位置 没有子孩子了，调整结束 待调整结点为：array[0] = 97 将与子孩子 array[1] = 38 进行比较 子孩子比其小，交换位置 继续与新的子孩子进行比较 将与子孩子 array[3] = 49 进行比较 子孩子比其小，交换位置 没有子孩子了，调整结束 待调整结点为：array[0] = 65 将与子孩子 array[1] = 49 进行比较 子孩子比其小，交换位置 继续与新的子孩子进行比较 将与子孩子 array[4] = 76 进行比较 子孩子均比其大，调整结束 待调整结点为：array[0] = 76 将与子孩子 array[2] = 49 进行比较 子孩子比其小，交换位置 没有子孩子了，调整结束 待调整结点为：array[0] = 97 将与子孩子 array[1] = 65 进行比较 子孩子比其小，交换位置 没有子孩子了，调整结束 待调整结点为：array[0] = 76 将与子孩子 array[1] = 97 进行比较 子孩子均比其大，调整结束 待调整结点为：array[0] = 97 97 76 65 49 49 38 27 13
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/65436.html
摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法为王。 想学好前端，先练好内功，只有内功深厚者，前端之路才...
摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。 前面介绍了七大算法的思想与实现步骤，下面来做一个归总。 排序方法 平均复杂度 最坏复杂度 最好复杂度 辅助空间 稳定性 直接选择排序 O(n^2...
摘要：奇妙的记忆点不稳定内排序基本思想分为两步建堆与维持堆的性质首先我们要先理解堆是什么东西堆其实就是一个完全二叉树我们可以使用顺序表存储一个二叉树如下图所示来存储其中分为最大堆最小堆而最大堆就是上头大下头小最小堆则反之明白了堆的定义我们就可以开 奇妙的记忆点: 不稳定 内排序 基本思想: 分为两步,建堆与维持堆的性质,首先我们要先理解堆是什么东西.堆其实就是一个完全二叉树,我们可以使用...
摘要：当到达时等同于直接插入排序，此时序列已基本有序，所有记录在统一组内排好成有序序列。当面对大量数据时，希尔排序将比直接插入排序更具优势图示讲解第一趟取增量，所有间隔为的元素分在一组，在各个组中分别进行直接插入排序。 ...
阅读 2594·2021-11-02 14:42
阅读 3008·2021-10-08 10:04
阅读 999·2019-08-30 15:55
阅读 867·2019-08-30 15:54
阅读 2191·2019-08-30 15:43
阅读 1584·2019-08-29 15:18
阅读 766·2019-08-29 11:11
阅读 2231·2019-08-26 13:52
