堆排序

heapInsert&heapify排序

思路来源

一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到

笔记内容

• 问题描述

  对一个数组进行大根堆排序

• 算法思路

  1. heapInsert ：视为用户一个个插入新数值，由下往上比较
  2. heapify ：视为对所有子树排序，由子树的头结点从上往下比较

• 代码实现

  public class Heapsort {
      public static void main(String[] args) {
          int[] target = {5,4,9,7,6,3,6};
          heapify(target,0);
          for (int i = 0; i < target.length; i++) {
              System.out.print(target[i]+" ");
          }
      }
  
      /**
       * 复杂度为nlogn的排序方法
       * */
      public static void heapInsert(int[] target){
          for (int i = 0; i < target.length; i++) {
              int index = i;
              while (true){
                  int max = (index-1)/2;
                  if(index ==0 ){
                      break;
                  }
                  if(target[(index-1)/2] < target[index]){
                      int temp = target[index];
                      target[index] = target[(index-1)/2];
                      target[(index-1)/2] = temp;
                      index = (index-1)/2;
                      max = (index-1)/2;
                  }else {
                      break;
                  }
              }
          }
  
      }
  
      /**
       * 复杂度为n的排序方法
       * */
      public static void heapify(int[] target, int root){
          if(2*root+1 > target.length-1){ //没有子节点
              return;
          }
          heapify(target,2*root+1);
          heapify(target,2*root+2);
          int max = -1;
          while (true){
              if(2*root+2 < target.length){ //有两个孩子
                   max = target[2*root+1] > target[2*root+2] ? 2*root+1 : 2*root+2;
              } else if (2*root+1 < target.length) { //只有左孩子
                   max = 2*root+1;
              }else {
                  break;
              }
              if(target[max] > target[root]){
                  int temp = target[max];
                  target[max] = target[root];
                  target[root] = temp;
                  root = max;
              }else {
                  break;
              }
  
          }
      }
  }