1.簡單選擇排序

void SelectSort(int k[], int n)
{
    int i, j, min, temp;

    for( i=0; i < n-1; i++ )
    {
        min = i;
        
        for( j=i+1; j < n; j++ )
        {
            if( k[j] < k[min] )
            {
                min = j;
            }
        }

        if( min != i )
        {
            temp = k[min];
            k[min] = k[i];
            k[i] = temp;
        }
    }

}

2.堆排序

1、什么是堆？

堆是一種非線性結構，可以把堆看作一個數(shù)組，也可以被看作一個完全二叉樹，通俗來講堆其實就是利用完全二叉樹的結構來維護的一維數(shù)組

按照堆的特點可以把堆分為大頂堆和小頂堆

大頂堆：每個結點的值都大于或等于其左右孩子結點的值

小頂堆：每個結點的值都小于或等于其左右孩子結點的值

（堆的這種特性非常的有用，堆常常被當做優(yōu)先隊列使用，因為可以快速的訪問到“最重要”的元素）
2、堆的特點（數(shù)組實現(xiàn)）

• 我們對堆中的結點按層進行編號，將這種邏輯結構映射到數(shù)組中就是下面這個樣子

我們用簡單的公式來描述一下堆的定義就是：（讀者可以對照上圖的數(shù)組來理解下面兩個公式）

大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

3、堆和普通樹的區(qū)別

內(nèi)存占用：

普通樹占用的內(nèi)存空間比它們存儲的數(shù)據(jù)要多。你必須為節(jié)點對象以及左/右子節(jié)點指針分配額外的內(nèi)存。堆僅僅使用數(shù)組，且不使用指針

（可以使用普通樹來模擬堆，但空間浪費比較大，不太建議這么做）

平衡：
二叉搜索樹必須是“平衡”的情況下，其大部分操作的復雜度才能達到O(nlog2n)。你可以按任意順序位置插入/刪除數(shù)據(jù)，或者使用 AVL 樹或者紅黑樹，但是在堆中實際上不需要整棵樹都是有序的。我們只需要滿足對屬性即可，所以在堆中平衡不是問題。因為堆中數(shù)據(jù)的組織方式可以保證O(nlog2n) 的性能

搜索：
在二叉樹中搜索會很快，但是在堆中搜索會很慢。在堆中搜索不是第一優(yōu)先級，因為使用堆的目的是將最大（或者最?。┑墓?jié)點放在最前面，從而快速的進行相關插入、刪除操作

4、堆排序的過程

先了解下堆排序的基本思想：

將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值，

如此反復執(zhí)行，便能得到一個有序序列了，建立最大堆時是從最后一個非葉子節(jié)點開始從下往上調(diào)整的（這句話可能不好太理解），下面會舉一個例子來理解堆排序的基本思想

int a[6] = {7, 3, 8, 5, 1, 2};
根據(jù)數(shù)組將完全二叉樹還原出來

大頂堆

大頂堆的特點：每個結點的值都大于或等于其左右孩子結點的值，我們把大頂堆構建完畢后根節(jié)點的值一定是最大的，然后把根節(jié)點的和最后一個元素（也可以說最后一個節(jié)點）交換位置，那么末尾元素此時就是最大元素了（理解這點很重要）

知道了堆排序的原理下面就可以來操作了，在進行操作前先理清一下步驟

（假設我們想要升序的排列）

第一步：先n個元素的無序序列，構建成大頂堆

第二步：將根節(jié)點與最后一個元素交換位置，（將最大元素"沉"到數(shù)組末端）

第三步：交換過后可能不再滿足大頂堆的條件，所以需要將剩下的n-1個元素重新構建成大頂堆

第四步：重復第二步、第三步直到整個數(shù)組排序完成

6、圖解交換過程（得到升序序列，使用大頂堆來調(diào)整）

這里以int a[6] = {7, 3, 8, 5, 1, 2}為例子

先要找到最后一個非葉子節(jié)點，數(shù)組的長度為6，那么最后一個非葉子節(jié)點就是：長度/2-1，也就是6/2-1=2，然后下一步就是比較該節(jié)點值和它的子樹值，如果該節(jié)點小于其左\右子樹的值就交換（意思就是將最大的值放到該節(jié)點）

8只有一個左子樹，左子樹的值為2，8>2不需要調(diào)整

下一步，繼續(xù)找到下一個非葉子節(jié)點（其實就是當前坐標-1就行了），該節(jié)點的值為3小于其左子樹的值，交換值，交換后該節(jié)點值為5，大于其右子樹的值，不需要交換

下一步，繼續(xù)找到下一個非葉子節(jié)點，該節(jié)點的值為7，大于其左子樹的值，不需要交換，再看右子樹，該節(jié)點的值小于右子樹的值，需要交換值

下一步，檢查調(diào)整后的子樹，是否滿足大頂堆性質(zhì)，如果不滿足則繼續(xù)調(diào)整（這里因為只將右子樹的值與根節(jié)點互換，只需要檢查右子樹是否滿足，而8>2剛好滿足大頂堆的性質(zhì)，就不需要調(diào)整了，

如果運氣不好整個樹的根節(jié)點的值是1，那么就還需要調(diào)整右子樹）

到這里大頂堆的構建就算完成了，然后下一步交換根節(jié)點（8）與最后一個元素（2）交換位置（將最大元素"沉"到數(shù)組末端），此時最大的元素就歸位了，然后對剩下的5個元素重復上面的操作

（這里用粉紅色來表示已經(jīng)歸位的元素）

剩下只有5個元素，最后一個非葉子節(jié)點是5/2-1=1，該節(jié)點的值（5）大于左子樹的值（3）也大于右子樹的值（1），滿足大頂堆性質(zhì)不需要交換

找到下一個非葉子節(jié)點，該節(jié)點的值（2）小于左子樹的值（5），交換值，交換后左子樹不再滿足大頂堆的性質(zhì)再調(diào)整左子樹，左子樹滿足要求后再返回去看根節(jié)點，根節(jié)點的值（5）小于右子樹的值（7），再次交換值

得到新的大頂堆，如下圖，再把根節(jié)點的值（7）與當前數(shù)組最后一個元素值（1）交換，再重構大頂堆->交換值->重構大頂堆->交換值····，直到整個數(shù)組都變成有序序列

最后得到的升序序列如下圖

// 雙親結點 s
// 數(shù)組長度 n
void HeapAdjust(int k[], int s, int n) {
    int i = s, j = 2 * i;   //k[j]是k[i]的左孩子
    int temp = k[i];
    
    while (j < n) {
        if (j < n && k[j] < k[j+1]) {
            ++j;            // 若右孩子大于左孩子，則把j指向右孩子
                            // 否則還是右孩子（j < n）
        }
        
        if (temp < k[j]) {
            k[i] = k[j];        //孩子小于雙親，將j指向的孩子賦值給雙親
            i = j;              //將雙親待存放的位置賦值給i
                                //目的是循環(huán)繼續(xù)調(diào)整 i 的左孩子
            j = 2 * i;          //繼續(xù)指向i的左孩子（循環(huán)條件）
            
        }
    }
    k[i] = temp; // 把原來的雙親方到最終的位置
}


void HeapSort(int k[], int n) {
    int i;
    int temp;
    for (i = n/2; i >= 1; i--) { // i =n/2 從最后一個非葉子結點開始
        HeapAdjust(k, i, n);
    }
    
    for (i = n; i >= 2; i--) {
        temp = k[1];
        k[1] = k[i];
        k[i] = temp;
        // 將第一個元素和最后一個元素互換
        // 調(diào)整好的第一個元素肯定是最大的元素
        // 互換再繼續(xù)調(diào)整除了最后一個的其他元素（最大值）
        
        
        HeapAdjust(k, 1, i-1);
    }
}