1.4 代码演示

package com.zhuang.algorithm;

import java.util.Arrays;

/**
 * @Classname HeapSort
 * @Description 堆排序
 * @Date 2021/6/13 17:09
 * @Created by dell
 */

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
        heapSort(arr);
        System.out.println("堆排序以后的序列为:");
        System.out.println(Arrays.toString(arr));
    }
    //定义堆排序的方法

    /**
     * @param arr 数组
     */
    public static void heapSort(int[] arr) {
        int temp = 0;
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //经过第一次调整 此时最大值位于大顶堆的根节点
        for (int j = arr.length - 1; j >= 1; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            System.out.println(Arrays.toString(arr));
            //递归进行大顶堆的下次调整
            //此时从根节点 i=0开始
            adjustHeap(arr, 0, j);
        }
    }
    //定义将处于i位置的子树调整成大顶堆的方法

    /**
     * @param arr 待排序的数组
     * @param i   非叶子子节点
     * @param len 构建大顶堆的数组参与的元素的长度
     */
    public static void adjustHeap(int[] arr, int i, int len) {
        //定义临时变量
        int temp = arr[i];
        // 由于数组下标为0，则若i为某个非叶子节点，左子节点为i*2+1;右子节点为i*2+2
        // 构建大顶堆从左到右，自下往上进行
        //下次继续选择该节点的左子节点
        for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {
            //在未越界的情况下，在未越界的情况下:如果当前非叶子节点的左子节点的值小于右子节点的值,则选择最大值,成为新的非叶子父节点
            if (k + 1 < len && arr[k] < arr[k + 1]) {
                //选择右子节点
                k += 1;
            }
            //进行比较出的左右子节点的最大值和当前父节点的大小进行比较，完成大顶堆
            if (arr[k] > temp) {
                //将arr[i]设置为最大值
                arr[i] = arr[k];
                //将i置为k,即下一轮int temp = arr[i] = arr[k],继续循环比较
                i = k;
            } else {
                break;
            }
        }
        //for循环后，将以i为父节点的最大值放在顶部
        arr[i] = temp;
    }
}

[50, 77, 82, 46, 65, 20, 51, 30, 18, 97]
[18, 77, 51, 46, 65, 20, 50, 30, 82, 97]
[30, 65, 51, 46, 18, 20, 50, 77, 82, 97]
[50, 46, 51, 30, 18, 20, 65, 77, 82, 97]
[20, 46, 50, 30, 18, 51, 65, 77, 82, 97]
[18, 46, 20, 30, 50, 51, 65, 77, 82, 97]
[18, 30, 20, 46, 50, 51, 65, 77, 82, 97]
[20, 18, 30, 46, 50, 51, 65, 77, 82, 97]
[18, 20, 30, 46, 50, 51, 65, 77, 82, 97]
堆排序以后的序列为:
[18, 20, 30, 46, 50, 51, 65, 77, 82, 97]