原理

利用二叉堆的性质来完成对于无序数组的排序

  1. 最大堆的堆顶是整个堆中的最大元素
  2. 最小堆的堆顶是整个堆中的最小元素

所以，以最大堆为例，如果删除一个最大堆的堆顶（逻辑删除，只是跟末尾的节点进行互换），那么经过自我调整，第二大的元素就会被交换上来，成为最大堆的堆顶。经过n-1次互换后，原本的二叉堆就变成由小到大的有序集合了。如图：
1638771826(1).jpg

1638771924(1).jpg

代码

  1. /**
  2.  * “下沉”调整
  3.  * @param array      待调整的堆
  4.  * @param parentIndex      要“下沉”的父节点
  5.  * @param length       堆的有效大小
  6.  * 将大的元素下沉的步骤：
  7.  * 1.定义要下沉的父节点，子节点=父节点*2+1，如果子节点存在就继续循环
  8.  * 2.比较左子节点跟右子节点大小，哪个大就将子节点定位到哪个节点
  9.  * 3.判断父节点跟子节点的大小，看是否需要下沉
  10.  * 4.把子节点的值赋值给父节点，令此时的子节点成为父节点继续下沉
  11.  */
  12. public static void downAdjust(int[] array, int parentIndex,
  13.                                 int length) {
  14.     int temp = array[parentIndex];
  15.     // 左子节点 = 父节点 * 2 + 1
  16.     int childrenIndex = 2 * parentIndex + 1;
  17.     while (childrenIndex < length) {
  18.         // 如果右子节点存在，且右子节点的值大于于左子节点，则定位到右子节点
  19.         if (childrenIndex + 1 <= length && array[childrenIndex] > array[childrenIndex + 1]) {
  20.             childrenIndex++;
  21.         }
  22.         // 如果父节点的值小于等于任何一个子节点，则结束循环
  23.         if (temp >= array[childrenIndex]) {
  24.             break;
  25.         }
  26.         array[parentIndex] = array[childrenIndex];
  27.         parentIndex = childrenIndex;
  28.         childrenIndex = 2 * childrenIndex + 1;
  29.     }
  30.     array[parenIndex] = temp;
  31. }
  33. public static void headSort(int[] array) {
  34.     // 1.把无序数组构成最大堆;从倒数第一个非叶子节点开始下沉，循环
  35.     for (int i = (array.length-2)/2; i>=0; i--) {
  36.         downAdjust(array,i,array.length);
  37.     }
  38.     // 2.循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶
  39.     for (int i = array.length-1; i>0; i--) {
  40.         int temp = array[i];
  41.         array[i] = array[0];
  42.         array[0] = temp;
  43.         // 下沉调整最大堆
  44.         downAdjust(array,0,i);
  45.     }
  46. }

复杂度分析

空间复杂度为O（1），因为没有开辟额外的空间。下沉方法的时间复杂度是O(logn)，把无序数组构建成二叉堆的时间复杂度是O(n)，需要进行n-1次循环，因为构建二叉堆跟循环是并列关系，所以总的时间复杂度是O(nlogn)