堆排序原理解析

概述

堆排序时间复杂度为O(nlogn),使用一个数组进行存储。堆分为最大堆与最小堆

最大堆满足的条件

​ A[PARENT(i)]>=A[i]

最小堆满足的条件

​ A[PARENT(i)]<=A[i]

堆是一个数组，可以被看成一个近似的完全二叉树。以(a)二叉树和(b)数组形式展现的一个最大堆。二叉树结点上方的数字是它在数组中相应的下标。

1583993496545.png

A[i] 的左节点为A[2*i]

A[i]的右节点为A[2*i+1]

建立最大堆

在无序数组自底向上建立最大堆,先代码后面有图。

   int []A=new int[];
    int length=A.length();
    //(length/2)+1 是二叉树中最小的叶子节点   叶子节点不需要进行调整
    for(int i=length/2;i>-1;i--){
        adjustMaxTree（A[i],i）;
    }
}

adjustMaxTree(int value,int index){
//如果 该节点为叶子节点则不需要调整
if(index>A.length()/2)
    return ;
  int largest=value;
  //如果左子节点大于A[index] 则值交换，并对左节点进行调整
  if(largest<A[index*2]){
      largest=A[index*2];
      A[index*2]=A[index];
      A[index]=largest;
      adjustMaxTree(A[index*2],index*2);
  }
    //如果右子节点大于A[index] 则值交换，并对右节点进行调整
 
   if(largest<A[index*2+1]){
      largest=A[index*2+1];
      A[index*2+1]=A[index];
      A[index]=largest;
       adjustMaxTree(A[index*2+1],index*2+1);
      
  }
    
}

1583995395983.png

堆排序

在之前我们为数组A建立好了 最大堆

1583997261328.png

建好后的据图f得最大堆的数组为

1583997513464.png

这时16已经是最大值了，将16 去除后得数组为

1583997623821.png

在对该数组建立最大堆，建好最大堆后将根节点取出再建立最大堆，多次建立最大堆,数组排序成功