• 这是一篇自学文章,如果有错误地方请及时指出
• 堆排序...算法属实优秀,真是有点难理解,花了很长时间才能自己完全写出来,至此献上一个表情包

• 自己很喜欢李雪健老师 义正辞严!!
• 图如果有画错的地方请及时指正,谢谢 ,好了正文开始
  

  ---

堆排序

• 这个算法是基于选择排序思想的算法,其利用堆结构和二叉树的一些特性来完成数据的排序

什么是堆结构

• 是一种树结构,准确的说是一个完全二叉树,在这个树中每个节点对应于原始数据的一个记录,如图

大顶堆与小顶堆

• 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆
• 每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
• 升序采用大顶堆,降序采用小顶堆

堆排序基本思想

• 将待排序序列构造成一个大顶堆,此时整个序列的最大值就是堆顶的根节点.将其与末尾元素进行交换,此时末尾就为最大值.然后将剩余n-1个元素重新构造成一个堆(n-1就是将以确定的最大值排除在外的意思),这样会得到n个元素的次小值.如此反复执行.便能得到一个有序序列了

堆排序过程

• 我们先看一张图,这是一张较为简单的构建过程

• 然后再来一张比较复杂点的

• 小总结

• 到这我们就知道了构建顶堆的基本思想,那么他是怎么来进行排序输出的呢?

• 上图说的交换首尾,意思是除了确定好的最大值的剩余序列的首尾,如上的数组结构示意图,72标红被确定了,所以下次有第二大的值就与41的位置处的数据进行交换

• 代码分析

  • 我们看完了上面的图的流程,我们可以想到首先我们必须要将数据序列先构造成一次大顶堆,因为如果不这样,我们拿不到最大值也就没办法知道哪个值与那个值互换了
  • 之后就是交换数据首尾的值
  • 上面一步操作完毕后,我们的大顶堆就又乱掉了,所以还的需要重新构建
  • 总的说就是:先构建一次大顶堆 -> 交换首尾 -> 再次构建大顶堆

• java代码实现

  import java.util.Arrays;
  
  public class SS {
      public static void main(String []args){
          //-1 不代表待排序的数字,无论是什么都不影响排序结果,只是一个站位的而已
          int []arr = {-1,41,34,56,33,36,45,72,30};
          heapSort(arr);
          System.out.println(Arrays.toString(arr));
      }
  
      private static void heapSort(int[] arr) {
          int len = arr.length;
          //第一个循环是从下到上的
          //i就是每个非叶结点
          for (int i = len / 2; i > 0; i --) {
              //将叶结点传入后,就是去比较叶结点与其子节点的关系了,而并非一下完成,
              // 而是一个个非叶结点传入,来判断父子关系,再决定交换
              build(arr,i,len);
          }
          //这个循环每循环一次都会挑出剩余最大的值
          for (int i = len - 1; i > 0 ; i --) {
              swap(arr,1,i);
              build(arr,1,i);
          }
      }
      /**
       * @param arr 待排数组
       * @param parent  即每一个非叶结点
       * @param len  数组长度,即从1到N需要排序,比如72确定了后,那么就是1到N-1个待排序
       */
      private static void build(int[] arr, int parent, int len) {
          //i初始化为 左结点 , i *= 2代表下一个非叶结点
          for (int i = parent * 2; i < len; i *= 2) {
              //i+1表示右结点,这就话的意思就是有右结点,并且这个右结点还是最大子节点
              if (i +1 < len && arr[i + 1] > arr[i]){
                  i ++;  //i原来指向了左结点,因为右结点大,所以指向右结点下标
              }
              //如果父节点比最大子节点还大或者相等,就不需要交换
              if (arr[parent] >= arr[i]){
                  break;
              }
              //到这就代表最大子节点比父节点大 ,那么就开始交换
              swap(arr,parent,i);
              //交换完毕后,我们在图中也遇到了就是图结构被破坏了,
              //也就是图四到图五的情况
              //这的赋值代表了,我们交换完成了,依旧要去重新判断一下刚刚交换的子节点是否符合结构
              //就比如图四到图五,72与41交换位置了,那么原来的parent是41,下标为1
              //而i是72,下标为3,由于他们两个交换位置了,所以导致结构乱掉了
              //我们可以将parent指向下标为3的位置,以下标为3作为parent节点,来判断其子节点是否符合结构
              parent = i;
          }
      }
      public static void swap(int []arr,int a ,int b){
          int temp=arr[a];
          arr[a] = arr[b];
          arr[b] = temp;
      }
  }