堆排序思想

  1. 构建初始堆，将待排序列构成一个大顶堆(或者小顶堆)，升序大顶堆，降序小顶堆；
  2. 将堆顶元素与堆尾元素交换，并断开(从待排序列中移除)堆尾元素。
  3. 重新构建堆。

  4. 重复2~3，直到待排序列中只剩下一个元素(堆顶元素)。

    代码实现

    ```java public class HeapSort {

    public static void main(String[] args) {

    1.  int[] arr = {49, 38, 65, 97, 76, 13, 27, 49};

    // int[] arr = {16, 7, 3, 20, 17, 8};

    1.  heapSort(arr);
    3.  for(int i=0; i<arr.length; i++)
    4.      System.out.print(arr[i] + " ");

    }

    //创建堆 private static void heapSort(int[] arr) {

    1.  //从第一个非叶子节点开始调整，从下至上、从右至左
    2.  //这样可以保证最大的那个数永远会被往上调整
    3.  for(int i=(arr.length-1)/2; i>=0; i--)
    4.  {
    5.      adjustHeap(arr, i, arr.length);
    6.  }
    8.  //交换堆顶元素与末尾元素，调整堆结构
    9.  for(int i=arr.length-1; i>0; i--)
    10.  {
    11.      int temp = arr[0];
    12.      arr[0] = arr[i];
    13.      arr[i] = temp;
    15.      adjustHeap(arr, 0, i);
    16.  }

    }

    //调整堆 /*

    1.  parent：    父节点
    2.  length：    待排序列的尾元素索引

    */ private static void adjustHeap(int[] arr, int parent, int length) {

    1.  //当前要调整的元素
    2.  int temp = arr[parent];
    3.  //左孩子
    4.  int lChild = 2 * parent + 1;
    6.  while(lChild < length)
    7.  {
    8.      //右孩子
    9.      int rChild = lChild + 1;
    10.      if(rChild<length && arr[lChild]<arr[rChild])
    11.          lChild++;    //左孩子指向的是孩子节点里最大的那个
    13.      //如果父结点的值已经大于孩子结点的值，则直接结束
    14.      //因为孩子结点已经是调整过的，可以保证比所有孙子节点都要大
    15.      if(temp >= arr[lChild])
    16.          break;
    18.      //把孩子结点的值赋给父节点
    19.      arr[parent] = arr[lChild];
    21.      //*注：虽然没有进行“交换”的步骤，但是每次比较的对象都是“temp”，所以相当于交换
    22.      //向下调整，防止当前交换影响子堆的结果
    23.      //整个操作相当于孩子结点逐个覆盖父节点，最后将最顶上的祖先结点的值赋给最下面的结点
    24.      parent = lChild;
    25.      lChild = 2 * lChild + 1;
    26.  }
    27.  arr[parent] = temp;

    }

} ```