堆排序

堆排序
    首先堆排序分为两个过程，建堆和调整堆，其中建堆过程中也要用到调整堆，堆排序本质上是一个选择排序，是一个不稳定排序。
    堆排序的核心是调整堆，每次调整从最后一个叶节点的父节点开始，每次拿父节点和其左右子节点比较，将子节点中比较大的节点和父节点进行交换，然后节点依次递增，像这样从下往上进行调整；一次调整结束后，此时堆顶元素为最大值，将堆顶元素与最后一个元素进行交换，重新开始调整。
    首先要找到调整的起点，也就是最后一个叶子节点的父亲节点，为(array.length-2)/2，比如数组长度为7，其最后一个叶子节点的父亲节点为(7-2)/2=2（下标从0开始）；

时间复杂度
    堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

public class HeapSort {
    /**
     *
     * @param array 数组元素
     * @param k  父节点下标
     * @param length
     */
    public static void adjust(int[] array,int k,int length){
        //父节点
        int temp=array[k];
        for (int i=2*k;i<length;i=2*i){
           // System.out.println("Parent"+array[k]);
            //调整
            if(i<length&&array[i]<array[i+1]){
                //找到子节点大的下标
                i++;
            }
            //如果父节点比子节点大，退出
            if (temp>=array[i]){
                break;
            }
            //将子节点大的元素上移
            array[k]=array[i];
            k=i;
        }
        array[k]=temp;
    }
    /**
     *  建立一个大根堆
     * @param array
     * @return
     */
    public static int [] buildHeap(int [] array){
        for (int i=(array.length-2)/2;i>=0;i--){
            adjust(array,i,array.length-1);
        }
        return array;
    }

    /**
     * 排序算法
     * @param array
     * @return
     */
    public static int [] HeapSort(int [] array){
        //建立大根堆
        array=buildHeap(array);
        for(int i=array.length-1; i>0; i--){
            //将堆顶元素与最后一个元素交换
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            //进行调整
            adjust(array,0,i-1);
        }
        return array;
    }

    public static void main(String[] args) {
        int [] array={10,0,7, 5,4, 6, 3, 2, 1};
       HeapSort(array);
        //buildMaxHeap(array);
        for (int i:array){
            System.out.print(i);
        }
    }
}