排序算法系列之一：堆排序

     堆分类是借助一种称为堆的完全二元树结构进行的。完全二元树可以用一个数组表示。在这种表示法中，容易确定一个结点的父结点及其左右儿子的下标。现在，把具有如下性质的数组A表示的完全二元树称为堆：(1)如果2i < n, 则A[i] <= A[2i] (2)如果2i + 1 < n, 则A[i] <= A[2i + 1] 。即树中任一非叶子结点的值都不大于其左右儿子结点的值。

     堆排序算法思想：(1)初始化操作：初始建堆（2）每一趟排序的基本操作：将堆中的第一个结点值与最后一个结点值交换，重新把前面的元素整理成堆。

     我的方法实现与这种略有差别:我是每次先整理成堆，然后交换。

     其实都是一样的，都是以一个堆开始，以交换结束。

 

/**
 * 堆排序类
 *
 * @author YouFengkai
 *
 */
public class HeapSort {

 private final int ARRAYSIZE = 10;
 // 该数组表示一颗完全二叉树
 private int[] tree;

 public HeapSort() {
  // 排序下标1到ARRAYSIZE的
  this.tree = new int[ARRAYSIZE + 1];
  for (int i = 0; i < this.ARRAYSIZE + 1; i++) {
   tree[i] = (int) (1 + Math.random() * 40);
  }
 }

 // 输出排序数组下标1到ARRAYSIZE中的所有数据
 public void desc() {
  for (int i = 1; i <= ARRAYSIZE; i++) {
   System.out.print(tree[i]);
   System.out.print(" ");
  }
  System.out.println();
 }

 // 堆排序
 public void sort() {

  int last = ARRAYSIZE;
  for (int i = last; i >= 2; i--) {
   // 初始化堆，先整理好堆，从i/2开始是因为这是最后一个非叶子结点
   for (int j = i / 2; j >= 1; j--) {
    pushDown(j, i);
   }
   // 树根为最小的，把它与最后的元素交换。
   // 除最后的元素外，是一个只有树根不满足条件的堆，重新整理。
   swap(1, i);
  }

 }

 /**
  * 交换树中两个节点的值
  *
  * @param positionA
  *            第一个位置
  * @param positionB
  *            第二个位置
  */
 private void swap(int positionA, int positionB) {
  int temp = tree[positionA];
  tree[positionA] = tree[positionB];
  tree[positionB] = temp;
 }

 /**
  * 下推整理堆
  *
  * @param first
  *            开始整理的第一个节点
  * @param last
  *            最大的节点
  */
 private void pushDown(int first, int last) {
  // 如果first位置不是叶子节点，开始下推整理
  int r = first;
  if (r <= last / 2) {
   // 如果当前节点不是叶子，则继续整理下推
   while (2 * r <= last) {
    int leftSon = 2 * r;
    boolean hasRightSon = false;
    int rightSon = leftSon + 1;
    if (leftSon + 1 <= last) {
     hasRightSon = true;
    }
    // 如果只有左儿子，且左儿子值比当前节点值小，则与左儿子交换
    if (!hasRightSon && tree[leftSon] < tree[r]) {
     swap(r, leftSon);
     r = leftSon;
    }
    // 否则如果右儿子值不大于左儿子值，且左儿子值比当前节点值小，则与左儿子交换
    else if (hasRightSon && tree[rightSon] <= tree[leftSon]
      && tree[rightSon] < tree[r]) {
     swap(r, rightSon);
     r = rightSon;
    }
    // 否则如果左儿子值不大于右儿子值，且左儿子值比当前节点值小，则与左儿子交换
    else if (hasRightSon && tree[leftSon] <= tree[rightSon]
      && tree[leftSon] < tree[r]) {
     swap(r, leftSon);
     r = leftSon;
    }
    // 否则，不做变化。结束循环
    else {
     break;
    }
   }
  } else {
   return;
  }
 }

 public static void main(String[] args) {
  HeapSort hs = new HeapSort();
  System.out.println("初始的数组为：");
  hs.desc();
  hs.sort();
  System.out.println("经过堆排序后的数组为：");
  hs.desc();
 }

}

 

 

结果：

初始的数组为：
22 36 18 10 24 18 12 35 15 5
经过堆排序后的数组为：
36 35 24 22 18 18 15 12 10 5