[数据结构与算法]堆排序算法

堆排序

package heapSort;

import java.util.Arrays;

/**
 * @ClassName HeapSort
 * @Description TODO
 * @Author guobenqi
 * @Date 2021/8/19 21:04
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] a = {24, 10, 5, 1, 2, 24, 5};
        heapSort(a);
        System.out.println(Arrays.toString(a)); // 1ms

}

    private static void heapSort(int[] a) {
        //建堆，从倒数第二层建堆，
        for (int i = a.length/2 -1; i >= 0; i--) {
            sortDownHeap(a,a.length-1,i);
        }
        //堆排序，每次将顶节点和数组最后一个进行交换，然后其他进行比较
        for (int i = 0; i < a.length-1; i++) {
            swap(a,0,a.length-1-i);
            sortDownHeap(a,a.length - 2 -i ,0);
        }


    }

    /**
     * 最大堆向下调整
     * @param a
     * @param high 堆的大小,边界
     * @param low 需要调整顺序的元素
     */
    private static void sortDownHeap(int[] a, int high, int low) {

        //保存循环变量
        int k = low;
        while(2*k + 1 <= high){//为什么2k+1,因为堆可能不是完全二叉树，可能缺右孩子节点
            int bigIndex = 2*k+1;//将最大值赋值给节点的右孩子
            if (bigIndex < high){//判断左孩子是否已经超过数组范围
                if (a[2*k+1] <a[2*k+2]){//左孩子和右孩子作比较，选出最大的
                    bigIndex++;
                }
            }

            if (a[bigIndex] > a[k]){//节点跟左右孩子最大值比较，如果节点小，则需要换位置，然后将k赋值最大值，继续循环，否则退出循环
                //交换
                swap(a,k,bigIndex);
                k = bigIndex;
            }else{
                break;
            }

        }
    }

    //交换
    private static void swap(int[] a, int i, int j) {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }


}