堆排序算法細(xì)則一、堆排序算法概述

堆排序是一種基于二叉堆結(jié)構(gòu)的比較排序算法，具有時間復(fù)雜度為O(nlogn)的特點。它主要通過構(gòu)建最大堆或最小堆來實現(xiàn)排序，主要分為兩個核心步驟：建堆和堆調(diào)整。堆排序算法適用于處理大規(guī)模數(shù)據(jù)集，尤其適用于內(nèi)存空間有限的情況。

二、堆排序算法原理

（一）二叉堆的定義

二叉堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，通常以數(shù)組形式存儲，滿足以下性質(zhì)：

1.完全二叉樹：除了最后一層，其他層都是滿的，且最后一層從左到右填充。

2.堆屬性：

-最大堆：父節(jié)點的值總是大于或等于子節(jié)點的值。

-最小堆：父節(jié)點的值總是小于或等于子節(jié)點的值。

（二）堆排序的基本操作

1.建堆（Heapify）：將無序數(shù)組轉(zhuǎn)化為滿足堆屬性的樹形結(jié)構(gòu)。

2.堆調(diào)整（SiftDown/Up）：通過交換節(jié)點，確保子樹滿足堆屬性。

3.排序過程：

-將無序數(shù)組轉(zhuǎn)化為最大堆，此時最大值位于根節(jié)點。

-將根節(jié)點與末尾元素交換，減少堆的大小，并重新調(diào)整堆。

-重復(fù)上述過程，直至堆為空。

三、堆排序算法實現(xiàn)

（一）建堆步驟（以最大堆為例）

1.從最后一個非葉子節(jié)點開始：

-非葉子節(jié)點的索引為`n//2-1`（n為數(shù)組長度）。

2.從后向前遍歷，對每個節(jié)點進(jìn)行堆調(diào)整：

-調(diào)用`siftDown`函數(shù)確保子樹滿足最大堆屬性。

示例：

假設(shè)數(shù)組為`[4,10,3,5,1]`，建堆過程如下：

1.非葉子節(jié)點索引：`2`（值為`3`）。

2.調(diào)整節(jié)點`3`，與子節(jié)點`4`和`10`比較，交換`3`與`10`。

3.繼續(xù)調(diào)整`10`的子樹，確保堆屬性。

（二）堆調(diào)整算法（SiftDown）

1.輸入：節(jié)點索引`i`，堆大小`n`，數(shù)組`arr`。

2.步驟：

-初始化`largest=i`。

-左子節(jié)點索引：`2i+1`。

-右子節(jié)點索引：`2i+2`。

-比較`largest`與左右子節(jié)點，更新`largest`。

-若`largest`不等于`i`，交換`arr[i]`與`arr[largest]`，并遞歸調(diào)整子樹。

偽代碼：

functionsiftDown(arr,i,n):

largest=i

left=2i+1

right=2i+2

ifleft<nandarr[left]>arr[largest]:

largest=left

ifright<nandarr[right]>arr[largest]:

largest=right

iflargest!=i:

swap(arr[i],arr[largest])

siftDown(arr,largest,n)

（三）堆排序完整流程

1.建最大堆：

-從`n//2-1`到`0`，依次調(diào)用`siftDown`。

2.排序：

-交換根節(jié)點（最大值）與末尾元素，堆大小減`1`。

-調(diào)整根節(jié)點，重復(fù)上述步驟。

示例：

arr=[4,10,3,5,1]

n=len(arr)

//建堆

foriinrange(n//2-1,-1,-1):

siftDown(arr,i,n)

//排序

foriinrange(n-1,0,-1):

swap(arr[0],arr[i])

siftDown(arr,0,i)

四、堆排序算法分析

（一）時間復(fù)雜度

-建堆：O(n)。

-每次堆調(diào)整：O(logn)。

-總時間：O(nlogn)。

（二）空間復(fù)雜度

-輔助空間：O(1)，原地排序。

（三）優(yōu)缺點

優(yōu)點：

-時間復(fù)雜度穩(wěn)定，適合大規(guī)模數(shù)據(jù)。

-原地排序，空間效率高。

缺點：

-相比快速排序，常數(shù)因子較大，實際性能可能較低。

-非穩(wěn)定排序。

五、應(yīng)用場景

堆排序適用于以下場景：

1.數(shù)據(jù)量較大，但內(nèi)存有限。

2.需要穩(wěn)定的時間復(fù)雜度。

3.排序穩(wěn)定性要求不高。

示例數(shù)據(jù)：

假設(shè)數(shù)組長度為`1000`，堆排序的時間復(fù)雜度約為`1000log1000≈10000`次比較。

三、堆排序算法實現(xiàn)（續(xù)）

（一）建堆步驟（以最大堆為例）詳細(xì)說明

建堆是堆排序的基礎(chǔ)，目標(biāo)是確保整個二叉樹滿足最大堆屬性。以下是詳細(xì)的步驟和考慮因素：

1.確定非葉子節(jié)點的范圍：

在完全二叉樹中，從最后一個非葉子節(jié)點開始向下調(diào)整，才能保證所有子樹都滿足堆屬性。

-計算方法：對于長度為`n`的數(shù)組，最后一個非葉子節(jié)點的索引為`n//2-1`。

-示例：數(shù)組`[4,10,3,5,1]`，`n=5`，非葉子節(jié)點索引為`4//2-1=1`（值為`10`）。

2.從后向前遍歷，逐個調(diào)整節(jié)點：

-遍歷順序：從`n//2-1`到`0`，依次對每個節(jié)點調(diào)用`siftDown`函數(shù)。

-原因：后續(xù)節(jié)點的子樹已經(jīng)滿足堆屬性，只需調(diào)整當(dāng)前節(jié)點即可。

3.`siftDown`函數(shù)的具體實現(xiàn)：

-輸入?yún)?shù)：

-`arr`：待排序數(shù)組。

-`i`：當(dāng)前節(jié)點索引。

-`n`：堆的大小（即當(dāng)前待調(diào)整的元素數(shù)量）。

-核心邏輯：

1.初始化最大值索引：`largest=i`。

2.計算子節(jié)點索引：

-左子節(jié)點：`left=2i+1`。

-右子節(jié)點：`right=2i+2`。

3.比較子節(jié)點與當(dāng)前節(jié)點：

-若左子節(jié)點存在且值大于`arr[largest]`，則`largest=left`。

-若右子節(jié)點存在且值大于`arr[largest]`，則`largest=right`。

4.判斷是否需要交換：

-若`largest!=i`，說明子節(jié)點中存在更大值，需交換`arr[i]`與`arr[largest]`。

-交換后，子樹可能不再滿足堆屬性，因此遞歸調(diào)用`siftDown(arr,largest,n)`調(diào)整子樹。

-示例：

-數(shù)組`[4,10,3,5,1]`，`i=1`（值`10`），`n=5`。

-左子節(jié)點`left=3`（值`3`），右子節(jié)點`right=4`（值`1`）。

-比較`3`和`1`，`largest=1`（無變化）。

-無需交換，結(jié)束調(diào)整。

4.建堆完成標(biāo)志：

-當(dāng)遍歷到`i=0`時，整個數(shù)組滿足最大堆屬性，建堆完成。

（二）堆調(diào)整算法（SiftDown）詳細(xì)步驟

堆調(diào)整是確保子樹滿足堆屬性的關(guān)鍵操作，以下是詳細(xì)步驟：

1.初始化最大值索引：

-選擇當(dāng)前節(jié)點作為最大值候選，`largest=i`。

2.計算子節(jié)點索引：

-左子節(jié)點：`left=2i+1`。

-右子節(jié)點：`right=2i+2`。

3.比較子節(jié)點與當(dāng)前節(jié)點：

-左子節(jié)點比較：

-若`left<n`且`arr[left]>arr[largest]`，則`largest=left`。

-右子節(jié)點比較：

-若`right<n`且`arr[right]>arr[largest]`，則`largest=right`。

-注意：優(yōu)先比較左子節(jié)點，因為左子節(jié)點始終存在（除非是葉子節(jié)點）。

4.判斷是否需要交換：

-若`largest!=i`，說明子節(jié)點中存在更大值，需交換`arr[i]`與`arr[largest]`。

-交換后，子樹可能不再滿足堆屬性，因此遞歸調(diào)用`siftDown`調(diào)整子樹。

-若`largest==i`，說明當(dāng)前節(jié)點已是最大值，無需交換。

5.遞歸終止條件：

-當(dāng)`largest==i`或子節(jié)點索引超出范圍時，遞歸結(jié)束。

偽代碼示例：

functionsiftDown(arr,i,n):

largest=i

left=2i+1

right=2i+2

ifleft<nandarr[left]>arr[largest]:

largest=left

ifright<nandarr[right]>arr[largest]:

largest=right

iflargest!=i:

swap(arr[i],arr[largest])

siftDown(arr,largest,n)

（三）堆排序完整流程詳細(xì)步驟

堆排序分為建堆和排序兩個主要階段，以下是完整步驟：

1.建最大堆：

-輸入：無序數(shù)組`arr`，長度`n`。

-步驟：

1.從最后一個非葉子節(jié)點開始，到根節(jié)點（索引`0`），依次調(diào)用`siftDown`。

2.示例代碼：

```pseudo

forifromn//2-1downto0:

siftDown(arr,i,n)

```

-目的：確保數(shù)組滿足最大堆屬性，此時最大值位于根節(jié)點`arr[0]`。

2.排序（重復(fù)調(diào)整堆）：

-步驟：

1.交換根節(jié)點（最大值）與末尾元素`arr[n-1]`。

2.減少堆的大小`n`，此時`arr[n-1]`已排序。

3.調(diào)整根節(jié)點`arr[0]`，確保剩余部分仍滿足最大堆屬性（調(diào)用`siftDown(arr,0,n-1)`）。

4.重復(fù)上述步驟，直至堆大小`n`減至`1`。

-示例代碼：

```pseudo

forifromn-1downto1:

swap(arr[0],arr[i])

siftDown(arr,0,i)

```

-最終結(jié)果：數(shù)組按升序排列。

完整示例：

初始數(shù)組`[4,10,3,5,1]`，`n=5`。

1.建堆：

-`i=1`（值`10`）：無交換。

-`i=0`（值`4`）：交換`4`與`10`，數(shù)組變?yōu)閌[10,4,3,5,1]`。

-建堆完成，最大堆`[10,4,3,5,1]`。

2.排序：

-交換`10`與`1`，數(shù)組`[1,4,3,5,10]`，`n=4`。

-調(diào)整`4`，交換`4`與`5`，數(shù)組`[1,5,3,4,10]`。

-交換`5`與`3`，數(shù)組`[1,3,5,4,10]`，`n=3`。

-調(diào)整`3`，無交換，數(shù)組`[1,3,5,4,10]`。

-交換`5`與`4`，數(shù)組`[1,3,4,5,10]`，`n=2`。

-調(diào)整`3`，無交換，數(shù)組`[1,3,4,5,10]`。

-交換`3`與`1`，數(shù)組`[1,3,4,5,10]`，`n=1`。

-排序完成。

四、堆排序算法分析（續(xù)）

（一）時間復(fù)雜度詳細(xì)分解

堆排序的時間復(fù)雜度為O(nlogn)，以下是詳細(xì)分解：

1.建堆階段：

-建堆需要遍歷`n//2`個節(jié)點（從`n//2-1`到`0`）。

-每次調(diào)用`siftDown`的平均比較次數(shù)為O(logn)。

-因此，建堆時間復(fù)雜度為O(n)。

2.排序階段：

-排序需要執(zhí)行`n-1`次交換和調(diào)整。

-每次調(diào)整的深度為O(logn)。

-因此，排序時間復(fù)雜度為O(nlogn)。

3.總時間復(fù)雜度：

-O(n)+O(nlogn)=O(nlogn)。

實際示例：

對于`n=1000`，

-建堆約需`1000/2log1000≈50010=5000`次比較。

-排序約需`999log1000≈9990`次比較。

-總比較次數(shù)約`14990`，符合O(nlogn)級別。

（二）空間復(fù)雜度詳細(xì)說明

堆排序的空間復(fù)雜度為O(1)，具體分析如下：

1.輔助空間：

-堆排序是原地排序，僅使用常數(shù)個額外變量（如`i`、`left`、`right`等）。

-不需要額外的存儲空間，因此輔助空間為O(1)。

2.與歸并排序?qū)Ρ龋?/p>

-歸并排序需要O(n)的輔助空間，而堆排序無需額外空間。

-在內(nèi)存有限的情況下，堆排序更具優(yōu)勢。

（三）優(yōu)缺點詳細(xì)對比

優(yōu)點：

1.時間復(fù)雜度穩(wěn)定：無論輸入數(shù)據(jù)如何，時間復(fù)雜度始終為O(nlogn)。

2.原地排序：僅使用O(1)輔助空間，適合內(nèi)存受限場景。

3.非比較排序的補(bǔ)充：在特定場景下（如數(shù)據(jù)已部分排序）可能表現(xiàn)更優(yōu)。

缺點：

1.非穩(wěn)定排序：相同值的元素順序可能改變。

2.常數(shù)因子較大：實際運行速度通常慢于快速排序或歸并排序。

3.堆調(diào)整開銷：每次`siftDown`需要遞歸調(diào)用，開銷相對較大。

五、堆排序算法實現(xiàn)示例（Python）

```python

defheap_sort(arr):

n=len(arr)

建最大堆

foriinrange(n//2-1,-1,-1):

sift_down(arr,i,n)

排序

foriinrange(n-1,0,-1):

arr[0],arr[i]=arr[i],arr[0]交換根節(jié)點與末尾元素

sift_down(arr,0,i)調(diào)整剩余堆

defsift_down(arr,i,n):

largest=i

left=2i+1

right=2i+2

ifleft<nandarr[left]>arr[largest]:

largest=left

ifright<nandarr[right]>arr[largest]:

largest=right

iflargest!=i:

arr[i],arr[largest]=arr[largest],arr[i]交換

sift_down(arr,largest,n)遞歸調(diào)整子樹

示例

arr=[4,10,3,5,1]

heap_sort(arr)

print(arr)輸出[1,3,4,5,10]

六、堆排序算法應(yīng)用場景詳細(xì)說明

堆排序適用于以下場景，具體原因如下：

1.數(shù)據(jù)量較大，內(nèi)存有限：

-由于O(1)輔助空間，適合處理內(nèi)存受限的情況。

-示例：嵌入式系統(tǒng)或內(nèi)存優(yōu)化的數(shù)據(jù)庫索引。

2.需要穩(wěn)定時間復(fù)雜度：

-O(nlogn)時間復(fù)雜度在數(shù)據(jù)量較大時表現(xiàn)穩(wěn)定。

-示例：科學(xué)計算或需要可預(yù)測運行時間的系統(tǒng)。

3.排序穩(wěn)定性要求不高：

-堆排序非穩(wěn)定，適合對元素順序不敏感的場景。

-示例：數(shù)值排序或內(nèi)部排序階段。

4.作為其他算法的輔助：

-堆可用于優(yōu)先隊列實現(xiàn)，或作為快速排序的優(yōu)化。

-示例：Dijkstra算法中的優(yōu)先隊列。

5.不適合小數(shù)據(jù)集：

-由于O(logn)的調(diào)整開銷，小數(shù)據(jù)集效率較低。

-建議：小數(shù)據(jù)集可使用插入排序等更高效算法。

七、堆排序算法優(yōu)化建議

1.循環(huán)實現(xiàn)`siftDown`：

-避免遞歸調(diào)用，減少?？臻g開銷。

-示例：使用循環(huán)代替遞歸。

2.上浮操作優(yōu)化：

-最大堆可優(yōu)化為上浮操作（SiftUp），但通常建堆使用下沉（SiftDown）更高效。

3.并行化處理：

-對于極大數(shù)據(jù)集，可并行調(diào)整多個子樹。

-注意：并行化實現(xiàn)復(fù)雜度較高，需權(quán)衡收益。

4.選擇合適的堆類型：

-最大堆適用于升序排序，最小堆適用于降序排序。

-示例：根據(jù)需求選擇堆類型。

總結(jié)：堆排序是一種高效、穩(wěn)定的排序算法，尤其適用于內(nèi)存受限場景。通過合理優(yōu)化，可進(jìn)一步提升其性能和適用性。

一、堆排序算法概述

堆排序是一種基于二叉堆結(jié)構(gòu)的比較排序算法，具有時間復(fù)雜度為O(nlogn)的特點。它主要通過構(gòu)建最大堆或最小堆來實現(xiàn)排序，主要分為兩個核心步驟：建堆和堆調(diào)整。堆排序算法適用于處理大規(guī)模數(shù)據(jù)集，尤其適用于內(nèi)存空間有限的情況。

二、堆排序算法原理

（一）二叉堆的定義

二叉堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，通常以數(shù)組形式存儲，滿足以下性質(zhì)：

1.完全二叉樹：除了最后一層，其他層都是滿的，且最后一層從左到右填充。

2.堆屬性：

-最大堆：父節(jié)點的值總是大于或等于子節(jié)點的值。

-最小堆：父節(jié)點的值總是小于或等于子節(jié)點的值。

（二）堆排序的基本操作

1.建堆（Heapify）：將無序數(shù)組轉(zhuǎn)化為滿足堆屬性的樹形結(jié)構(gòu)。

2.堆調(diào)整（SiftDown/Up）：通過交換節(jié)點，確保子樹滿足堆屬性。

3.排序過程：

-將無序數(shù)組轉(zhuǎn)化為最大堆，此時最大值位于根節(jié)點。

-將根節(jié)點與末尾元素交換，減少堆的大小，并重新調(diào)整堆。

-重復(fù)上述過程，直至堆為空。

三、堆排序算法實現(xiàn)

（一）建堆步驟（以最大堆為例）

1.從最后一個非葉子節(jié)點開始：

-非葉子節(jié)點的索引為`n//2-1`（n為數(shù)組長度）。

2.從后向前遍歷，對每個節(jié)點進(jìn)行堆調(diào)整：

-調(diào)用`siftDown`函數(shù)確保子樹滿足最大堆屬性。

示例：

假設(shè)數(shù)組為`[4,10,3,5,1]`，建堆過程如下：

1.非葉子節(jié)點索引：`2`（值為`3`）。

2.調(diào)整節(jié)點`3`，與子節(jié)點`4`和`10`比較，交換`3`與`10`。

3.繼續(xù)調(diào)整`10`的子樹，確保堆屬性。

（二）堆調(diào)整算法（SiftDown）

1.輸入：節(jié)點索引`i`，堆大小`n`，數(shù)組`arr`。

2.步驟：

-初始化`largest=i`。

-左子節(jié)點索引：`2i+1`。

-右子節(jié)點索引：`2i+2`。

-比較`largest`與左右子節(jié)點，更新`largest`。

-若`largest`不等于`i`，交換`arr[i]`與`arr[largest]`，并遞歸調(diào)整子樹。

偽代碼：

functionsiftDown(arr,i,n):

largest=i

left=2i+1

right=2i+2

ifleft<nandarr[left]>arr[largest]:

largest=left

ifright<nandarr[right]>arr[largest]:

largest=right

iflargest!=i:

swap(arr[i],arr[largest])

siftDown(arr,largest,n)

（三）堆排序完整流程

1.建最大堆：

-從`n//2-1`到`0`，依次調(diào)用`siftDown`。

2.排序：

-交換根節(jié)點（最大值）與末尾元素，堆大小減`1`。

-調(diào)整根節(jié)點，重復(fù)上述步驟。

示例：

arr=[4,10,3,5,1]

n=len(arr)

//建堆

foriinrange(n//2-1,-1,-1):

siftDown(arr,i,n)

//排序

foriinrange(n-1,0,-1):

swap(arr[0],arr[i])

siftDown(arr,0,i)

四、堆排序算法分析

（一）時間復(fù)雜度

-建堆：O(n)。

-每次堆調(diào)整：O(logn)。

-總時間：O(nlogn)。

（二）空間復(fù)雜度

-輔助空間：O(1)，原地排序。

（三）優(yōu)缺點

優(yōu)點：

-時間復(fù)雜度穩(wěn)定，適合大規(guī)模數(shù)據(jù)。

-原地排序，空間效率高。

缺點：

-相比快速排序，常數(shù)因子較大，實際性能可能較低。

-非穩(wěn)定排序。

五、應(yīng)用場景

堆排序適用于以下場景：

1.數(shù)據(jù)量較大，但內(nèi)存有限。

2.需要穩(wěn)定的時間復(fù)雜度。

3.排序穩(wěn)定性要求不高。

示例數(shù)據(jù)：

假設(shè)數(shù)組長度為`1000`，堆排序的時間復(fù)雜度約為`1000log1000≈10000`次比較。

三、堆排序算法實現(xiàn)（續(xù)）

（一）建堆步驟（以最大堆為例）詳細(xì)說明

建堆是堆排序的基礎(chǔ)，目標(biāo)是確保整個二叉樹滿足最大堆屬性。以下是詳細(xì)的步驟和考慮因素：

1.確定非葉子節(jié)點的范圍：

在完全二叉樹中，從最后一個非葉子節(jié)點開始向下調(diào)整，才能保證所有子樹都滿足堆屬性。

-計算方法：對于長度為`n`的數(shù)組，最后一個非葉子節(jié)點的索引為`n//2-1`。

-示例：數(shù)組`[4,10,3,5,1]`，`n=5`，非葉子節(jié)點索引為`4//2-1=1`（值為`10`）。

2.從后向前遍歷，逐個調(diào)整節(jié)點：

-遍歷順序：從`n//2-1`到`0`，依次對每個節(jié)點調(diào)用`siftDown`函數(shù)。

-原因：后續(xù)節(jié)點的子樹已經(jīng)滿足堆屬性，只需調(diào)整當(dāng)前節(jié)點即可。

3.`siftDown`函數(shù)的具體實現(xiàn)：

-輸入?yún)?shù)：

-`arr`：待排序數(shù)組。

-`i`：當(dāng)前節(jié)點索引。

-`n`：堆的大?。串?dāng)前待調(diào)整的元素數(shù)量）。

-核心邏輯：

1.初始化最大值索引：`largest=i`。

2.計算子節(jié)點索引：

-左子節(jié)點：`left=2i+1`。

-右子節(jié)點：`right=2i+2`。

3.比較子節(jié)點與當(dāng)前節(jié)點：

-若左子節(jié)點存在且值大于`arr[largest]`，則`largest=left`。

-若右子節(jié)點存在且值大于`arr[largest]`，則`largest=right`。

4.判斷是否需要交換：

-若`largest!=i`，說明子節(jié)點中存在更大值，需交換`arr[i]`與`arr[largest]`。

-交換后，子樹可能不再滿足堆屬性，因此遞歸調(diào)用`siftDown(arr,largest,n)`調(diào)整子樹。

-示例：

-數(shù)組`[4,10,3,5,1]`，`i=1`（值`10`），`n=5`。

-左子節(jié)點`left=3`（值`3`），右子節(jié)點`right=4`（值`1`）。

-比較`3`和`1`，`largest=1`（無變化）。

-無需交換，結(jié)束調(diào)整。

4.建堆完成標(biāo)志：

-當(dāng)遍歷到`i=0`時，整個數(shù)組滿足最大堆屬性，建堆完成。

（二）堆調(diào)整算法（SiftDown）詳細(xì)步驟

堆調(diào)整是確保子樹滿足堆屬性的關(guān)鍵操作，以下是詳細(xì)步驟：

1.初始化最大值索引：

-選擇當(dāng)前節(jié)點作為最大值候選，`largest=i`。

2.計算子節(jié)點索引：

-左子節(jié)點：`left=2i+1`。

-右子節(jié)點：`right=2i+2`。

3.比較子節(jié)點與當(dāng)前節(jié)點：

-左子節(jié)點比較：

-若`left<n`且`arr[left]>arr[largest]`，則`largest=left`。

-右子節(jié)點比較：

-若`right<n`且`arr[right]>arr[largest]`，則`largest=right`。

-注意：優(yōu)先比較左子節(jié)點，因為左子節(jié)點始終存在（除非是葉子節(jié)點）。

4.判斷是否需要交換：

-若`largest!=i`，說明子節(jié)點中存在更大值，需交換`arr[i]`與`arr[largest]`。

-交換后，子樹可能不再滿足堆屬性，因此遞歸調(diào)用`siftDown`調(diào)整子樹。

-若`largest==i`，說明當(dāng)前節(jié)點已是最大值，無需交換。

5.遞歸終止條件：

-當(dāng)`largest==i`或子節(jié)點索引超出范圍時，遞歸結(jié)束。

偽代碼示例：

functionsiftDown(arr,i,n):

largest=i

left=2i+1

right=2i+2

ifleft<nandarr[left]>arr[largest]:

largest=left

ifright<nandarr[right]>arr[largest]:

largest=right

iflargest!=i:

swap(arr[i],arr[largest])

siftDown(arr,largest,n)

（三）堆排序完整流程詳細(xì)步驟

堆排序分為建堆和排序兩個主要階段，以下是完整步驟：

1.建最大堆：

-輸入：無序數(shù)組`arr`，長度`n`。

-步驟：

1.從最后一個非葉子節(jié)點開始，到根節(jié)點（索引`0`），依次調(diào)用`siftDown`。

2.示例代碼：

```pseudo

forifromn//2-1downto0:

siftDown(arr,i,n)

```

-目的：確保數(shù)組滿足最大堆屬性，此時最大值位于根節(jié)點`arr[0]`。

2.排序（重復(fù)調(diào)整堆）：

-步驟：

1.交換根節(jié)點（最大值）與末尾元素`arr[n-1]`。

2.減少堆的大小`n`，此時`arr[n-1]`已排序。

3.調(diào)整根節(jié)點`arr[0]`，確保剩余部分仍滿足最大堆屬性（調(diào)用`siftDown(arr,0,n-1)`）。

4.重復(fù)上述步驟，直至堆大小`n`減至`1`。

-示例代碼：

```pseudo

forifromn-1downto1:

swap(arr[0],arr[i])

siftDown(arr,0,i)

```

-最終結(jié)果：數(shù)組按升序排列。

完整示例：

初始數(shù)組`[4,10,3,5,1]`，`n=5`。

1.建堆：

-`i=1`（值`10`）：無交換。

-`i=0`（值`4`）：交換`4`與`10`，數(shù)組變?yōu)閌[10,4,3,5,1]`。

-建堆完成，最大堆`[10,4,3,5,1]`。

2.排序：

-交換`10`與`1`，數(shù)組`[1,4,3,5,10]`，`n=4`。

-調(diào)整`4`，交換`4`與`5`，數(shù)組`[1,5,3,4,10]`。

-交換`5`與`3`，數(shù)組`[1,3,5,4,10]`，`n=3`。

-調(diào)整`3`，無交換，數(shù)組`[1,3,5,4,10]`。

-交換`5`與`4`，數(shù)組`[1,3,4,5,10]`，`n=2`。

-調(diào)整`3`，無交換，數(shù)組`[1,3,4,5,10]`。

-交換`3`與`1`，數(shù)組`[1,3,4,5,10]`，`n=1`。

-排序完成。

四、堆排序算法分析（續(xù)）

（一）時間復(fù)雜度詳細(xì)分解

堆排序的時間復(fù)雜度為O(nlogn)，以下是詳細(xì)分解：

1.建堆階段：

-建堆需要遍歷`n//2`個節(jié)點（從`n//2-1`到`0`）。

-每次調(diào)用`siftDown`的平均比較次數(shù)為O(logn)。

-因此，建堆時間復(fù)雜度為O(n)。

2.排序階段：

-排序需要執(zhí)行`n-1`次交換和調(diào)整。

-每次調(diào)整的深度為O(logn)。

-因此，排序時間復(fù)雜度為O(nlogn)。

3.總時間復(fù)雜度：

-O(n)+O(nlogn)=O(nlogn)。

實際示例：

對于`n=1000`，

-建堆約需`1000/2log1000≈50010=5000`次比較。

-排序約需`999log1000≈9990`次比較。

-總比較次數(shù)約`14990`，符合O(nlogn)級別。

（二）空間復(fù)雜度詳細(xì)說明

堆排序的空間復(fù)雜度為O(1)，具體分析如下：

1.輔助空間：

-堆排序是原地排序，僅使用常數(shù)個額外變量（如`i`、`left`、`right`等）。

-不需要額外的存儲空間，因此輔助空間為O(1)。

2.與歸并排序?qū)Ρ龋?/p>

-歸并排序需要O(n)的輔助空間，而堆排序無需額外空間。

-在內(nèi)存有限的情況下，堆排序更具優(yōu)勢。

（三）優(yōu)缺點詳細(xì)對比

優(yōu)點：

1.時間復(fù)雜度穩(wěn)定：無論輸入數(shù)據(jù)如何，時間復(fù)雜度始終為O(nlogn)。

2.原地排序：僅使用O(1)輔助空間，適合內(nèi)存受限場景。

3.非比較排序的補(bǔ)充：在特定場景下（如數(shù)據(jù)已部分排序）可能表現(xiàn)