这是昨天朋友在面试过程中，遇到的笔试问题，帮忙解决并自我学习之。主要是堆排序里面涉及的基本概念和排序过程。比如什么是堆以及利用堆排序的基本思
路等。数据结构里面知识基本上算是归还了老师了，希望这个排序能给自己提个醒。

基本思想：

       堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

堆的定义:

N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
       Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

       堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。

排序过程：

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。

小根堆排序实现：

HeapSort.java

package javasort;

// 参考：http://blog.csdn.net/EmaYoung/archive/2007/09/29/1806228.aspx
public class HeapSort {

    //调整无序序列为大根堆 s 为数组的起始下标，m为终止下标
    public void HeapAdjust(int[] arr, int s, int m) {
        int temp = arr[s];
        for (int j = 2 * s + 1; j < m; j = j * 2 + 1) {
            if (j + 1 < m && arr[j] > arr[j + 1]) {
                ++j;
            }
            if (temp < arr[j]) {
                break;
            }
            arr[s] = arr[j];
            s = j;
            arr[s] = temp;
        }
    }

    //根据大根堆，对堆排序
    public void HeapSorting(int[] arr) {
        //把顺序表构建成为一个大根堆
        for (int i = arr.length / 2 - 1; i >= 0; --i) {
            HeapAdjust(arr, i, arr.length);
        }

        for (int j = arr.length - 1; j > 0; --j) {
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;
            HeapAdjust(arr, 0, j);
        }
    }
}

Main.java

package javasort;
public class Main {

    public static void main(String[] args) {
        int[] arry_int = {49, 38, 65, 97, 76, 13, 27, 55};
        show("数组排序前", arry_int);
        System.out.println();
        HeapSort hsort = new HeapSort();
        hsort.HeapSorting(arry_int);
        show("数组排序后", arry_int);
    }

    private static void show(String message, int[] array) {
        System.out.println(">>>" + message + "<<<");
        for (int i = 0; i < array.length; i++) {
            System.out.print("  " + array[i]);
        }
    }
}

执行结果：

>>>数组排序前<<<
  49  38  65  97  76  13  27  55
>>>数组排序后<<<
  97  76  65  55  49  38  27  13