关于Java排序算法-堆排序（Heap Sort）

堆排序是利用堆的特性进行排序的过程。
堆排序：输出堆顶的最小(大)值后，使剩余的n-1个元素序列重新再建成堆，则可得到原序列的次小(大)值。反复进行可得到一个有序序列，整个过程称为堆排序。
堆排序分为两个步骤：
根据初始输入数据，形成初始堆；
通过一系列的记录交换和重新调整堆进行排序。

public class HeapSort {
  
  // 主函数
  public static void main(String[] args) {
    int[] arr = { 27, 83, 96, 38, 11, 9 };
    sort(arr);
  }
  
  // 排序
  public static void sort(int[] arr) {
    // arr为待排序表， n为表的长度
    int n = arr.length;
    
    display("原始数据 : ", arr);
    
    // 建堆函数：根据堆的定义，从最后一个非终端结点（第(n-2)/2个）开始筛选，直至到根结点为止。这一过程使得初始序列 arr[0..n-1] 建成一个堆。
    // 构建大顶堆
    for (int i = (n - 2) / 2; i >= 0; i--) {
      adjustHeap(arr, i, n);
      display("构建中: ", arr);
    }
    
    display("大顶堆 : ", arr);
    
    // 调整堆结构
    // 交换堆顶元素与末尾元素
    for (int j = n - 1; j > 0; j--) {
      // 将堆顶元素与末尾元素进行交换
      swap(arr, 0, j);
      // 重新对堆进行调整
      adjustHeap(arr, 0, j);
      display("排序中: ", arr);
    }
    
    display("排序结果: ", arr);
  }
  
  // 调整大顶堆
  public static void adjustHeap(int[] arr, int i, int length) {
    // 先取出当前元素i
    int temp = arr[i];
    
    // 从i结点的左子结点开始，也就是2i+1处开始
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
      
      // 如果左子结点小于右子结点，k指向右子结点
      if (k + 1 < length && arr[k] < arr[k + 1]) {
        k++;
      }
      
      // 如果子节点大于父节点，将子节点值赋给父节点。不用进行交换。
      if (arr[k] > temp) {
        arr[i] = arr[k];
        i = k;
      } else {
        break;
      }
    }
    
    // 将temp值放到最终的位置
    arr[i] = temp;
  }
  
  // 交换元素
  public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

  // 显示
  public static void display(String str, int[] arr) {
    System.out.println(str);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
}

原始数据 :
27 83 96 38 11 9
构建中:
27 83 96 38 11 9
构建中:
27 83 96 38 11 9
构建中:
96 83 27 38 11 9
大顶堆 :
96 83 27 38 11 9
排序中:
83 38 27 9 11 96
排序中:
38 11 27 9 83 96
排序中:
27 11 9 38 83 96
排序中:
11 9 27 38 83 96
排序中:
9 11 27 38 83 96
排序结果:
9 11 27 38 83 96