堆排序回忆

紧扣堆排序的算法思想：1、建堆：从第一个非叶子节点开始从右至左（从右至左用

                                            一个循环去做）的调整（调整用专门的函数）

                                        2、不断交换堆顶和最后一个元素，调整剩下的序列

public void heapSort(int[] array){

    //从第一个非叶子节点开始从右至左调整其中的小堆

    //构建初始堆

    //array.lentht/2-1表示第一个非叶子节点的序号

    //一直要调整到堆顶，所以i要取到等于0

    for(int i=array.length/2-1;i>=0;i--){

        heapAdjust(array,i,array.length);//调整堆

    }

    //不断交换堆顶和最后一个元素，并调整堆

    for(int i=array.length-1;i>0;i--){

        swap(array, 0, i);

    //这个i刚好可以表示i这一点前面的序列长度

    heapAdjust(array, 0, i);//调整堆

    }

}

    //这个函数功能很纯粹，默认自i以下曾经构建过大顶堆

    //这里不取length这个参数，就无法确定调整剩余序列的长度

    //将i这个节点及以下的所有树调整

public void heapAdjust(int[] array, int i, int length) {

    if(length==1)

        return;

    int temp = array[i];

    for(int k=2*i+1;k<length;k=2*k+1){

        if(k+1<length&&array[k]<array[k+1])

            k++;

        if(array[k]>temp){

            array[i] = array[k];

            i = k;//把k的位置标记为i，k会继续深入

        }else {

            break;

        }

    }

//最终要把移动的i节点的值还原回来

    array[i] = temp;

}

public void swap(int[] array, int a, int b) {

    int temp;

    temp = array[a];

    array[a] = array[b];

    array[b] = temp;

}