一菱农、概述

排序算法概念

在計(jì)算機(jī)科學(xué)與數(shù)學(xué)中缭付，一個(gè)排序算法是將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)的算法。排序的目的是便于查找循未。

衡量排序算法好壞的三個(gè)重要依據(jù)

• 時(shí)間效率陷猫，即排序的速度秫舌，用時(shí)間復(fù)雜度來(lái)描述算法的運(yùn)行時(shí)間。
• 空間效率绣檬，即占內(nèi)存輔助空間的大小足陨，用空間復(fù)雜度來(lái)描述算法占用額外空間的大小。
• 穩(wěn)定性娇未，若兩個(gè)記錄A和B的關(guān)鍵字值相等墨缘，但排序后A、B的先后次序保持不變零抬，則稱這種排序算法是穩(wěn)定的镊讼。不穩(wěn)定排序算法可能會(huì)在相等的鍵值中改變紀(jì)錄的相對(duì)次序，在這個(gè)狀況下平夜，有可能產(chǎn)生不同的排序結(jié)果蝶棋。

內(nèi)部排序與外部排序

若待排序記錄都在內(nèi)存中，則稱為內(nèi)部排序忽妒。若待排序記錄一部分在內(nèi)存玩裙，一部分在外存，則稱為外部排序段直。

按排序的規(guī)則不同献酗，內(nèi)部排序可分為5類：

• 插入排序（直接插入排序、折半插入排序坷牛、希爾排序）罕偎，其基本思想是每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小京闰，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上颜及，直到對(duì)象全部插入為止。簡(jiǎn)言之蹂楣，邊插入邊排序俏站，保證子序列中隨時(shí)都是排好序的。

• 交換排序（冒泡排序痊土、快速排序）肄扎，其基本思想是兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反）赁酝，則交換之犯祠，直到所有記錄都排好序?yàn)橹埂?/p>

• 選擇排序（簡(jiǎn)單選擇排序，堆排序）酌呆，其基本思想是在待排序的序列中依次選擇關(guān)鍵字最泻庠亍（或最大）的元素作為有序序列的最后一個(gè)元素，直至全部記錄選擇完畢隙袁。

• 歸并排序

• 基數(shù)排序

按排序算法的時(shí)間復(fù)雜度不同痰娱，內(nèi)部排序可分為3類：

• 簡(jiǎn)單的排序算法：時(shí)間效率低弃榨，$O(n^2)$
• 先進(jìn)的排序算法：時(shí)間效率高，$O(nlog_2n)$
• 基數(shù)排序算算法：時(shí)間效率高梨睁，$O(d \times n)$

二鲸睛、常見排序算法

1、直接插入排序

基本思想

在已形成的有序表中線性查找坡贺，并在適當(dāng)位置插入官辈，把原來(lái)位置上的元素向后順移。

算法描述

設(shè)關(guān)鍵字?jǐn)?shù)組為a[0…n-1]拴念。

1. 初始時(shí)钧萍，a[0]自成1個(gè)有序區(qū)褐缠，無(wú)序區(qū)為a[1..n-1]政鼠。令i=1

2. 將a[i]并入當(dāng)前的有序區(qū)a[0…i-1]中形成a[0…i]的有序區(qū)間。

3. i++队魏，并重復(fù)第二步直到 i==n-1公般，排序完成。

如待排序序列 T =（20胡桨，16官帘，31，23昧谊，19刽虹，32，85呢诬，0）涌哲，直接插入排序的中間過程為：

【20】，16尚镰，31阀圾，23，19狗唉，32初烘，85，0

【16分俯，20】肾筐，31，23缸剪，19局齿，32，85橄登，0

【16抓歼，20讥此，31】，23谣妻，19萄喳，32，85蹋半，0

【16他巨，20，23减江，31】染突，19，32辈灼，85份企，0

【16，19巡莹，20司志，23，31】降宅，32骂远，85，0

【16腰根，19激才，20，23额嘿，31瘸恼，32】，85岩睁，0

【16钞脂，19，20捕儒，23冰啃，31，32刘莹，85】阎毅，0

【0，16点弯，19扇调，20，23抢肛，31狼钮，32碳柱，85】

算法分析

• 若設(shè)待排序的對(duì)象個(gè)數(shù)為 n，則算法需要進(jìn)行 n-1 次插入熬芜。

• 最好情況下莲镣，排序前對(duì)象已經(jīng)按關(guān)鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象的關(guān)鍵碼比較 1 次涎拉，移動(dòng) 2 次對(duì)象瑞侮。因此，總的關(guān)鍵碼比較次數(shù)為 n-1鼓拧，對(duì)象移動(dòng)次數(shù)為 2(n-1)半火。

• 最壞情況下，第 i 趟插入時(shí)季俩，第 i 個(gè)對(duì)象必須與前面 i-1 個(gè)對(duì)象都做關(guān)鍵碼比較钮糖，并且每做 1 次比較就要做 1 次數(shù)據(jù)移動(dòng)。則總的關(guān)鍵碼比較次數(shù) CN 和對(duì)象移動(dòng)次數(shù) MN 分別為

CN = \sum_{i=1}^{n-1}i={n(n-1)}/2 \approx {n^2}/2

MN = \sum_{i=1}^{n-1}(i+2) = {(n+4)(n-1)}/2 \approx {n^2}/2

• 若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同种玛，則可取上述最好情況和最壞情況的平均情況藐鹤。在平均情況下的關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 $n^2/4$瓤檐。因此赂韵，直接插入排序的時(shí)間復(fù)雜度為 $O(n^2)$。

• 直接插入排序是一種穩(wěn)定的排序方法挠蛉。

算法實(shí)現(xiàn)

public static void InsertSort(int[] data) 
{
    int i, j;
    int count = data.Length;
    
    for (i = 1; i < count; i++) 
    {
        int t = data[i];
        for(j = i - 1; j >= 0 && data[j] > t; j--)
        {
            data[j + 1] = data[j];
        }
            
        data[j + 1] = t;
    }
}

2祭示、折半插入排序

基本思想

在已形成的有序表中折半查找，并在適當(dāng)位置插入谴古，把原來(lái)位置上的元素向后順移质涛。

算法描述：

在將一個(gè)新元素插入已排好序的數(shù)組的過程中，尋找插入點(diǎn)時(shí)掰担，將待插入?yún)^(qū)域的首元素設(shè)置為a[low]汇陆，末元素設(shè)置為a[high]，則輪比較時(shí)將待插入元素與a[m]带饱，其中m=(low+high)/2相比較,如果比參考元素大毡代，則選擇a[low]到a[m-1]為新的插入?yún)^(qū)域(即high=m-1)，否則選擇a[m+1]到a[high]為新的插入?yún)^(qū)域（即low=m+1）勺疼，如此直至low<=high不成立教寂，即將此位置之后所有元素后移一位，并將新元素插入a[high+1]执庐。

算法分析：

• 折半插入排序是直接插入排序的改進(jìn)酪耕，比較的次數(shù)大大減少，全部元素比較次數(shù)僅為 $O(nlog_2n)$轨淌；

• 算法的平均時(shí)間復(fù)雜度為 $O(n^2)$迂烁，雖然比較次數(shù)大大減少看尼，但移動(dòng)次數(shù)并未減少；

• 在最好情況下盟步，即待排記錄序列已經(jīng)是從小到大排好順序時(shí)狡忙，其時(shí)間復(fù)雜度為 $O(n)$；

• 當(dāng)待排記錄基本有序或待排序序列的元素個(gè)數(shù) n 很小時(shí)址芯，算法的效率也比較高灾茁。

• 空間復(fù)雜度為 $O(1)$；

• 折半插入排序是一種穩(wěn)定的排序方法谷炸。

算法實(shí)現(xiàn)：

public static void BinaryInsertSort(int[] data)
{
    for (int i = 1; i < data.Length; i++)
    {
        int low = 0;
        int high = i - 1;
        int tmp = data[i];

        while (low <= high)
        {
            int mid = (low + high) / 2;

            if (data[i] > data[mid])
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }

        for (int j = i; j > low; j--)
        {
            data[j] = data[j - 1];
        }

        data[low] = tmp;
    }
}

3北专、希爾排序

基本思想

希爾排序，又稱縮小增量排序旬陡，是插入排序的一種更高效的改進(jìn)版本拓颓。其基本思想是對(duì)待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整描孟。所謂“宏觀”調(diào)整驶睦，指的是，“跳躍式”的插入排序匿醒。具體做法為：將記錄序列分成若干子序列场航，分別對(duì)每個(gè)子序列進(jìn)行插入排序。

例如：將 n 個(gè)記錄{R[1]…R[n]}分成 d 個(gè)子序列：

{ R[1]廉羔，R[1+d]溉痢，R[1+2d]，…憋他，R[1+kd] }

{ R[2]孩饼，R[2+d]，R[2+2d]竹挡，…镀娶，R[2+kd] }

...

{ R[d]，R[2d]揪罕，R[3d]梯码，…，R[kd]耸序，R[(k+1)d] }

其中忍些，d 稱為增量，它的值在排序過程中從大到小逐漸縮小坎怪，直至最后一趟排序減為 1罢坝。

希爾排序示例：關(guān)鍵字序列 T=(49，38，65嘁酿，97, 76, 13, 27, 49*隙券，55, 04），請(qǐng)寫出希爾排序的具體實(shí)現(xiàn)過程闹司。

希爾排序的實(shí)現(xiàn)

取定步長(zhǎng)序列娱仔，如dk=5,3,1。

對(duì)每一步長(zhǎng)dk游桩，重復(fù)執(zhí)行如下過程：

把每一子序列第一個(gè)元素看成是有序的牲迫，對(duì)后面的每一個(gè)元素r[i]，重復(fù)執(zhí)行如下過程：

把r[i]暫存在第0號(hào)單元借卧；

尋找相應(yīng)子序列中應(yīng)該插入的位置：從后向前依次比較相應(yīng)子序列中的元素盹憎，直到找到不大于r[i]的元素。

把r[i]放到適當(dāng)?shù)奈恢谩?/p>

希爾排序算法分析

時(shí)間效率：
當(dāng)增量序列為$d(k)=2^{t-k+1}-1$時(shí)铐刘，時(shí)間復(fù)雜度為$O(n^{1.5})$陪每。

空間效率：$O(1)$

算法的穩(wěn)定性： 不穩(wěn)定

初始： (49，38镰吵，65檩禾，97, 76, 13, 27, 49*，55, 04）

結(jié)束： (04疤祭，13盼产，27，38, 49*, 49, 55, 65画株，76, 97）

4辆飘、冒泡排序

基本思想

每趟不斷將記錄兩兩比較啦辐，并按“前小后大”（或“前大后小”）規(guī)則交換谓传。

算法描述

待排序序列 T=(21，25芹关，49续挟，25*，16侥衬，08）诗祸，冒泡排序的排序過程為：

初態(tài)： 21，25轴总，49直颅， 25*，16怀樟， 08

第1趟： 21功偿，25，25*往堡，16械荷， 08 共耍， 49

第2趟： 21，25吨瞎， 16痹兜， 08 ，25*颤诀，49

第3趟： 21字旭，16， 08 崖叫，25谐算， 25*，49

第4趟： 16归露，08 洲脂，21， 25剧包， 25*恐锦，49

第5趟： 08，16疆液， 21一铅， 25， 25*堕油，49

算法分析

• 每趟結(jié)束時(shí)潘飘，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素掉缺；一旦下趟沒有交換發(fā)生卜录，還可以提前結(jié)束排序。

• 時(shí)間效率：$O(n^2)$ —因?yàn)橐紤]最壞情況

• 空間效率：$O(1)$ ——只在交換時(shí)用到一個(gè)緩沖單元

• 冒泡排序是一種穩(wěn)定的排序方法眶明，25和25*在排序前后的次序未改變

• 最好情況下艰毒，即初始排列已經(jīng)有序，只執(zhí)行一趟起泡搜囱，做 n-1 次關(guān)鍵碼比較丑瞧，不移動(dòng)對(duì)象。

• 最壞情況下蜀肘， 即初始排列逆序绊汹，算法要執(zhí)行 n-1 趟起泡，第 i 趟(1<= i< n) 做了n- i 次關(guān)鍵碼比較扮宠，執(zhí)行了n-i 次對(duì)象交換西乖。此時(shí)的比較總次數(shù) CN 和記錄移動(dòng)次數(shù) MN 為：

CN = \sum_{i=1}^{n-1}{(n-i)}={n(n-1)}/2

MN = 3\sum_{i=1}^{n-1}(n-i) = 3n{(n-1)}/2

算法實(shí)現(xiàn)

/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="data"></param>
public static void BubbleSort(int[] data)
{
    int temp = 0;
    bool swapped;

    for (int i = 0; i < data.Length; i++)
    {
        swapped = false;

        for (int j = 0; j < data.Length - 1 - i; j++)
        {
            if (data[j] > data[j + 1])
            {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;

                if (!swapped)
                {
                    swapped = true;
                }
            }
        }

        if (!swapped)
        {
            return;
        }
    }
}

5. 快速排序

基本思想

從待排序列中任取一個(gè)元素 (例如取中間值)作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放浴栽，形成左右兩個(gè)子表荒叼；然后再對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)典鸡。此時(shí)便為有序序列了被廓。

算法分析

• 快速排序是一個(gè)不穩(wěn)定的排序算法

• 最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 $log_2(n+1)$ 萝玷，要求存儲(chǔ)開銷為 $O(log_2n)$嫁乘。

• 如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同球碉，則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序蜓斧，這是最理想的情況。此時(shí)睁冬，快速排序的趟數(shù)最少挎春。

• 就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)部排序方法中最好的一個(gè)豆拨。因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的直奋！
  設(shè)每個(gè)子表的支點(diǎn)都在中間（比較均衡），則：
  第1趟比較施禾，可以確定1個(gè)元素的位置脚线；
  第2趟比較（2個(gè)子表），可以再確定2個(gè)元素的位置弥搞；
  第3趟比較（4個(gè)子表）邮绿，可以再確定4個(gè)元素的位置；
  第4趟比較（8個(gè)子表）攀例，可以再確定8個(gè)元素的位置船逮；
  ……
  只需 $log_2n+1$ 趟便可排好序。而且肛度，每趟需要比較和移動(dòng)的元素也呈指數(shù)下降傻唾，加上編程時(shí)使用了交替逼近技巧，更進(jìn)一步減少了移動(dòng)次數(shù)承耿，所以速度特別快∥泵海快速排序的平均排序效率為 $O(nlog_2n)$加袋；

• 在最壞的情況，排序效率仍為$O(n^2)$抱既。即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下职烧，其遞歸樹成為單支樹，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。這樣蚀之，必須經(jīng)過 (n-1) 趟才能把所有對(duì)象定位蝗敢，而且第 i 趟需要經(jīng)過 (n-i) 次關(guān)鍵碼比較才能找到第 i 個(gè)對(duì)象的安放位置，總的關(guān)鍵碼比較次數(shù)將達(dá)到 $n^2/2$ 足删。

代碼實(shí)現(xiàn)

• 每一趟的子表的形成是采用從兩頭向中間交替式逼近法寿谴；
• 由于每趟中對(duì)各子表的操作都相似，主程序可采用遞歸算法失受。

以數(shù)組 data = {16, 20, 19, 20*, 11, 3} 作為示例讶泰，取子表中間元素作為基準(zhǔn)。初始時(shí)數(shù)組如下：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 16 | 20 | 19 | 20* | 11 | 3

此時(shí)拂到，i = 0, j = 5, middle = data[(i + j) / 2] = 19, 將中間元素與第一個(gè)元素交換痪署，數(shù)組變?yōu)椋?/p>

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 19 | 20 | 16 | 20* | 11 | 3

采用從兩頭向中間交替式逼近法，首先兄旬，從索引 j 開始向前尋找一個(gè)小于等于 middle 的數(shù)狼犯，當(dāng) j = 5 時(shí)，符合條件领铐，將 j=5 的值賦到索引 i 的值辜王，i 做累加操作（即 data[0]=data[5]; i++），數(shù)組如下：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 20 | 16 | 20* | 11 | 3

然后罐孝，再?gòu)乃饕?i （此時(shí) i=1 ）開始向后尋找一個(gè)大于等于 middle 的數(shù)呐馆，當(dāng) i = 1 時(shí)，符合條件莲兢，將索引 i=1 的值賦給索引 j 的值上汹来，j 做累減操作（即 data[5]=data[1]; j--;），此時(shí)數(shù)組為

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 20 | 16 | 20* | 11 | 20

這時(shí)又從索引 j （此時(shí) j=4）開始向前尋找一個(gè)小于等于 middle 的數(shù)改艇，當(dāng) j=4 時(shí)收班，符合條件，將 j=4 的值賦到索引 i 的值谒兄，i 做累加操作（即 data[1]=data[4]; i++）摔桦，數(shù)組如下：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 11 | 16 | 20* | 11 | 20

此時(shí) i=2, j=4, 又從索引 i 開始向后尋找一個(gè)大于等于 middle 的數(shù)，當(dāng) i=3 時(shí)承疲，符合條件邻耕，將索引 i=3 的值賦到索引 j(j=4) 的值上，j 做累減操作（即 data[4]=data[3]; j--;）燕鸽，此時(shí)數(shù)組為

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 11 | 16 | 20* | 20* | 20

此時(shí) i=3兄世，j=3，即 i=j啊研，剛將 middle 的值賦到索引為 3 的值上御滩，數(shù)組變?yōu)?/p>

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 11 | 16 | 19 | 20* | 20

至此鸥拧，排序第一趟結(jié)束，排序后的結(jié)果如下：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
初態(tài) | 16 | 20 | 19 | 20* | 11 | 3
第一趟 | 3 | 11 | 16 | 19 | 20* | 20

可以看出第一趟排序后削解，data[3] 前面的數(shù)字都小于它富弦，a[3] 后面的數(shù)字都大于它。再對(duì)各子表（a[0,1,2]和a[4,5]這二個(gè)子表）重新選擇中心元素并依此規(guī)則調(diào)整氛驮，直到每個(gè)子表的元素只剩一個(gè)腕柜，此時(shí)便為有序序列了。

C#代碼

/// <summary>
/// 快速排序
/// </summary>
/// <param name="data"></param>
public static void QuickSort(int[] data)
{
    QuickSort(data, 0, data.Length - 1);
}

/// <summary>
/// 快速排序柳爽，遞歸方式（采用從兩頭向中間交替式逼近法）
/// </summary>
/// <param name="data"></param>
/// <param name="left"></param>
/// <param name="right"></param>
private static void QuickSort(int[] data, int left, int right)
{
    if (left < right)
    {
        int midIndex = (left + right)/2;

        // 取中間元素作為基準(zhǔn)
        int middle = data[midIndex];

        // 將中間元素與第一個(gè)元素交換
        int tmp = data[left];
        data[left] = data[midIndex];
        data[midIndex] = tmp;
        
        int i = left;
        int j = right;

        while (i < j)
        {
            while (data[j] >= middle && i < j)
            {
                j--;
            }

            if (i < j)
            {
                data[i++] = data[j];
            }

            while (data[i] < middle && i < j)
            {
                i++;
            }

            if (i < j)
            {
                data[j--] = data[i];
            }
        }

        data[i] = middle;

        QuickSort(data, left, i - 1);
        QuickSort(data, i + 1, right);
    }
}

6. 選擇排序

基本思想

在待排序的序列中依次選擇關(guān)鍵字最邢蔽铡（或最大）的元素作為有序序列的最后一個(gè)元素，直至全部記錄選擇完畢磷脯。

如待排序的序列 data = [47 38 25 17 16 12 25* 20 49]蛾找，使用簡(jiǎn)單選擇排序（選擇關(guān)鍵字最小的元素），其過程如下：

[47 38 25 17 16 12 25* 20 49]

12 [38 25 17 16 47 25* 20 49]

12 16 [25 17 38 47 25* 20 49]

12 16 17 [25 38 47 25* 20 49]

12 16 17 20 [38 47 25* 25 49]

12 16 17 20 25* [47 38 25 49]

12 16 17 20 25* 25 [38 47 49]

12 16 17 20 25* 25 38 [47 49]

12 16 17 20 25* 25 38 47 [49]

12 16 17 20 25* 25 38 47 49

12[47 38 25 17 16 12 20 49]
13[38 65 97 76 49 27 49]
13 27[65 97 76 49 38 49]
13 27 38[65 97 76 49 49]
13 27 38 49[65 97 76 49]
13 27 38 49 49[65 97 76]
13 27 38 49 49 65[97 76]
13 27 38 49 49 65 76 97

特點(diǎn)：

1. 算法簡(jiǎn)單, 時(shí)間復(fù)雜度為O(n2)
2. 序列存儲(chǔ)：順序赵誓、鏈?zhǔn)?/li>
3. 穩(wěn)定

/// <summary>
/// 簡(jiǎn)單選擇排序
/// </summary>
/// <param name="data"></param>
public static void SelectionSort(int[] data)
{
    for (int i = 0; i < data.Length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < data.Length; j++)
        {
            if (data[min] > data[j])
            {
                min = j;
            }
        }

        if (min != i)
        {
            int tmp = data[min];
            data[min] = data[i];
            data[i] = tmp;
        }
    }
}

7. 堆排序

若有n個(gè)元素(a1打毛，a2，a3俩功，…幻枉，an)，當(dāng)滿足如下條件：
ai≤a2i ai≥a2i
（1） ai≤a2i+1 或 (2) ai≥a2i+1

其中i=1,2,…,?n/2?诡蜓，則稱此n個(gè)元素a1熬甫，a2，a3蔓罚，…椿肩，an為一個(gè)堆。

若將此元素序列按順序組成一棵完全二叉樹豺谈，則（1）稱為小根堆（二叉樹的所有根結(jié)點(diǎn)值小于或等于左右孩子的值）郑象，（2）稱為大根堆（二叉樹的所有根結(jié)點(diǎn)值大于或等于左右孩子的值）。

堆節(jié)點(diǎn)的訪問[編輯]
通常堆是通過一維數(shù)組來(lái)實(shí)現(xiàn)的茬末。在數(shù)組起始位置為0的情形中：
父節(jié)點(diǎn)i的左子節(jié)點(diǎn)在位置(2i+1);
父節(jié)點(diǎn)i的右子節(jié)點(diǎn)在位置(2i+2);
子節(jié)點(diǎn)i的父節(jié)點(diǎn)在位置floor((i-1)/2);
堆的操作[編輯]
在堆的數(shù)據(jù)結(jié)構(gòu)中厂榛，堆中的最大值總是位于根節(jié)點(diǎn)(在優(yōu)先隊(duì)列中使用堆的話堆中的最小值位于根節(jié)點(diǎn))。堆中定義以下幾種操作：
最大堆調(diào)整（Max_Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整丽惭，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數(shù)據(jù)重新排序
堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)击奶，并做最大堆調(diào)整的遞歸運(yùn)算

原地堆排序[編輯]
基于以上堆相關(guān)的操作，我們可以很容易的定義堆排序吐根。例如正歼，假設(shè)我們已經(jīng)讀入一系列數(shù)據(jù)并創(chuàng)建了一個(gè)堆，一個(gè)最直觀的算法就是反復(fù)的調(diào)用del_max()函數(shù)拷橘，因?yàn)樵摵瘮?shù)總是能夠返回堆中最大的值局义，然后把它從堆中刪除，從而對(duì)這一系列返回值的輸出就得到了該序列的降序排列冗疮。真正的原地堆排序使用了另外一個(gè)小技巧萄唇。堆排序的過程是：
創(chuàng)建一個(gè)堆H[0..n-1]
把堆首（最大值）和堆尾互換
把堆的尺寸縮小1，并調(diào)用shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置
重復(fù)步驟2术幔，直到堆的尺寸為1
平均復(fù)雜度[編輯]
堆排序的平均時(shí)間復(fù)雜度為 {\displaystyle O(n\mathrm {log} n)} O(n\mathrm{log}n)另萤，空間復(fù)雜度為 {\displaystyle \Theta (1)} \Theta(1)。

96 50 85 45 17 31 63 24 17

8.歸并排序

歸并排序指的是將兩個(gè)或兩個(gè)以上的有序序列組合成一個(gè)新的有序序列操作诅挑。

2-路歸并排序

設(shè)初始序列含有n個(gè)記錄四敞，則可看成n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為1拔妥。

兩兩合并忿危，得到?n/2?個(gè)長(zhǎng)度為2或1的有序子序列。

再兩兩合并没龙，……如此重復(fù)铺厨，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。

時(shí)間復(fù)雜度：
T(n)=O(nlogn)

空間復(fù)雜度：
S(n)=O(n)

它是一個(gè)穩(wěn)定的排序方法硬纤。

迭代法[編輯]

申請(qǐng)空間解滓，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
設(shè)定兩個(gè)指針筝家，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑赝菘悖x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針到達(dá)序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾

遞歸法[編輯]

原理如下（假設(shè)序列共有n個(gè)元素）：
將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作溪王，形成 {\displaystyle floor(n/2)} floor(n/2)個(gè)序列腮鞍，排序后每個(gè)序列包含兩個(gè)元素
將上述序列再次歸并，形成 {\displaystyle floor(n/4)} floor(n/4)個(gè)序列在扰，每個(gè)序列包含四個(gè)元素
重復(fù)步驟2缕减，直到所有元素排序完畢

三、總結(jié)