参考文章：
https://www.cnblogs.com/guoyaohua/p/8600214.html 十大经典排序算法最强总结（含JAVA代码实现）
https://mp.weixin.qq.com/s/3krwgrzB6EV4HU7wI0Rm4A 堆排序就这么简单
堆排序分析：
平均时间复杂度最好情况最坏情况空间复杂度排序方式稳定性O（n*logn）O（n*log n）O（n*log n）O（1）In-place不稳定堆排序原理：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
温馨提示：算法描述，排序原理搞不懂，先把最大（小）堆搞明白了，然后再看这篇文章。
堆排序算法描述：
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
堆排序原理图解：
Java 代码实现：
代码一：
package com.sorting.algorithm; public class HeapSort { public static int[] heapSort(int[] array){ int n = array.length; // 把数组堆化 heapify， 创建最大堆 for (int i = (n-1-1)/2; i >= 0; i--) { siftDown(array,n,i); } // 将创建好的最大堆最大值放到数组最后，并重建除最大值以外的数组，建立最大堆，循环或递归进行 for (int i = n-1; i > 0; i--) { swap(array,0,i); siftDown(array,i,0); } return array; } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } // 堆中原始的下沉操作 private static void siftDown2(int[] array, int n, int k) { while(2*k+1 < n){ // j 代表左右子树最大值的下标 int j = 2*k +1; if(j+1 < n && array[j] < array[j+1]) j++; // 如果父节点 大于 左右子树节点就跳出循环 if(array[j] < array[k]) break; // 将父节点和左右子树中的最大值交换位置 swap(array, k, j); // 迭代看子树是否需要下沉操作 k=j; } } // 堆中改进的下沉操作 private static void siftDown(int[] array, int n, int k) { int e = array[k]; while(2*k+1 < n){ int j = 2*k +1; if(j+1 < n && array[j] < array[j+1]) j++; if(array[j] < array[k]) break; array[k] = array[j]; k=j; } array[k] = e; } public static void printArr(int[] array){ for (int i = 0; i < array.length; i++) { if(i != array.length-1) System.out.print(array[i] + ","); else System.out.println(array[i]); } } public static void main(String[] args) { int[] array = { 58,36,70,22,88,64,1,32 }; System.out.println("排序之前："); printArr(array); System.out.println("-------------------------------"); System.out.println("排序过程"); heapSort(array); System.out.println("-------------------------------"); System.out.println("排序之后:"); printArr(array); } }
代码二：
package com.sorting.algorithm; public class HeapSort2 { // 用来记录变化的数组长度 private static int len; public static int[] heapSort(int[] array){ len = array.length; // 将数组堆化 buildMaxHeap(array); // 将最大堆中的最大值放大数组的后面，数组长度减一，并重建最大堆 ，循环遍历，知道完成排序 while(len > 0){ printArr(array); swap(array,0,len-1); len--; printArr(array); adjustHeap(array,0); } return array; } // 调整最大堆，使它符合最大堆的性质 private static void adjustHeap(int[] array, int i) { int maxIndex = i; if(2*i <len && array[maxIndex] < array[2*i]) maxIndex = 2*i; if(2*i+1 <len && array[maxIndex] < array[2*i+1]) maxIndex = 2*i+1; // 递归调用 adjustHeap ，让父节点，左右子树都符合最大堆的性质 if(maxIndex != i){ swap(array, i, maxIndex); adjustHeap(array, maxIndex); } } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } // 将数组堆化 private static void buildMaxHeap(int[] array) { int n = array.length; for(int i = n/2; i >= 0; i--){ adjustHeap(array,i); } } public static void printArr(int[] array){ for (int i = 0; i < array.length; i++) { if(i != array.length-1) System.out.print(array[i] + ","); else System.out.println(array[i]); } } public static void main(String[] args) { int[] array = { 58,36,70,22,88,64,1,32 }; System.out.println("排序之前："); printArr(array); System.out.println("-------------------------------"); System.out.println("排序过程"); heapSort(array); System.out.println("-------------------------------"); System.out.println("排序之后:"); printArr(array); } }
堆排序代码测试：
代码一：
代码二：
