今天写的这个堆排序算法，用了很久的时间，一是理解编程思想；二是调试出现了诸多的小错误。现在记下来，下不为例。
预备知识
堆排序堆是一种特殊的树形数据结构，即完全二叉树。堆分为大根堆和小根堆，大根堆为根节点的值大于两个子节点的值；小根堆为根节点的值小于两个子节点的值，同时根节点的两个子树也分别是一个堆。
基本思路
算法实现主要分为三个步骤：
1、构造大根堆：将n个元素组成的序列构建为一个大根堆。
根据堆的树形结构，根节点的值要大于两个子节点的值，所以构建一个大根堆的子结构，就是让一个节点的左节点和右节点的值都小于该节点，如果发现左节点或者右节点的值大于该节点的值，那么执行交换操作。设一个非叶子节点的索引是index,那么左节点就是2index+1，右节点是2index+2。当不满足大根堆的子结构时，维护一个局部最大值maxindex索引，并交换到相应的位置。这时看看交换以后，符不符合大根堆的结构，不符合则从maxindex往下递归。
核心代码
private static void heapify(int[] arr, int length, int index) {
int left=2*index+1;
int right=2*index+2;
int maxindex=index;
if(left<length && arr[left] >arr[maxindex]){
maxindex=left;
}
if(right<length && arr[right]>arr[maxindex]){
maxindex=right;
}
if(maxindex!=index){
//交换arr[index]与arr[maxindex]
int temp=arr[index];//
arr[index]=arr[maxindex];
arr[maxindex]=temp;
//递归
heapify(arr,length,maxindex);
}
}
2、调整大根堆：交换堆首和堆尾元素--获得最大元素
第一次heapify以后，其实已经将最大元素找出来了，最大元素位于根节点，arr[0]，那么这时候将堆尾元素与堆首元素交换。
此时处于堆尾的是最大元素，最大元素将不会被改变。现在调用headify，继续构造大根堆。再取出次大的元素，置于堆尾倒数第二个位置。依次类推。
这样循环结束，也就完成了排序。
//调整大根堆
for (int i = arr.length-1; i >=0; i--) {
int temp=arr[0];//交换堆首与堆尾的元素
arr[0]=arr[i];
arr[i]=temp;
heapify(arr,i,0);//将未完成排序的部分,长度为i，继续进行堆排序
}
3、堆排序：
两大步骤：构造大根堆，调整大根堆。需要注意的是构建大根堆的时候首先从最后一个非叶子节点开始，然后遍历非叶子节点。i=0时，到达根节点。
//堆排序
public static void heapsort(int [] arr){
//构建大顶堆, 从最后一个非叶子节点开始
for(int i=arr.length/2-1;i>=0;i--){
heapify(arr,arr.length,i);
}
//调整大根堆
for (int i = arr.length-1; i >=0; i--) {
int temp=arr[0];//交换堆首与堆尾的元素
arr[0]=arr[i];
arr[i]=temp;
heapify(arr,i,0);//将未完成排序的部分,长度为i，继续进行堆排序
}
}
图示说明：
见链接https://www.cnblogs.com/wanglei5205/p/8733524.html。
代码实现
完整代码：
public class HeapSort {
//构建大根堆
private static void heapify(int[] arr, int length, int index) {
int left=2*index+1;
int right=2*index+2;
int maxindex=index;
if(left<length && arr[left] >arr[maxindex]){
maxindex=left;
}
if(right<length && arr[right]>arr[maxindex]){
maxindex=right;
}
if(maxindex!=index){
//交换arr[index]与arr[maxindex]
int temp=arr[index];//交换
arr[index]=arr[maxindex];
arr[maxindex]=temp;
//递归
heapify(arr,length,maxindex);
}
}
//堆排序
public static void heapsort(int [] arr){
//构建大顶堆, 从最后一个非叶子节点开始
for(int i=arr.length/2-1;i>=0;i--){
heapify(arr,arr.length,i);
}
//调整大根堆
for (int i = arr.length-1; i >=0; i--) {
int temp=arr[0];//交换堆首与堆尾的元素
arr[0]=arr[i];
arr[i]=temp;
heapify(arr,i,0);//将未完成排序的部分,长度为i，继续进行堆排序
}
}
public static void main(String[] args) {
int[] arr=new int[]{5,88,45,37,91,26,13,66,50};
heapsort(arr);
System.out.println(Arrays.toString(arr));
}
}