堆排序介绍：
①堆排序是利用堆的数据结构设计的一种排序算法，堆排序是一种选择排序，时间复杂度为O(nlogn)，是不稳定排序；
②堆是具有以下性质的完全二叉树：每个节点的值都大于或者等于其左右孩子节点的值，称为大顶堆；（没有要求其左右孩子节点的值谁大谁小）
③每个节点的值都小于或者等于其左右孩子节点的值，称为小顶堆
对堆中的节点按层进行编号，映射到数组中：
大顶堆的特点：
arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2]; //i对应的是第几个节点，i从0开始小顶堆特点：
arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2]; //i对应第几个节点，i从0开始编号一般升序的时候采用大顶堆，降序的时候采用小顶堆
堆排序的基本思想：
①将待排序序列构造成一个大顶堆
②此时，整个序列的最大值就是堆顶的根节点
③将其与末尾元素进行交换，此时末尾就是最大值
④然后将剩余 n-1 个元素重新调整成一个堆，这样会得到n个元素的次小值，反复执行，就能得到一个有序序列
在构建大顶堆的过程中，元素的个数逐渐减少，最后就能得到一个有序序列；
例如： 将{4，6，8，5，9}使用堆排序，将数组升序排序
调整大顶堆代码
/** * 功能：完成将以 i 对应的非叶子节点的树调整成为大顶堆 * * @param arr 待调整的数组 * @param i 表示非叶子节点在数组中的索引 * @param length 表示对多少个元素进行调整，每排序好一趟，length的长度就减1 */ public static void adjustHeap(int[] arr, int i, int length) { int temp = arr[i]; //先取出当前元素的值，保存在临时变量中 //开始调整 //1.k = i * 2 + 1 是i 节点的左子节点 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { if (k + 1 < length && arr[k] < arr[k + 1]) { //说明左子节点的值小于右子节点的值， k++; //k指向右子节点，目的是为了找到左右孩子节点中的最大值 } if (arr[k] > temp) { //如果子节点大于父节点，说明需要调整 arr[i] = arr[k]; //把较大的值作为当前的树的父节点 i = k; // i 指向 k，继续循环比较 } else { break; } } //当for循环结束后，已经将以 i 为父节点的树的最大值，放在了顶端（局部） arr[i] = temp; //将temp值放到调整后的位置 }堆排序代码：
public static void heapSort(int[] arr) { System.out.println("堆排序"); //将无序序列构建成一个大顶堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } //将堆顶元素和末尾元素进行交换，将最大的数放到数组的末尾 //再重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行 调整+交换 步骤，直到整个序列有序 for (int j = arr.length - 1; j >= 0; j--) { //交换 int temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, j); } // System.out.println("调整后的数组 = " + Arrays.toString(arr)); }