6.1、堆排序

大顶堆：当前节点的元素值大于或等于其左右子节点的值；
小顶堆：当前节点的元素值小与其左右子节点的值。

堆排序的具体步骤：
step1：首先将一个数组按照需求（升序/降序）构造成大顶堆和小顶堆——实现数组的最大值为树结构的根节点。
step2：将堆顶的元素（即数组的首位元素）与数组的末尾元素进行交换，将堆顶的元素沉积到末端，完成一次排序，此时还剩下n-1个数未进行排序。
step3：以剩下的n-1个数的数组，重新构造成大顶堆/小顶堆，然后执行step2，此时还剩下n-2个元素未进行排序。
step4：循环step3和step2，直至数组完成排序。
构建大顶堆的具体方法：
step1：首先找到最后一个非叶子节点，对其节点值进行更新，最后一个非叶子节点的下标索引为arr.length/2-1。
step2：首先定义一个变量temp将当前元素进行保存 。
step3：寻找当前节点的左子节点，判断是否越界
step4：判断当前节点的左子节点和右子节点的大小，如果右子节点的值比左子节点的值大，就指向较大的右子节点。
step5：比较当前节点的值和其子节点的大小，若其子节点的值更大，则对当前节点进行更新，将较大的值进行赋值给当前节点，并指向赋值的子节点，对其值进行重新考虑。
step6：由于对子节点的值进行了更新，可能会对其子节点的大顶堆产生影响，判断其子节点是否为大顶堆，若不是，重新进行大顶堆构造，循环，直至越界。将当前节点的值赋值给子节点。

  1.     //将当前数组变成一个大顶堆
  2.     private static void BigHeap(int[] arr, int k, int length) {
  3.         //先取出当前元素
  4.         int temp=arr[k];
  5.         //首先找到当前数组元素的左子节点，判断是否越界
  6.         for (int i = 2*k+1; i <length ; i=2*i+1) {
  7.                 //如果不越界，则判断当前节点的左子节点和右子节点的大小
  8.                 if (arr[i]<arr[i+1]&&i+1<length){
  9.                     //指向右子节点
  10.                     i++;
  11.                 }
  12.                 //判断当前节点与Math.max（左子节点，右子节点）
  13.                 if (arr[i]<temp){
  14.                     break;
  15.                 }else {
  16.                     //将左子节点和右子节点的值赋给当前节点
  17.                     arr[k]=arr[i];
  18.                     k=i;
  19.                 }
  20.             }
  21.             arr[k]=temp;
  22.         }