自己实现堆，你能写出堆排序吗？

前言

外援

public static void heapSort(int[] arr) {
    PriorityQueue heap = new PriorityQueue<>();
    for(int i = 0; i < arr.length; i++) {
        heap.offer(arr[i]);
    }
    for(int i = 0; i < arr.length; i++) {
        arr[i] = heap.poll();
    }
}

内功

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static void downAdjust(int[] arr, int parent, int end) {
    int left = parent * 2, right = parent * 2 + 1;
    if(left > end) {
        return;
    }
    if(right <= end && arr[parent] < arr[right] && arr[left] < arr[right]) {
        swap(arr, parent, right);
        parent = right;
    } else if(arr[parent] < arr[left]) {
        swap(arr, parent, left);
        parent = left;
    } else {
        return;
    }
    downAdjust(arr, parent, end);
}

public static void heapSort(int[] arr) {
    for(int i = arr.length / 2; i >= 0; i--) {
        downAdjust(arr, i, arr.length - 1);
    }
    for(int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        downAdjust(arr, 0, i - 1);
    }
}

练习题