001什么是堆排序？

堆結構如下圖，堆的實際結構是數組，但是我們在分析它的時候用的是有特殊標準的完全二叉樹來分析。也就是說數組是堆的實際物理結構而完全二叉樹是我們便于分析的邏輯結構。堆有兩種：大根堆和小根堆。每個節點的值都大于其左孩子和右孩子節點的值，稱為大根堆。每個節點的值都小于其左孩子和右孩子節點的值，稱為小根堆。

上面的結構映射成數組就變成了下面這個樣子

002堆排序的特點？

1.首先堆的大小是提前知道的，根節點的位置上存儲的數據總是在數組的第一個元素。

2.假設一個非根節點所存儲的數據的索引為i，那么它的父節點存儲的數據所對應的索引就為[(i-1)/2]

3.假設一個節點所存儲的數據的索引為i，那么它的孩子（如果有）所存儲的數據分別所對應的索引為：左孩子是[2*i+1]，右孩子是[2*i+2]

003堆排序的流程？

第一步，將待排序的數組構造成一個大根堆，假設有下面這個數組：

具體思路：第一次保證0~0位置大根堆結構，第二次保證0~1位置大根堆結構，第三次保證0~2位置大根堆結構...直到保證0~n-1位置大根堆結構（每次新插入的數據都與其父節點進行比較，如果插入的數比父節點大，則與父節點交換。周而復始一直向上比較，直到小于等于父節點或者來到了根節點則終止）

【1】插入6的時候，6大于他的父節點3，即arr(1)>arr(0)，則交換；此時保證了0~1位置是大根堆結構，如下圖：

【2】插入8的時候，8大于其父節點6，即arr(2)>arr(0),則交換；此時，保證了0~2位置是大根堆結構，如下圖

【3】插入5的時候，5大于其父節點3，則交換，交換之后，5又發現比8小，所以不交換；此時，保證了0~3位置大根堆結構，如下圖

【4】插入7的時候，7大于其父節點5，則交換，交換之后，7又發現比8小，所以不交換；此時整個數組已經是大根堆結構

第二步，將根節點的數與末尾的數交換

【1】大根堆中整個數組的最大值就是堆結構的父節點，接下來將根節點的數8與末尾的數5交換

第三步，將剩余的n-1個數再構造成大根堆

如上圖所示，此時最大數8已經來到末尾，讓堆的有效大小減1，后面拿頂端的數與其左右孩子較大的數進行比較，如果頂端的數大于其左右孩子較大的數，則停止，如果頂端的數小于其左右孩子較大的數，則交換；周而復始一直向下比較，直到大于左右孩子較大的數或者沒有孩子節點則終止。

下圖中，5的左右孩子中，左孩子7比右孩子6大，則5與7進行比較，發現5<7，則交換；交換后，發現5已經大于他的左孩子，說明剩余的數已經構成大根堆，

第四步，再將第二步和第三步反復執行，便能得到有序數組

004如何將待排序的數組構造成一個大根堆？

首先遍歷該數組，假設某個數處于index位置，每次都讓index位置和父節點位置的數進行比較，如果大于父節點的值就交換位置，....周而復始，一直到不能往上為止。

for (int i = 0; i < arr.length; i++) { // O(N)
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }	
}

005如何將剩余的n-1個數再構造成大根堆？

先將大根堆的頭節點的數據與堆上的最后一個數交換位置后，把堆有效區的長度減1，再從頭節點開始做向下的比較，每次都和左右孩子中較大值進行比較，如果父節點比最大孩子的值下就交換位置....周而復始，一直到不能往下為止。

// 某個數在index位置，能否往下移動
public static void heapify(int[] arr, int index, int heapSize) {
    int left = index * 2 + 1; // 左孩子的下標
    while (left < heapSize) { // 下方還有孩子的時候
        // 兩個孩子中，誰的值大，把下標給largest		
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        // 父和較大的孩子之間，誰的值大，把下標給largest
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;	
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

006堆的排序如何實現？

具體實現前面的問題，具體源代碼實現如下：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    //第一步，將待排序的數組構造成一個大根堆
    for (int i = 0; i < arr.length; i++) { // O(N)
        heapInsert(arr, i); // O(logN)
    }
    int heapSize = arr.length;
    //第二步，將根節點的數與末尾的數交換
    swap(arr, 0, --heapSize);
    while (heapSize > 0) { // O(N)
        //第三步，將剩余的n-1個數再構造成大根堆
        heapify(arr, 0, heapSize); // O(logN)
        //第二步，將根節點的數與末尾的數交換
        swap(arr, 0, --heapSize); // O(1)
    }
}

007什么是桶排序？

1）桶排序（Bucket sort）或所謂的箱排序，是一個排序算法，工作的原理是將數組分到有限數量的桶里。每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序），最后依次把各個桶中的記錄列出來記得到有序序列。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ(n)）。但桶排序并不是比較排序，他不受到O(n log n)下限的影響。

2）算法圖解

008堆排序平均執行的時間復雜度和需要附加的存儲空間復雜度分別是( )

A. O(n^2)和O(1)
B. O(nlog(n))和O(1)
C. O(nlog(n))和O(n)
D. O(n^2)和O(n)
答案：B
解析：暫無解析