基本介绍
- 1）、堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最好、最坏、平均时间复杂度均为O(nlogn)，它也是不稳定排序。
- 2）、堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆，注意：没有要求节点的左孩子的值和右孩子的值的大小关系。
- 3）、每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。
- 4）、大堆顶举例说明，堆数据都是以顺序存储二叉树的形式存储到数组中。
- 5）、小堆顶距离说明
- 6）、一般升序用大顶堆，降序用小顶堆
基本思想：
- 1）、将待排序序列构造成一个大顶堆或小顶堆；
- 2）、此时，整个序列的最大值或最小值就是堆顶的根节点；
- 3）、将其与末尾元素进行交换，此时末尾就为最大值或最小值；
- 4）、然后将剩余的 n-1 个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
可以看到在构建大堆顶的过程中，元素的个数逐渐减少，最后就得到一个有序序列了。
举例：
- 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序用大顶堆，降序用小顶堆）
- 1)、原始数组｛4,6,8,5,9｝
2）、此时我们从最后一个非叶子节点开始（叶节点自然不用调整，第一个非叶子节点 arr.length/2 -1 =5/2 -1 = 1，也就是下面的6节点），从左至右，从下至上进行调整。
- 3）、找到第二个非叶子节点4，由于【4,9,8】中的9元素最大，4和9 交换
4）、这时，交换导致了根【4,5,6】结构混乱，继续调整，6最大，交换4和6
- 此时，我们就将一个无序序列构造成了一个大顶堆。
- 5）、将堆顶元素和末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素和末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
- 6）、交换堆顶元素和末尾元素的值
- 7）、找到最后一个非叶子节点，【6,5】构造大顶堆，6大于5，不用交换
- 8）、找到非叶子节点【4,6,8】,构造大顶堆，8和4交换位置
- 9）、交换堆顶元素和末尾元素的值
- 10）、找到非叶子节点【5,6,4】,构造大顶堆，6和5交换位置
- 11）、交换堆顶元素和末尾元素的值
- 12）、找到非叶子节点【4,5】,构造大顶堆，4和5交换位置
- 13）、交换堆顶元素和末尾元素的值
- 14)、最后得到一个有序序列{4,5,6,8,9}
示例代码
public class HeapSortDemo {public static void main(String[] args) {int[] arr = {4, 6, 8, 5, 9};int k = 1;for (int i = arr.length / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, arr.length);System.out.printf("%d = %s\n", k++, Arrays.toString(arr));}int temp;for (int j = arr.length - 1; j > 0; j--) {temp = arr[j];arr[j] = arr[0];arr[0] = temp;adjustHeap(arr, 0, j);}System.out.printf("排序完成后的数组：%s\n", Arrays.toString(arr));}public static void adjustHeap(int[] arr, int i, int length) {int temp = arr[i];for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {if ((k + 1) < length && arr[k] < arr[k + 1]) {k++;}if (arr[k] > temp) {arr[i] = arr[k]; i = k;} else {break;}}arr[i] = temp;}
}
