堆排序

写了一个堆排序代码，支持升序和降序

package code;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = new int[] {2,1,4,7,4,3,9,8};
        sort(array, false);
        System.out.println(Arrays.toString(array));
        sort(array, true);
        System.out.println(Arrays.toString(array));
    }

    //排序主函数
    //flag, true升序, false降序
    public static void sort(int[] array, boolean flag) {
        //从最后一个叶子节点开始调整堆,直到第一个节点
        for (int i = array.length/2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length, flag);
        }

        //从后往前, 将堆顶元素换到堆的尾部, 然后调整堆
        for (int i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            adjustHeap(array, 0, i, flag);
        }
    }

    //调整堆
    public static void adjustHeap(int[] array, int i, int length, boolean flag) {
        int tmp = array[i];

        //k是i的左节点, k+1是右节点
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            //拿到左子节点和右子节点中最大的(升序), 或最小的(降序)
            if ((flag && k+1 < length && array[k] < array[k+1])
                || (!flag && k+1 < length && array[k] > array[k+1])) {
                k++;
            }
            //如果比待调整节点大(升序), 或者比待调整节点小(降序), 交换; 然后继续调整子树
            boolean swap = flag ? array[k] > tmp : array[k] < tmp;
            if (swap) {
                swap(array, i, k);
                i = k;
            } else {
                //如果不满足交换条件,结束
                break;
            }
        }
    }

    //交换
    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

}

参考 https://blog.csdn.net/u013384984/article/details/79496052