排序算法之堆排序

package com.banmoon.algorithm.order;

import java.util.Arrays;

/**
 * 堆排序
 */
public class Demo08 {

    public static void main(String[] args) {
//        int[] arr = {128, 359, 26, 78, 98, 5, 789, 12, 6, 2};
        int[] arr = {2, 9, 7, 8, 3, 5, 4, 1, 6, 0};
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    private static int[] sort(int[] arr) {
        // 先进行一次大顶推的转换
        int last = (arr.length - 1) / 2;
        for (int i = last; i >= 0; i--) {
            maxHeap(arr, arr.length, i);
        }
        // 将这个根节点与最后的叶子节点进行替换，也就是将最大的数放到了最后
        for (int i = arr.length-1; i > 0; i--) {
            // 替换最前和最后的数
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 替换后，需要将根节点的数进行一次转移，重新变为大顶堆
            maxHeap(arr, i, 0);
        }
        return arr;
    }


    public static void maxHeap(int[] arr, int size, int index){
        // 左节点
        int leftIndex = index*2+1;
        // 右节点
        int rightIndex = index*2+2;
        // 和左右节点进行对比
        int max = index;;
        if(leftIndex < size && arr[leftIndex] > arr[max])
            max = leftIndex;
        if(rightIndex < size && arr[rightIndex] > arr[max])
            max = rightIndex;
        // 进行交换
        if (max != index) {
            int temp = arr[max];
            arr[max] = arr[index];
            arr[index] = temp;
            // 交换位置后，需要再对替换的index向下判断
            maxHeap(arr, size, max);
        }
    }

}