堆排序

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {6,5,4,3,2,1};
        heapSort(arr);
    }

    public static void heapSort(int[] arr) {
        System.out.println("堆排序");

        //build heap，共有(n/2-1)非叶子节点，从下往上，从左往右建立大根堆
        for (int i = arr.length/2 -1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //将堆顶元素与莫为元素交换，最大值“沉”到数组末端
        int cnt = 0;
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, j, 0);
            adjustHeap(arr, 0, j);
        }
        System.out.println("数组 = " + Arrays.toString(arr));
    }

    /**升序排列，构建大根堆
     * @param arr:  待调整的数组
     * @param i:    非叶子节点在数组中的索引
     * @param length:   表示待调整的元素的数量
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //k=2*i+1是第i个节点的左子节点；k+1是第i个节点的右子节点
        for (int k = 2 * i + 1; k < length; k = k * 2 +1) {
            if (k+1 < length && arr[k] < arr[k+1]) {
                k += 1;
            }
            if (arr[k] > temp) {    //如果子节点k大于父节点i
                arr[i] = arr[k];
                i = k;
            } else {    //如果当前节点i已经最大，则不用交换（注意，由于是从左到右、从下到上调整大根堆）
                break;
            }
        }
        //当for循环结束，我们将以i为父节点的最大值，放在了最顶端（局部大顶堆）
        arr[i] = temp;  //将temp放到最终的位置
    }

    //交换函数
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

堆排序
数组 = [1, 2, 3, 4, 5, 6]