堆排序

预备知识

1. 线性存储二叉树，即用数组来存储树（广度遍历存储）
2. 根节点为i，则左节点arr[2i+1]，右节点arr[2i+2]
3. 最后一个非叶子节点开始（arr.length/2 - 1）
4. 应用于完全二叉树，完全二叉树概念

基本介绍

1. 是一种选择排序，最好、最坏、平均时间复杂度为O(nlogn),不稳定排序
2. 完全二叉树，每个节点的值都大于子节点的值，子节点值没有大小关系，是大顶堆，反之小顶堆
3. 大顶堆特点：arr[i]>=arr[2i+1] && arr[i] >= arr[2i+2] // i为数组下标，从0开始 ，小顶堆反之
4. 升序采用大顶堆，降序采用小顶堆

基本思想

1. 构建大顶堆
2. 根节点（即最大值）与末尾元素交换
3. 将剩下的元素重新构建大顶堆
4. 重复直至剩一个元素

思路步骤

1. 构建大顶堆，从下往上，从最后一个非叶子节点开始（arr.length/2 - 1）
2. 选择排序，每次都找一个最大的值放到最末尾

实现

1. 递归版本 2.非递归版本

public class HeapSort {

  public static void main(String[] args) {
    int arr[] = {4, 6, 8, 5, 9};
    heapSort(arr);
    System.out.println(Arrays.toString(arr));
  }

  public static void heapSort(int[] arr) {
    for (int i = arr.length/2 - 1; i >= 0; i--) {
      adjustHeap(arr, i, arr.length);
    }

    int temp;
    for(int i = arr.length -1; i >0; i--) {
        temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        adjustHeap2(arr, 0, i);
    }
  }

  /**
   * 非递归版本
   * 把i以下的部分调整为大顶堆,从下往上，以左右节点为根的子树都已经是大顶堆了
   * @param arr 被排序的数组
   * @param i 非叶子节点的索引
   * @param length 剩下未排序的部分
   */
  public static void adjustHeap(int[] arr, int i, int length) {
    int temp = arr[i];
    for (int k = 2 * i + 1; k < length; k = 2*k+1) {
      // 找到最大的
      if(k+1 < length && arr[k] < arr[k+1]) {
        k++;
      }
      // 交换
      if(arr[k] > temp) {
        // arr[i]变成了最大的值，那么temp应该放在什么位置呢，循环的意义就在于寻找满足大顶堆定义的位置，即i被赋予的新的含义
        arr[i] = arr[k];
        // 此时i的的含义变了，i变成了要被交换的索引
        i = k;
      } else {
        // 找到一个满足大顶堆定义的就行了，用于安放被交换的值，下标是index，不用继续往下找了
        break;
      }
      arr[i] = temp;
    }
  }

// 递归版本
  public static void adjustHeap2(int[] arr, int i, int length) {
    int left = 2*i + 1;
    int right = left + 1;
    int maxIndex = i;
    int temp = arr[i];
    // 找到最大的
    if(left < length && arr[left] > arr[maxIndex]) {
      maxIndex = left;
    }
    if(right < length && arr[right] > arr[maxIndex]) {
      maxIndex = right;
    }
    // 交换
    if(arr[i] < arr[maxIndex]) {

      arr[i] = arr[maxIndex];
      arr[maxIndex] = temp;
      adjustHeap2(arr,maxIndex, length);
    }
  }
}