堆排序的实现

堆排序是利用完全二叉树的结构特性的一种选择排序算法，其满足完全二叉树的结构特性，排序的步骤如下（最大堆）：

1）初始化堆（按照完全二叉树初始化）
2）从最后一个有子节点的父节点开始往上调整，具体调整方法是父节点必须比子节点大，如果小则互换，父节点需是三个节点中最大的，换过之后的节点需要重新调整
3）完成一遍之后将根元素与最后一个元素互换，最后一个元素不参与下一轮排序调整，然后重复以上动作

下面的图是我按照堆排序的规则手画的流程图以及费好大劲用java实现的堆排序（理解和要实现完全不是一回事>_<!）：

PS：带毛刺表示被减掉不再参与调整的元素

/**
 * Description: 堆排序
 * Author: zhangliangfu
 * Create on: 2019-08-20 9:54
 */
import java.util.Arrays;

public class HeapSort {
    /**
     * 向下调整方法，从最后一个子节点的父节点开始，如果有换位发生，立马对换过位置的子节点进行迭代调整
     * @param a 数组
     * @param i 节点index
     * @param len 数组长度
     */
    public static void adjustNode(int a[], int i, int len){
        if (i<0)return;
        int temp = a[i];  //记录父节点值
        int j;
        for (j = 2*i+1; j < len; j=2*j+1) {
            if (j+1<len&&a[j+1]>a[j]){
                j++;
            }
            if (a[i]<a[j]){
                a[i] = a[j];
                i=j;
                a[j] = temp;
            }else {
                break;
            }
        }
    }

    /**
     * 建立大顶堆
     * @param a
     */
    public static void buildMaxHeap(int a[], int len){
        for (int i = len/2-1; i >=0 ; i--) {
            adjustNode(a,i,len);
        }
    }

    /**
     * 建立大顶堆之后将根元素与最后一个元素互换位置，并将长度减一
     * @param a
     */
    public static void heapSort(int a[]){
        int length = a.length;
        buildMaxHeap(a, length);
        for (int i = length -1; i >=0 ; i--) {
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            buildMaxHeap(a, i);
        }
    }
    public static void main(String[] args) {
        int a[] = {5,9,8,15,7,3,4,2};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}