令人头疼的堆排序简单化解

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
堆排序从理解程度就不好理解，所以并不推荐使用堆排序，但是这里作为了解

堆排序分为小顶堆和大顶堆
概念：

1. 小顶堆就是把最小的值放到头节点，每个节点值都比子树小
2. 大顶堆则和小顶堆相反，每个节点值都比子树大
   
   小堆顶就是不停把小的放上去

过程解析

主要由两部分组成

1. adjustHeap 调整堆结构，比如下面要调整，不停的调整直到最大值在头节点位置，大的值都在上面，但是虽然构建了头节点比子树大的情况，但还是不满足我们的升序或者降序排列这时候就要第二步了，第一步就是构建一个堆结构

最后是这样的堆结构这里拿的大顶堆图片

2. sort排序，把拿到的堆结构进行排序，直接头节点和最后一个节点交换值交换完肯定会破环整个堆结构，所以要执行一次adjustHeap形成堆结构
3.

代码实现

public class HeapSort {
 public static void main(String[] args) {
  // TODO 自动生成的方法存根
        int[] arr= {6,5,8,9,4};
        sort(arr);
 }
 public static void sort(int[] arr) {
  int temp=0;
  System.out.println("小顶堆排序");
  //1. 找到最后一个非叶子节点
  for(int i=arr.length/2-1;i>=0;i--){
   adjustHeap(arr,i,arr.length);
  }
  //2.将堆顶元素与末尾元素交换，最大的元素沉到数组末端
  //3. 换完之后将整个数组调整结构，然后继续交换堆顶元素和当前末尾元素
  //4. 反复执行3和2，直到整个数组有序
  for(int j=arr.length-1;j>0;j--) {
   //交换
   temp=arr[j];  //将末尾节点存值
   arr[j]=arr[0]; 
   arr[0]=temp;
   adjustHeap(arr, 0, j);
  }
  System.out.println("小顶堆数组:"+Arrays.toString(arr));
 }
 private static void adjustHeap(int[] arr, int i, int length) {
  // TODO 自动生成的方法存根
  int temp=arr[i];//先取出当前元素值
  //拿到左子树的每个节点，如果小于右子树就拿右边的
  for(int k=i*2+1;k<length;k=k*2+1) {
   if(k+1<length&&arr[k]<arr[k+1]) {
    k++;
   }
   if(arr[k]>temp) {
    arr[i]=arr[k];
    i=k;
   }else {
    break;
   }
  }
  //for循环结束i指向了要交换的节点位置
  arr[i]=temp;//完成最大值与头节点的交换
 }
}

输出

小顶堆排序
小顶堆数组:[4, 5, 6, 8, 9]

注意

只要将调整堆结构的判断条件改一下就可以实现是小顶堆还是大顶堆
==大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] ==
==小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] ==

按照下面这个图堆排序并不稳定且难理解，通过每次的调整结构就要耗费大量时间所以并不推荐使用，了解即可