堆排序

一、相关概述

1.1 基本介绍

• 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。它的最坏最好平均时间复杂度均为 O(nlogn)，它属于不稳定排序（即：在排序过程中，如果两个键的值相同，那么他们的相对位置会发生变化）。
• 堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。
• 注意 : 没有要求节点的左孩子的值和右孩子的值的大小关系。
• 大顶堆示意图：

• 小顶堆示意图：

• 说明：一般升序采用大顶堆，降序采用小顶堆。

1.2 排序思想

1. 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点（创建一个堆 H[0……n-1]）；
2. 将其与末尾元素进行交换，此时末尾就为最大值（把堆首（最大值）和堆尾互换）；
3. 然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值（把堆的尺寸缩小 1，目的是把新的数组顶端数据调整到相应位置）；
4. 如此反复执行（元素的个数逐渐减少），便能得到一个有序序列了（重复步骤 2，直到堆的尺寸为 1）。

二、基本应用

2.1 步骤说明

需求：假设将数组 {4,6,8,5,9} 要求使用堆排序法，将数组升序排序。

• 示意图：

2.2 代码示例

public class HeapSort {public static void main(String[] args) {int[] array = new int[10];for (int i = 0; i < array.length; i++) {// 随机 100 以内的整数。array[i] = (int) (Math.random() * 100);}System.out.println("before:" + Arrays.toString(array));// before:[72, 36, 54, 10, 87, 11, 2, 81, 81, 20]heapSort(array);System.out.println("after:" + Arrays.toString(array));// after:[2, 10, 11, 20, 36, 54, 72, 81, 81, 87]}/*** 堆排序。** @param array 数组*/public static void heapSort(int[] array) {// 将无序序列构建成一个堆 (升序选择大顶堆 / 降序选择小顶堆)。for (int i = (array.length / 2 - 1); i >= 0; i--) {adjustHeap(array, i, array.length);}// 将堆顶元素与末尾元素交换，并反复调整结构。int temp;for (int j = (array.length - 1); j > 0; j--) {// 交换。temp = array[j];array[j] = array[0];array[0] = temp;adjustHeap(array, 0, j);}}/*** 将一个数组(二叉树)，调整成一个大顶堆。** @param array  待调整的数组* @param index  非叶子节点在数组中的索引* @param length 对多少个元素继续调整 (该值不断减小)*/public static void adjustHeap(int[] array, int index, int length) {// 将当前元素值保存至临时变量。int temp = array[index];// 开始调整动作：// ( k = i * 2 + 1 ) : 表示 k 是 index 节点的左子节点。for (int k = (index * 2 + 1); k < length; k = (k * 2 + 1)) {// 说明左子节点的值小于右子节点的值。if ((k + 1 < length) && (array[k] < array[k + 1])) {// 指向右子节点。k++;}// 如果子节点大于父节点。if (array[k] > temp) {// 则把较大值赋值给当前节点。array[index] = array[k];// 索引指向k继续循环比较。index = k;} else {break;}}// 循环结束，表示已经 index 已经为父节点树的最大值。（即最顶部）array[index] = temp;}
}

三、结束语

---

“-------怕什么真理无穷,进一寸有一寸的欢喜。”

微信公众号搜索：饺子泡牛奶。