堆排序 java实现

堆排序就是一种特殊的选择排序，借助顺序二叉树大顶堆/小顶堆的特性，每次将根节点与末尾节点交换值，再将出末尾节点之外的节点重新构造大顶堆/小顶堆，直到未排序的数为1(该值为最大/最小值)时结束排序。

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9,-12,1,-895,1000};
        headSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void headSort(int[] arr)
    {
        int temp;
        //讲顺序二叉树调整为一个大顶堆
        for (int i = arr.length/2 -1; i >= 0; i--) {
            getBigHeap(arr,i,arr.length);
        }

        //排序，每次将队首(最大值)放到队尾
        for (int j = arr.length-1; j > 0 ; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            //再次调整为大顶堆结构
            //此时因为是在原有的大顶堆的基础上进行调整的
            //所以每次只需调整索引0的位置即可
            getBigHeap(arr,0,j);
        }
    }

    
    public static void getBigHeap(int[] arr,int index,int len)
    {
        int temp = arr[index];
        //从该非叶子节点的左孩子开始遍历
        for (int i = 2*index+1; i < len; i = 2*i+1) {
            //比较左右节点的大小
            if (i+1arr[i]){
                i++;
            }
            //比较该非叶子节点的值与其左右孩子的大小
            // 若小于，则赋值，并将索引定位到其子节点进行下一轮调整
            // 若大于，则直接结束循环——原因:每次传入的索引均为未调整过的首个非叶子节点，大于则说明该索引对应的值大于其子树的所有值，无需再进行遍历
            if(arr[i] > temp)
            {
             arr[index] = arr[i];
             index = i;
            }else
            {
                break;
            }
        }
        //for循环结束后，参数中的index已经是该子树中的最大值
        //需要将其原来的值赋值给其子节点。
         arr[index] = temp;
    }
}