堆排序(Java)

思想：
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根结点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样就会得到n个元素的次小值，重复上述过程，就能得到有序序列。
图示(黑色表示和此次移动相关，深色表示实际移动的元素)：

代码：

public class HeapSort {
    private HeapSort() { }

    public static void sort(Comparable[] pq) {
        int n = pq.length;
        for (int k = n/2; k >= 1; k--)
            sink(pq, k, n);
        while (n > 1) {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }

    private static void sink(Comparable[] pq, int k, int n) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && less(pq, j, j+1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }

    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i-1];
        pq[i-1] = pq[j-1];
        pq[j-1] = swap;
    }

    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        HeapSort.sort(a);
        show(a);
    }
}

说明:

以上图为例对sort方法进行分析，sort方法中第一个for循环就是构建有序的堆，本例中构造的是大根堆。它的特点就是根结点比不小于其左右孩子，所以初始条件为k=n/2，这样就能找到最后的叶子结点的父结点，对其进行sink操作判断是否需要调整位置。再对sink方法进行分析，while循环是为了防止下标越界，之后通过if对其左右孩子进行比较，取较大那个，然后判断根结点是否比较大的孩子结点大，如果大则进入下个循环，否则交换，经过如此反复就能完成位置调整的工作。调整结束之后就进行排序，由于此时最大值已经调整到了根结点，所以通过和最后的元素进行交换就能提取出最大的元素，然后调用sink方法重建堆。

时间复杂度：平均情况O(nlog2n)，最坏O(nlog2n)，最好O(nlog2n)

空间复杂度：O(1)

稳定性：不稳定，在重建堆的过程中可能发生相同大小数值调换的情况。

这其中的StdOut、StdIn库使用自algs4这个jar包，下载地址：
https://algs4.cs.princeton.edu/code/algs4.jar