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

基本思想：

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

堆的定義:

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

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

排序過程：

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

小根堆排序?qū)崿F(xiàn)：

HeapSort.java

package javasort;

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

    //調(diào)整無序序列為大根堆 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) {
        //把順序表構(gòu)建成為一個大根堆
        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í)行結(jié)果：

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