JAVA十大排序算法之堆排序详解

目录

• 堆排序
  • 知识补充
    • 二叉树
    • 满二叉树
    • 完全二叉树
    • 二叉堆
  • 代码实现
  • 时间复杂度
  • 算法稳定性
  • 思考
• 总结

public class HeapSort {
    public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};
    public static int[] sort(int[] array) {
        //数组的长度
        int length = array.length;
        if (length < 2) return array;
        //首先构建一个最大堆
        buildMaxHeap(array);
        //调整为最大堆之后，顶元素为最大元素并与微元素交换
        while (length > 0) {//当lenth <= 0时，说明已经到堆顶
            //交换
            swap(array, 0, length - 1);
            length--;//交换之后相当于把树中的最大值弹出去了，所以要--
            //交换之后从上往下调整使之成为最大堆
            adjustHeap(array, 0, length);
        }
        return array;
    }
    //对元素组构建为一个对应数组的最大堆
    private static void buildMaxHeap(int[] array) {
        //在之前的分析可知，最大堆的构建是从最后一个非叶子节点开始，从下往上，从右往左调整
        //最后一个非叶子节点的位置为：array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            //调整使之成为最大堆
            adjustHeap(array, i, array.length);
        }
    }
    /**
     * 调整
     * @param parent 最后一个非叶子节点
     * @param length 数组的长度
     */
    private static void adjustHeap(int[] array, int parent, int length) {
        //定义最大值的索引
        int maxIndex = parent;
        //parent为对应元素的位置（数组的索引）
        int left = 2 * parent + 1;//左子节点对应元素的位置
        int right = 2 * (parent + 1);//右子节点对应元素的位置
        //判断是否有子节点，再比较父节点和左右子节点的大小
        //因为parent最后一个非叶子节点，所以如果有左右子节点则节点的位置都小于数组的长度
        if (left < length && array[left] > array[maxIndex]) {//左子节点如果比父节点大
            maxIndex = left;
        }
        if (right < length && array[right] > array[maxIndex]) {//右子节点如果比父节点大
            maxIndex = right;
        }
        //maxIndex为父节点，若发生改变则说明不是最大节点，需要交换
        if (maxIndex != parent) {
            swap(array, maxIndex, parent);
            //交换之后递归再次调整比较
            adjustHeap(array, maxIndex, length);
        }
    }
    //交换
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}