基本原理

1):将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素

2):将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；

3):重复步骤2

小知识点

大顶堆：在完全二叉树的基础上，每个结点的值都大于或等于其左右孩子结点的值

小顶堆：在完全二叉树的基础上，每个结点的值都小于或等于其左右孩子结点的值

完全二叉树：完全二叉树是一种特殊的二叉树。从上到下，从左到右，每一层的节点都是满的，最下边一层所有的节点都是连续集中在最左边

步骤

第一步：构建大顶堆

一：将无序的数组画出来一个二叉树，开始构建大顶堆

二：8是3的左孩子父亲（parent）没有左孩子（lChild）大所以二者进行交换，

三：17比他兄弟小让左孩子（LChild）和父亲（parent）交换

四：20比他兄弟和父亲都大，lChild和parent互换

五：16与他的孩子又不满足条件，与又孩子互换

大顶堆完成

第二步：将堆顶元素和最后一个元素进行交换，然后将剩下的节点重新构造成一个大顶堆

重复

重复

重复

重复得出结果

代码

public class HeapSort {public static void main(String[] args) {int[] arr = {16, 7, 3, 20, 17, 8};heapSort(arr);for (int i : arr) {System.out.print(i + " ");}}/*** 创建堆，* @param arr 待排序列*/private static void heapSort(int[] arr) {//创建堆(这个地方可以先讲解一下)for (int i = arr.length - 1; i >= 0; i--) {//从第一个非叶子结点从下至上，从右至左调整结构adjustHeap(arr, i, arr.length);}//调整堆结构+交换堆顶元素与末尾元素for (int i = arr.length - 1; i > 0; i--) {//将堆顶元素与末尾元素进行交换int temp = arr[i];arr[i] = arr[0];arr[0] = temp;//重新对堆进行调整adjustHeap(arr, 0, i);}}/*** 调整堆* @param arr 待排序列* @param parent 父节点* @param length 待排序列尾元素索引*/private static void adjustHeap(int[] arr, int parent, int length) {//将temp作为父节点int temp = arr[parent];//左孩子int lChild = 2 * parent + 1;while (lChild < length) {//右孩子int rChild = lChild + 1;// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点if (rChild < length && arr[lChild] < arr[rChild]) {lChild++;}// 如果父结点的值已经大于孩子结点的值，则直接结束if (temp >= arr[lChild]) {break;}// 把孩子结点的值赋给父结点arr[parent] = arr[lChild];//选取孩子结点的左孩子结点,继续向下筛选parent = lChild;lChild = 2 * lChild + 1;}arr[parent] = temp;}