堆排序

import java.util.Arrays;

public class My {
    public void heapSort(int[] arr) {
        // 前提：根节点为0号结点，结点总数为n
        // 若当前结点为i,则其左孩子为2*i+1,右孩子为2*i+2
        // 最后一个非叶子结点为n/2-1，即(n-1-1)/2，父节点=(左/右孩子结点-1)/2
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {  //初始化调整为大根堆
            siftDown(arr, i, n - 1);
        }
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            siftDown(arr, 0, i - 1);
        }
    }

    public void siftDown(int[] arr, int p, int last) {
        int i = p;
        int j = 2 * i + 1;
        while (j <= last) {
            if (j < last && arr[j] < arr[j + 1]) {
                j++;
            }
            if (arr[i] < arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }
    }

    public static void main(String[] args) {
        My my = new My();
        int[] arr = {4, 46, 54, 546, 4, 44, 1, 6, 56, 31, 54, 41};
        my.heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}