堆排序的实现

使用大顶锥实现升序排序，二叉堆的详细操作见以前的文章

步骤如下：

• 先构建大顶堆
• 然后循环删除堆顶元素（交互首尾元素），因为大顶堆的堆顶元素就是最大值
• 最后得到的就是升序的数组列表

public class HeapSortTest {

    public static void main(String[] args) {
        int[] arr = {32, 32, 12, 3, 4, 5, 12, 1, 4, 6};
        heapSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 下沉操作
     */

    public static void downAdjust(int[] arr, int index, int length) {
        int parent = index;
        int child = parent * 2 + 1;
        int tmp = arr[parent];
        while (child < length) {
            //获取两个中间较大的值
            if (child + 1 < length && arr[child + 1] > arr[child]) {
                child++;
            }
            if (tmp >= arr[child]) {
                break;
            }
            arr[parent] = arr[child];
            parent = child;
            child = child * 2 + 1;
        }
        arr[parent] = tmp;
    }


    /**
     * 构建大顶堆，利用非子叶节点依次下沉完成构建
     * @param arr
     */
    public static void buildMaxHeap(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
    }

    public static void heapSort(int[] arr, int length) {
        //构建大顶堆
        buildMaxHeap(arr);
        //交换头尾元素
        for (int i = length - 1; i > 0; i--) {
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            downAdjust(arr, 0, i);
        }
    }
}