JAVA⼗⼤排序算法之堆排序详解⽬录堆排序知识补充⼆叉树满⼆叉树完全⼆叉树⼆叉堆代码实现时间复杂度算法稳定性思考总结堆排序这⾥的堆并不是JVM中堆栈的堆，⽽是⼀种特殊的⼆叉树，通常也叫作⼆叉堆。
它具有以下特点：它是完全⼆叉树堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值知识补充⼆叉树树中节点的⼦节点不超过2的有序树满⼆叉树⼆叉树中除了叶⼦节点，每个节点的⼦节点都为2，则此⼆叉树为满⼆叉树。
完全⼆叉树如果对满⼆叉树的结点进⾏编号，约定编号从根结点起，⾃上⽽下，⾃左⽽右。
则深度为k的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为k的满⼆叉树中编号从1⾄n的结点⼀⼀对应时，称之为完全⼆叉树。
特点：叶⼦结点只能出现在最下层和次下层，且最下层的叶⼦结点集中在树的左部。
需要注意的是，满⼆叉树肯定是完全⼆叉树，⽽完全⼆叉树不⼀定是满⼆叉树。
⼆叉堆⼆叉堆是⼀种特殊的堆，可以被看做⼀棵完全⼆叉树的数组对象，⽽根据其性质⼜可以分为下⾯两种：⼤根堆：每⼀个根节点都⼤于等于它的左右孩⼦节点，也叫最⼤堆⼩根堆：每⼀个根节点都⼩于等于它的左右孩⼦节点，也叫最⼩堆如果把⼀个数组通过⼤根堆的⽅式来表⽰（数组元素的值是可变的），如下：由此可以推出：对于位置为 k 的节点，其⼦节点的位置分别为，左⼦节点 = 2k + 1，右⼦节点 = 2(k + 1)如：对于 k = 1，其节点的对应数组为 5左⼦节点的位置为 3，对应数组的值为 3右⼦节点的位置为 4，对应数组的值为 2最后⼀个⾮叶⼦节点的位置为 (n/2) - 1，n为数组长度如：数组长度为6，则 (6/2) - 1 = 2，即位置 2 为最后⼀个⾮叶⼦节点给定⼀个随机数组[35,63,48,9,86,24,53,11]，将该数组视为⼀个完全⼆叉树：从上图很明显的可以看出，这个⼆叉树不符合⼤根堆的定义，但是可以通过调整，使它变为最⼤堆。
如果从最后⼀个⾮叶⼦节点开始，从下到上，从右往左调整，则：通过上⾯的调整，该⼆叉树为最⼤堆，这个时候开始排序，排序规则：将堆顶元素和尾元素交换交换后重新调整元素的位置，使之重新变成⼆叉堆代码实现public class HeapSort {public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};public static int[] sort(int[] array) {//数组的长度int length = array.length;if (length < 2) return array;//⾸先构建⼀个最⼤堆buildMaxHeap(array);//调整为最⼤堆之后，顶元素为最⼤元素并与微元素交换while (length > 0) {//当lenth <= 0时，说明已经到堆顶//交换swap(array, 0, length - 1);length--;//交换之后相当于把树中的最⼤值弹出去了，所以要--//交换之后从上往下调整使之成为最⼤堆adjustHeap(array, 0, length);}return array;}//对元素组构建为⼀个对应数组的最⼤堆private static void buildMaxHeap(int[] array) {//在之前的分析可知，最⼤堆的构建是从最后⼀个⾮叶⼦节点开始，从下往上，从右往左调整 //最后⼀个⾮叶⼦节点的位置为：array.length/2 - 1for (int i = array.length / 2 - 1; i >= 0; i--) {//调整使之成为最⼤堆adjustHeap(array, i, array.length);}}/*** 调整* @param parent 最后⼀个⾮叶⼦节点* @param length 数组的长度*/private static void adjustHeap(int[] array, int parent, int length) {//定义最⼤值的索引int maxIndex = parent;//parent为对应元素的位置（数组的索引）int left = 2 * parent + 1;//左⼦节点对应元素的位置int right = 2 * (parent + 1);//右⼦节点对应元素的位置//判断是否有⼦节点，再⽐较⽗节点和左右⼦节点的⼤⼩//因为parent最后⼀个⾮叶⼦节点，所以如果有左右⼦节点则节点的位置都⼩于数组的长度 if (left < length && array[left] > array[maxIndex]) {//左⼦节点如果⽐⽗节点⼤maxIndex = left;}if (right < length && array[right] > array[maxIndex]) {//右⼦节点如果⽐⽗节点⼤maxIndex = right;}//maxIndex为⽗节点，若发⽣改变则说明不是最⼤节点，需要交换if (maxIndex != parent) {swap(array, maxIndex, parent);//交换之后递归再次调整⽐较adjustHeap(array, maxIndex, length);}}//交换private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}public static void print(int[] array) {for (int i : array) {System.out.print(i + " ");}System.out.println("");}public static void main(String[] args) {print(ARRAY);System.out.println("============================================");print(sort(ARRAY));}}时间复杂度堆的时间复杂度是 O(nlogn)参考：堆排序的时间复杂度分析算法稳定性堆的结构为，对于位置为 k 的节点，其⼦节点的位置分别为，左⼦节点 = 2k + 1，右⼦节点 = 2(k + 1)，最⼤堆要求⽗节点⼤于等于其2个⼦节点，最⼩堆要求⽗节点⼩于等于其2个⼦节点。
