堆排序算法

堆排序 平均时间复杂度为 O(nlogn) 最坏情况下O(nlogn)

原理 （以从小到大为例）

首先将数组中的数据构建大根堆 具体代码如下

    for(i=n/2-1;i>=0;i--){//建成大根堆
        while(2*i+1<n){       //存在左右子树
            j=2*i+1;//左子树
            if((j+1)<n){//右子树存在的情况
                if(a[j]<a[j+1]) j++;//如果右子树比做左子树大      j指向  右子树
            }
            if(a[i]<a[j]){//如果    子节点大于根节点进行交换
                t=a[j];
                a[j]=a[i];
                a[i]=t;
                i=j;//调整子树
            }else{
                break;//不需要调整
            }
        }
    }

构建大根堆结束后下来进行排序 由于是大根对 则根节点就是当前最大值 交换该值重新构造大根堆

重复上述具体代码如下

    for(i=n-1;i>0;i--){//依次遍历
        t=a[0];                //与第i个数据进行交换     将最大值    插入到该在的地方
        a[0]=a[i];
        a[i]=t;
        k=0;
        while(2*k+1<i){//更换根节点后   堆中元素数量减少     重新构造大根堆
            j=2*k+1;//左子树
            if((j+1)<i){//右子树存在的情况
                if(a[j]<a[j+1]) j++;//如果右子树比做左子树大      j指向  右子树
            }
            if(a[k]<a[j]){
                t=a[j];
                a[j]=a[k];
                a[k]=t;
                k=j;//调整子树
            }else{
            
                break;//不需要调整
            }
        
        }
    }

完整代码如下

/*先建成 大根堆 然后每次取a0 的数据此时的数据为最大值 调整堆结构 使最大值依旧在a0 上

• flag为true 从小到大 false 从大到小
  */
  public class Pile_Sort {

  public void pile_sort(int a[],boolean flag){
  int i=0,j=0,h=0,k=0,t;
  int n=a.length;
  for(i=n/2-1;i>=0;i--){//建成大根堆
  while(2i+1<n){
  j=2i+1;//左子树
  if((j+1)<n){//右子树存在的情况
  if(a[j]<a[j+1]) j++;///如果右子树比做左子树大 j指向 右子树
  }
  if(a[i]<a[j]){
  t=a[j];
  a[j]=a[i];
  a[i]=t;
  i=j;//调整子树
  }else{
  break;//不需要调整
  }
  }
  }
  for(i=n-1;i>0;i--){//依次遍历
  t=a[0]; //与第i个数据进行交换
  a[0]=a[i];
  a[i]=t;
  k=0;
  while(2k+1<i){//更换根节点后 堆中元素数量减少
  j=2k+1;//左子树
  if((j+1)<i){//右子树存在的情况
  if(a[j]<a[j+1]) j++;///如果右子树比做左子树大 j指向 右子树
  }
  if(a[k]<a[j]){
  t=a[j];
  a[j]=a[k];
  a[k]=t;
  k=j;//调整子树
  }else{

               break;//不需要调整
           }
       
       }
   }
   if(!flag){//如果flag  为false    则从大到小排序  此时我们交换前后顺序
        n=a.length-1;
       for(i=0;i<a.length/2;i++){
           t=a[i];
           a[i]=a[n-i];
           a[n-i]=t;
       }
   }
  

  }
  }