這是昨天朋友在面試過程中，遇到的筆試問題，幫忙解決并自我學習之。主要是堆排序里面涉及的基本概念和排序過程。比如什么是堆以及利用堆排序的基本思
路等。數(shù)據(jù)結構里面知識基本上算是歸還了老師了，希望這個排序能給自己提個醒。

基本思想：

       堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。

堆的定義:

N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性：
       Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

       堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大于等于其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，它對應的完全二叉樹如上圖所示。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結點的關鍵字均大于等于其孩子的關鍵字，則稱之為大根堆。

排序過程：

堆排序正是利用小根堆（或大根堆）來選取當前無序區(qū)中關鍵字小（或最大）的記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無序區(qū)調整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴大到整個記錄區(qū)。

小根堆排序實現(xiàn)：

HeapSort.java

package javasort;

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

    //調整無序序列為大根堆 s 為數(shù)組的起始下標，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;
        }
    }

    //根據(jù)大根堆，對堆排序
    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("數(shù)組排序前", arry_int);
        System.out.println();
        HeapSort hsort = new HeapSort();
        hsort.HeapSorting(arry_int);
        show("數(shù)組排序后", 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]);
        }
    }
}

執(zhí)行結果：

>>>數(shù)組排序前<<<
  49  38  65  97  76  13  27  55
>>>數(shù)組排序后<<<
  97  76  65  55  49  38  27  13