排序 - [选择排序 - 堆排序]-蒲公英云

跟之前一样，我的文章力求通俗易懂。

今天讨论堆排序。

堆排序是选择排序的一种。堆排序大致分为两个步骤：

构建初始堆 (大顶堆或小顶堆)；
逐渐从堆中取出顶部元素，重新构造堆，然后再取出顶部元素，循环直到堆为空。

正式开始，首先我们来如何构建初始堆。因为堆是一个二叉树，为了更清楚的描述，在这篇文中我用了一些图片，希望能够讲清楚。

今天待排序的数组为：15, 19, 10, 7, 17, 6

我们用二叉树来表示这个数组，方法很简单，原则就是：

* 给每个元素加上编号，比如编号为1的元素是 15，编号为2的元素是19，以此类推，给每个元素加上编号；

* 1号元素为二叉树的根，他的左孩子是#2 (左孩子位置：2 * i)，右孩子是#3 (右孩子位置：2 * i + 1) ；

* 2 号元素的左孩子是#4, 右孩子是#5；3号元素的左孩子是#6, 右孩子是#7，照这样的算法我们可以得到这样的二叉树：

SouthEast

这个二叉树是未经排序的，在我们真正开始堆排序之前，这个应该是满足堆的要求的二叉树。

那么什么是堆呢? 什么又是大顶堆、小顶堆呢？

堆就是二叉树，每个节点是一个元素。

大顶堆就是每个节点的值都大于他的左右孩子的值；

小顶堆就是每个节点的值小于他的左右孩子的值。（个人见解，不保证一定准确，具体还劳烦大家google。）

那么如何将这个堆变成大顶堆呢？

我们从二叉树的“最右面”的元素开始调整。

什么是“最右面”？

最右面就是指：这个二叉树倒数第二层的最右面一个元素。

为什么从最右面开始呢？

因为最后一层所有的元素都是没有子节点的，那么也没有必要对没有子节点（或者说只有一个节点）的二叉树进行调整。

那么哪个元素是最右面的呢？很简单，就是size / 2。对本例来说，元素个数为6. 6 / 2 = 3.

那么#3元素就是最右面，也就是我们开始调整的地方。

从图上我们可以看到#3元素是10. 如何调整呢？

因为我们要调整成一个大顶堆，那么调整的思想就是将这个元素的值同他的子节点进行比较，如果子节点中较大的值大于自己，那么交换他们。

对于我们的情况是这样的：

要比较的元素是10 和 16.

比较前：

![Image 1][]

交换后结果：

![Image 1][]

从图中我们可以看到，16 大于10，我们对他们做了交换。

接下来我们要做调整的是2号元素：19，他的左右孩子分别为7 和 17，

因为 19 大于他的左右两个孩子，故对19这个节点，我们不需要改变二叉树的结构，故此时的结构不做改变。

为清楚起见，我们也将19比较的过程图画出来：

![Image 1][]

接下来要看的是1号元素，15.

我们拿1号元素的两个孩子：2号和3号跟1号元素比较，可以得到，2号元素19是最大的孩子。

故15应该跟19交换位置。

交换后：

![Image 1][]

咦？图上有条虚线？

是的，因为19被调动了位置，那么7 和17的父节点也就改变了，此时需要对 15 —> (7, 17) 这棵二叉树进行重新调整。

同理，我们知道17是孩子中较大的值，所以我们将15跟17交换位置，交换后结果为：

![Image 1][]

此时，这棵二叉树已经满足大顶堆的条件了，树上任意一棵二叉树都是根节点的值大于左右孩子的值。

对了，忘了说了，图上左面是代表对树做调整时，数组的变化。

到此，我们完成了堆的初始化工作，接下里我们要对他进行排序了。

排序的思想就是逐渐把堆中最大的数字（就是堆顶的元素）跟数组”最后面”(最后面是指未经排序子数组的最后面)的元素进行调换，

然后再把被调换的元素放到堆顶，也就是树根位置，再重新调整为大顶堆，然后循环。

好了，开始排序啦。

我们把19拿出来了，然后跟10进行交换位置：

此时，我们需要再把10放到树根的位置，我们可以看到他的左右孩子分别为 17 和 16.

那么显然，17是较大的孩子，且17大于10，那么我们需要将17和10调换位置，我们得到：

对于10这个元素，我们还没有调整完，因为当10和17对调后，10的左右孩子变为了7和15.

那么15又是左右孩子中较大的值，且他大于10，故我们仍然需要将10和15对调，我们得到：

到此，元素 10 的调整已经完成，我们可以看到，原来的堆顶：19已经在数组的末尾了（我们认为19已经是有序的了）。

那么此时的堆顶是17。同理我们将17跟无序子数组的最后一个元素交换位置。最后一个元素是10，我们得到：

同理啦，此时我们需要把10放到堆顶，再进行调整。

我们简单说下步骤吧：

* 10放到堆顶；

* 左右孩子分别为15,16，很明显16是较大的孩子，我们需要用他跟10进行交换。

那么我们得到：

此时的堆顶元素是16.

继续，我们用16跟无序子数组的末位元素（7）交换，交换后状态如下：

接下来：

* 7放到堆顶，此时他的左右孩子分别为15和10；

* 15为较大的元素，跟7交换位置，得到：

此时堆顶为15，我们用15跟无序子数组的末位元素（10）交换，交换后状态如下：

同理，此时10会处于堆顶位置，我们需要重新调整堆。

他的左右孩子。。。哦，他只有左孩子没有右孩子，左孩子为7，7小于10，好的那么我们不需要调整，状态为：

将10跟无序子数组的末位交换，我们得到：

此时，因为二叉树中只有一个元素，那么我们认为他是有序的，不需要再调整，故最终结果为：

java程序实现:

public class HeapSort {
  public static final int[] toSort = {5, 90, 12, 23, 1, 2, 66, 32}; 
      //{15, 19, 10, 7, 17, 16};
  public static int leftChild = 0;
  public static int rightChild = 0;
  public static int biggerChild = leftChild;
  public static int[] initHeap(int[] sort) {
    int rightMost = (sort.length - 1) / 2;
    for (int i = rightMost; i >=0; i--) {
      sortItem(sort, i, sort.length);
    }
    return sort;
  }
  private static void sortItem(int[] sort, int i, int limit) {
    // 确定要排序的元素的左右孩子的下标
    leftChild = 2 * i + 1;
    rightChild = leftChild + 1;
    if (leftChild < limit) {
      biggerChild = leftChild;
      if (rightChild < limit) {
        if (sort[rightChild] > sort[leftChild]) {
          biggerChild = rightChild;
        }
      }
      if (sort[i] < sort[biggerChild])
        swap(sort, i, biggerChild);
      sortItem(sort, biggerChild, limit);
    }
  }
  /**
   * 交换
   * @param sort
   * @param a
   * @param b
   */
  private static void swap(int[] sort, int a, int b) {
    int tmp = sort[a];
    sort[a] = sort[b];
    sort[b] = tmp;
  }
  /**
   * 堆排序
   * @param sort
   */
  public static void heapSort(int[] sort) {
    initHeap(sort);
    for (int i = 0; i < sort.length; i++) {
      // 将堆顶跟最后一个未排序的元素交换
      swap(sort, 0, sort.length - i - 1);
      percolate(sort, 0, sort.length - i - 1);
    }
  }
  /**
   * 将元素往下渗透
   * @param sort
   * @param i
   */
  private static void percolate(int[] sort, int i, int stopIndex) {
    sortItem(sort, i, stopIndex);
  }
  /**
   * @param args
   */
  public static void main(String[] args) {
    heapSort(toSort);
    for (int i : toSort) {
      System.out.print(i + ", ");
    }
  }
}