排序-堆排序

1 描述

• 是一棵完全二叉树，并且每个节点的值都不小于孩子就是大顶堆，每个节点都不大于孩子就是小顶堆。
  • 因为是完全二叉树，所以可以用连续数组表示。

1.1 思路

• 基本了解
  • i 父子节点计算
    • 父 (i - 1) / 2
    • 左儿 2 * i + 1
    • 右儿 2 * i + 2
• 1 首先把无序数据构建成一个大顶堆/小顶堆
  • 从 倒数第二层 开始修正 ... 到跟节点
    • 修正就是看 parent 是否是 最大的
      • 是 就不需要修正
      • 否 就是找出 三节点中的最大，与parent 替换，然后 递归修正被替换节点。
• 2 把a[0]与a[n-1]交换
  • n = 要构建堆的数组长度。
• 3 调整a[0] - a[n - 2]树的结构，让他重新变成大顶堆/小顶堆
• 4 重复第二步操作

1.2 复杂度

• 时间复杂度
  • 最好 最坏 平均 都是O(NlgN)
• 空间辅助度
  • O(1)

案例

/**
 * HeapSort class
 *
 * @author 格林
 * @date 2021-05-27
 */
public class HeapSort {

    // 局部修正
    public static void  correction(long arr[],int n, int i) {
        if(i >= n) {
            return ;
        }
        int leftChild = i * 2 + 1;
        int rightChild = i * 2 + 2;
        int max = i;
        if(leftChild < n && arr[leftChild] > arr[max]) {
            max = leftChild;
        }
        if(rightChild < n && arr[rightChild] > arr[max]) {
            max = rightChild;
        }
        if(i != max) {
            swap(arr,i,max);
            // 修正交换了的子树，保证是大顶堆。
            correction(arr,n,max);
        }

    }

    /**
     * 从倒数第二层开始构建，构建大顶堆
     * @param arr
     */
    public static void buildHeap(long[] arr) {
        int startIndex =  (arr.length - 2 ) / 2;
        for(int i = startIndex; i >= 0; i --) {
            correction(arr,arr.length, i);
        }

    }

    /**
     * 堆排序
     * @param arr
     */
    public static  void sortHeap(long[] arr) {
        // 构建大顶堆
        buildHeap(arr);
        for(int i = arr.length - 1; i >= 0; i -- ) {
            swap(arr,0,i);
            correction(arr,i ,0);

        }
    }
    public static void main(String[] args) {
        //long[] arr = {1,5,2,3,11,7,2222,333,11,2,3,4};
        long[] arr = {10,2,1,3,4,5,11,2312,321321};
        System.out.println("原始前" + Arrays.toString(arr));
        sortHeap(arr);
       System.out.println("排序后" +  Arrays.toString(arr));
    }

    public static  void swap(long[] arr, int start, int end) {
        long t = arr[start];
        arr[start] = arr[end];
        arr[end] = t;
    }
}