1. 堆排序的基本介绍

2. 堆排序思想

3. 代码实现

public class HeapSort {
    public static void main(String[] args) {
        int arr[] = {4,6,8,5,9};
        int temp = 0;
        //分步完成
//        adjustHeap(arr,1,arr.length);
//        System.out.println("第一次调整之后："+ Arrays.toString(arr));
//
//        adjustHeap(arr,0,arr.length);
//        System.out.println("第二次调整之后："+Arrays.toString(arr));

        //将无序序列构成一个堆
        for(int i = arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }

        //将堆元素与末尾元素交换，将最大元素调到数组末端
        for(int j=arr.length-1;j>0;j--){
            //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            //从0开始是因为只需要把堆顶元素排好就行了
            adjustHeap(arr,0,j);
        }
        System.out.println("数组为："+Arrays.toString(arr));
    }

    //编写一个堆排序的方法
    public static void heapSort(int arr[]){
        System.out.println("堆排序");
    }

    /**
     * 将以i为非叶子节点的数调整为大顶堆
     * @param arr
     * @param i 非叶子节点在数组中的索引
     * @param length 表示对多个元素进行调整,legnth在逐渐减少
     */
    public static void adjustHeap(int arr[],int i,int length){
        //先取出当前元素的值，保存在临时变量中
        int temp = arr[i];

        //开始调整
        for(int k=i*2+1;k<length;k=k*2+1){
            if(k+1<length && arr[k]<arr[k+1]){//说明左子节点的值小于右子节点的值
                k++;//k指向右子节点
            }
            if(arr[k]>temp){//如果子节点大于父节点
                arr[i] = arr[k];//把较大的值赋给当前节点
                i=k;//i指向k，继续循环
            }else{
                break;
            }
        }
        arr[i] = temp;
    }
}