package better.amy.sort;/** * 堆排序实现 *  * @author zhujinrong *  */public class HeapSort {    /**     * 构造大堆 大根堆排序的结果是升序     *      * @param a     *            数组a     * @param m     *            起始位置     * @param n     *            结束位置     */    private static void heapAdjustMax(int a[], int m, int n) {        int t = a[m];        for (int i = 2 * m + 1; i <= n; i = 2 * i + 1) {            if (i < n && a[i + 1] > a[i]) {                i++;            }            if (t < a[i]) {                a[m] = a[i];                m = i;            }        }        a[m] = t;    }    /**     * 升序堆排序     *      * @param a     *            待排序数组     */    public static void heapSortAsc(int a[]) {        if (a == null) {            return;        }        int n = a.length;        for (int i = n / 2 - 1; i >= 0; i--) {            heapAdjustMax(a, i, n - 1);        }        for (int i = n - 1; i > 0; i--) {            int t = a[i];            a[i] = a[0];            a[0] = t;            heapAdjustMax(a, 0, i - 1);        }    }    /**     * 从下标m,到n，将其调整为小堆 小根堆排序结果是降序（或者说是非升序）     *      * @param a     *            待排序数组     * @param m     *            起始位置     * @param n     *            结束位置     */    public static void heapAdjustMin(int[] a, int m, int n) {        int t = a[m];        for (int i = 2 * m + 1; i <= n; i = 2 * i + 1) {            if (i < n && a[i + 1] < a[i]) {                i++;            }            if (t > a[i]) {                a[m] = a[i];                m = i;            }        }        a[m] = t;    }    /**     * 降序堆排序     *      * @param a     *            待排序数组     */    public static void heapSortDesc(int a[]) {        if (a == null) {            return;        }        int n = a.length;        for (int i = n / 2 - 1; i >= 0; i--) {            heapAdjustMin(a, i, n - 1);        }        for (int i = n - 1; i > 0; i--) {            int t = a[i];            a[i] = a[0];            a[0] = t;            heapAdjustMin(a, 0, i - 1);        }    }}