算法描述：

堆在邏輯上是一個(gè)完全二叉樹(shù)，而在物理上其實(shí)是一個(gè)數(shù)組/向量。若非葉子結(jié)點(diǎn)的坐標(biāo)為i，則其左孩子結(jié)點(diǎn)的坐標(biāo)為（2i+1），其右孩子結(jié)點(diǎn)的坐標(biāo)為（2i+2）。

① 將待排序的序列構(gòu)造成一個(gè)大頂堆，根據(jù)大頂堆的性質(zhì)，當(dāng)前堆的根節(jié)點(diǎn)（堆頂）就是序列中最大的元素；

② 將堆頂元素和最后一個(gè)元素交換，然后將剩下的節(jié)點(diǎn)重新構(gòu)造成一個(gè)大頂堆；

③ 重復(fù)步驟2，如此反復(fù)，從第一次構(gòu)建大頂堆開(kāi)始，每一次構(gòu)建，我們都能獲得一個(gè)序列的最大值，然后把它放到大頂堆的尾部。最后，就得到一個(gè)有序的序列了。

對(duì)于大頂堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

對(duì)于小頂堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

package com.lin;

public class HeapSort {
    public static void main(String[] args) {
        System.out.println("=====堆排序=====");
        int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println("排序之前：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

        //堆排序
        array = heapSort(array);

        System.out.println("\n");
        System.out.println("排序之后：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }


    public static int[] heapSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return arr;
        }
        int len = arr.length;
        // 構(gòu)建大頂堆，這里其實(shí)就是把待排序序列，變成一個(gè)大頂堆結(jié)構(gòu)的數(shù)組
        buildMaxHeap(arr, len);

        // 交換堆頂和當(dāng)前末尾的節(jié)點(diǎn)，重置大頂堆
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private static void buildMaxHeap(int[] arr, int len) {
        // 從最后一個(gè)非葉節(jié)點(diǎn)開(kāi)始向前遍歷，調(diào)整節(jié)點(diǎn)性質(zhì)，使之成為大頂堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private static void heapify(int[] arr, int i, int len) {
        // 先根據(jù)堆性質(zhì)，找出它左右節(jié)點(diǎn)的索引
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 默認(rèn)當(dāng)前節(jié)點(diǎn)（父節(jié)點(diǎn)）是最大值。
        int largestIndex = i;
        if (left < len && arr[left] > arr[largestIndex]) {
            // 如果有左節(jié)點(diǎn)，并且左節(jié)點(diǎn)的值更大，更新最大值的索引
            largestIndex = left;
        }
        if (right < len && arr[right] > arr[largestIndex]) {
            // 如果有右節(jié)點(diǎn)，并且右節(jié)點(diǎn)的值更大，更新最大值的索引
            largestIndex = right;
        }

        if (largestIndex != i) {
            // 如果最大值不是當(dāng)前非葉子節(jié)點(diǎn)的值，那么就把當(dāng)前節(jié)點(diǎn)和最大值的子節(jié)點(diǎn)值互換
            swap(arr, i, largestIndex);
            // 因?yàn)榛Q之后，子節(jié)點(diǎn)的值變了，如果該子節(jié)點(diǎn)也有自己的子節(jié)點(diǎn)，仍需要再次調(diào)整。
            heapify(arr, largestIndex, len);
        }
    }

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

}

運(yùn)行結(jié)果

運(yùn)行結(jié)果