堆排序

堆排序

• 堆分为大顶堆和小顶堆，大顶堆就是父节点的值大于子节点的值（小顶堆反之）。大顶堆是升序，小顶堆是降序。

• 堆排序就是先构建一个顶堆，然后将堆顶第一个元素与最后一个元素交换，此时最大元素就跑到末尾去了，然后再整理一下堆进行下一次交换，直到剩下一个元素堆排序就完成了

• 稳定排序、空间复杂度是O(1)、时间复杂度是O(nlogn)（像快速排序、归并排序时间复杂度都是nlogn，那该如何选择呢？）

  • 快速排序时间复杂度是nlogn，但是最坏情况是n^2，而归并排序和堆排序的时间复杂度都稳定再nlogn

  

• 代码实现

  import java.util.Arrays;
  
  /**
   * @Description: 堆排序
   * @Author: LinZeLiang
   * @Date: 2020-10-08
   */
  public class HeapSort {
  
      public static void main(String[] args) {
          int[] a = {9, 8, 7, 5, 6, 4, 3, 2, 1, 0};
  
          heapSort(a);
  
          System.out.println(Arrays.toString(a));
      }
  
      /**
       * 堆排序
       *
       * @param a 待排序数组
       */
      private static void heapSort(int[] a) {
          //获取数组长度
          int length = a.length;
          //建立大顶堆，完成建堆
          for (int i = (length - 2) / 2; i >= 0; i--) {
              downAdjust(a, i, length);
          }
          //进行堆排序
          for (int i = length - 1; i >= 1; i--) {
              //交换，将大的数放到末尾
              int temp = a[i];
              a[i]  = a[0];
              a[0] = temp;
  
              downAdjust(a, 0, i);
          }
      }
  
      /**
       * 下沉调整
       *
       * @param a 待排序数组
       * @param parent 父节点
       * @param length 数组长度范围
       */
      private static void downAdjust(int[] a, int parent, int length) {
          int temp = a[parent];
          //获取左孩子索引
          int child = parent * 2 + 1;
          //当孩子的索引再数组长度范围内时（即孩子存在时）
          while (child < length) {
              //如果右孩子比左孩子大，就指向右孩子
              if (child + 1 < length && a[child] < a[child + 1]) {
                  child++;
              }
              //如果父节点小于等于孩子的结点，那么下沉结束
              if (temp >= a[child]) {
                  break;
              }
              //单向赋值，将孩子上移一位
              a[parent] = a[child];
              //父节点索引指向上移的那个孩子的结点，孩子索引也更新
              parent = child;
              child = parent * 2 + 1;
          }
          a[parent] = temp;
      }
  }
  

堆排序

原文：https://www.cnblogs.com/linzedian/p/13783389.html