排序算法之堆排序 Java 实现

---

1.知识补充

---

1.0 完全二叉树

一棵深度为K，有n个节点的二叉树，对树中节点按照从上至下，从左至右的顺序进行编号，如果编号为i（1<=i<=n）与满二叉树的编号为i的位置一致，则称此树为完全二叉树。

完全二叉树和非完全二叉树示意图.jpg

1.1满二叉树

满二叉树：如果一棵二叉树所有分支都存在左右子节点，且所有的叶子节点都在同一层，则成这棵树为满二叉树。

满二叉树（a）与非满二叉树（b）.jpg

1.2 完全二叉树的性质（重点）

如果对具有n个节点二叉树的根节点从0开始编号，则序号为i的节点的双亲结点为(i-1)/2,左孩子的编号为2i+1，右孩子为2i+2。如果从1开始编号，则双亲结点编号为i/2，左孩子结点序号为2i，右孩子结点序号为2i+1.

2 堆（千呼万唤始出来）

堆：n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：

树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。

3.堆得建立

---

算法思路：
1.我们首先将数组进行初始化调整成大根堆。
2.然后进行排序，每次排序时，将最后一个序号n节点的值与根节点0的值进行替换，然后将节点又调整成堆。
3.然后将根节点与n-1进行交换重复步骤2。直到序列为有序

3.1以大根堆为例：

 /**
     * 堆调整算法
     * @param num   数组
     * @param s 调整节序号
     * @param l 数组排序最大的序号 
     */
  public static void HeapAdjust(int[] num,int s,int l){
      int i,j;
      int temp=num[s];
      i=s;
      // 根据二叉树的性质可知道每一个序号对应的子节点以及双亲节点
      for(j=2*i+1;j<=l;j=2*j+1){
          //判断如果j指向数值较大的节点
          if(j<l&&num[j]<num[j+1]){
              j=j+1;
          }
          //如果调整节点大于其子节点最大的值则无需调整
          if(temp>num[j]){
              break;
          }
          //如果小于则将子节点移动到根节点位置，如果还存在子节点则继续判断调整位置的子节点
          //准备继续向下 调整节点
          num[i]=num[j];
          i=j;
      }
      //最后插入数据
      num[i]=temp;
  }                             

3.2堆的建立

   /**
     * 堆建立初始化函数
     * @param nums 数组序列
     * @param l 最大序号
     */
  public static void HeapInit(int[] nums,int l){
      for (int i = (l-1) / 2; i >=0; i--) {
          HeapAdjust(nums, i, l);
      }
  }

3.3 堆的排序算法

  public static void HeapSort(int[] nums,int l){
     for(int i=l;i>0;i--){
         int temp=nums[0];
         nums[0]=nums[i];
         nums[i]=temp;
         //因为每次调整都是对根节点进行调整所以下列方法s永远为0
         HeapAdjust(nums,0,i-1);
     }
  }

3.4最后我们来看看效果

 public static void main(String[] args){
        int[] nums={3,2,4,9,8};
        //第一步根据节点创建堆
        for (int i = (4-1) / 2; i >=0; i--) {
            HeapAdjust(nums, i, 4);
        }
        //第二步排序
        HeapSort(nums,4);
        for(int n:nums){
            System.out.println(n);
        }

    }

输出

2
3
4
8
9