序言
你只管努力，其他交給時(shí)間，時(shí)間會證明一切。
文章標(biāo)記顏色說明：
- 黃色：重要標(biāo)題
- 紅色：用來標(biāo)記結(jié)論
- 綠色：用來標(biāo)記一級論點(diǎn)
- 藍(lán)色：用來標(biāo)記二級論點(diǎn)
決定開一個(gè)算法專欄，希望能幫助大家很好的了解算法。主要深入解析每個(gè)算法，從概念到示例。
我們一起努力，成為更好的自己！
今天第3講，講一下排序算法的堆排序（Heap Sort）
1 基礎(chǔ)介紹
排序算法是很常見的一類問題，主要是將一組數(shù)據(jù)按照某種規(guī)則進(jìn)行排序。
以下是一些常見的排序算法：
冒泡排序（Bubble Sort）
插入排序（Insertion Sort）
選擇排序（Selection Sort）
歸并排序（Merge Sort）
快速排序（Quick Sort）
堆排序（Heap Sort）
一、堆排序介紹
1.1 原理介紹
堆排序（Heap Sort）是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法，其核心思想是將待排序的序列構(gòu)建成一個(gè)最大堆（或最小堆），然后將堆頂元素與最后一個(gè)元素交換，再將剩余元素重新調(diào)整為最大堆（或最小堆），重復(fù)以上步驟直到所有元素都有序。
堆是一種特殊的二叉樹，滿足以下兩個(gè)條件：
堆是一棵完全二叉樹，即除了最后一層，其他層都是滿的，最后一層的節(jié)點(diǎn)都靠左排列。
對于最大堆，任何一個(gè)父節(jié)點(diǎn)的值都大于（或等于）其左右子節(jié)點(diǎn)的值，對于最小堆，則是任何一個(gè)父節(jié)點(diǎn)的值都小于（或等于）其左右子節(jié)點(diǎn)的值。
堆排序的實(shí)現(xiàn)過程如下：
構(gòu)建堆：首先將待排序的序列構(gòu)建成一個(gè)最大堆（或最小堆），可以從最后一個(gè)非葉子節(jié)點(diǎn)開始，從右至左，從下至上依次將每個(gè)節(jié)點(diǎn)調(diào)整為符合堆的性質(zhì)。
堆排序：將堆頂元素與最后一個(gè)元素交換，然后將剩余元素重新調(diào)整為最大堆（或最小堆），再次將堆頂元素與倒數(shù)第二個(gè)元素交換，如此循環(huán)直到排序完成。
細(xì)節(jié)講解?
具體的實(shí)現(xiàn)細(xì)節(jié)如下：
構(gòu)建堆：從最后一個(gè)非葉子節(jié)點(diǎn)開始，依次將每個(gè)節(jié)點(diǎn)調(diào)整為符合堆的性質(zhì)。對于一個(gè)節(jié)點(diǎn)，如果它的左右子節(jié)點(diǎn)中有一個(gè)大于（或小于）該節(jié)點(diǎn)，則交換它們的位置，然后遞歸調(diào)用該節(jié)點(diǎn)所在的子樹，直到該節(jié)點(diǎn)不再有子節(jié)點(diǎn)或者其子節(jié)點(diǎn)都滿足堆的性質(zhì)為止。
堆排序：將堆頂元素與最后一個(gè)元素交換，然后將剩余元素重新調(diào)整為最大堆（或最小堆），再次將堆頂元素與倒數(shù)第二個(gè)元素交換，如此循環(huán)直到排序完成。
1.2 復(fù)雜度?
堆排序：
- 時(shí)間復(fù)雜度為 $O(n\log n)$
- 空間復(fù)雜度為 $O(1)$
相對于其他的排序算法，其實(shí)現(xiàn)簡單，但需要額外的空間來存儲堆數(shù)據(jù)結(jié)構(gòu)。
1.3使用場景
堆排序使用場景堆排序的使用場景與其他排序算法類似，適用于需要對大量數(shù)據(jù)進(jìn)行排序的場景。
1.4 優(yōu)缺點(diǎn)?
優(yōu)點(diǎn)：
其優(yōu)點(diǎn)主要包括：
時(shí)間復(fù)雜度較低：堆排序的時(shí)間復(fù)雜度為 $O(n\log n)$，相對于其他排序算法，其排序速度較快。
不占用額外空間：堆排序是一種原地排序算法，不需要額外的空間來存儲排序結(jié)果。
適用于大數(shù)據(jù)量的排序：堆排序的時(shí)間復(fù)雜度不隨數(shù)據(jù)量的增加而變化，因此適用于大數(shù)據(jù)量的排序。
缺點(diǎn)：
堆排序的缺點(diǎn)主要包括：
不穩(wěn)定性：由于堆排序是通過交換元素來實(shí)現(xiàn)排序的，因此在排序過程中可能會破壞原有的相對順序，導(dǎo)致排序結(jié)果不穩(wěn)定。
實(shí)現(xiàn)復(fù)雜：相對于其他排序算法，堆排序的實(shí)現(xiàn)稍微復(fù)雜一些，需要理解堆數(shù)據(jù)結(jié)構(gòu)的基本原理和實(shí)現(xiàn)過程。
因此，堆排序適用于需要對大量數(shù)據(jù)進(jìn)行排序的場景，特別是在數(shù)據(jù)量較大、內(nèi)存有限的情況下，堆排序可以通過原地排序的方式，節(jié)省額外空間的使用。
二、代碼實(shí)現(xiàn)
2.1 Python 實(shí)現(xiàn)
下面是 Python 實(shí)現(xiàn)堆排序的示例代碼：
def heap_sort(arr):
n = len(arr)
# 構(gòu)建最大堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 排序
for i in range(n - 1, 0, -1):
# 將堆頂元素與最后一個(gè)元素交換
arr[0], arr[i] = arr[i], arr[0]
# 調(diào)整剩余元素為最大堆
heapify(arr, i, 0)
def heapify(arr, n, i):
# 將以 i 為根節(jié)點(diǎn)的子樹調(diào)整為最大堆
largest = i # 初始化最大元素為根節(jié)點(diǎn)
left = 2 * i + 1 # 左子節(jié)點(diǎn)的索引
right = 2 * i + 2 # 右子節(jié)點(diǎn)的索引
# 找出左右子節(jié)點(diǎn)中的最大值
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值不是根節(jié)點(diǎn)，則交換根節(jié)點(diǎn)和最大值，并遞歸調(diào)整子樹
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
測試
下面是 Python 實(shí)現(xiàn)堆排序的測試代碼：
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print("Before sorting:", arr)
heap_sort(arr)
print("After sorting:", arr)
在上面的測試代碼中，定義了一個(gè)整數(shù)數(shù)組?
arr，并將其傳遞給?heap_sort?函數(shù)進(jìn)行排序。排序完成后，使用?
Before sorting: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
After sorting: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
可以看到，排序后的數(shù)組已經(jīng)按照從小到大的順序排列。
2.2Java實(shí)現(xiàn)
下面是 Java 實(shí)現(xiàn)堆排序的示例代碼：
public static void heapSort(int[] arr) {
int n = arr.length;
// 構(gòu)建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 排序
for (int i = n - 1; i > 0; i--) {
// 將堆頂元素與最后一個(gè)元素交換
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
// 調(diào)整剩余元素為最大堆
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
// 將以 i 為根節(jié)點(diǎn)的子樹調(diào)整為最大堆
int largest = i; // 初始化最大元素為根節(jié)點(diǎn)
int left = 2 * i + 1; // 左子節(jié)點(diǎn)的索引
int right = 2 * i + 2; // 右子節(jié)點(diǎn)的索引
// 找出左右子節(jié)點(diǎn)中的最大值
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根節(jié)點(diǎn)，則交換根節(jié)點(diǎn)和最大值，并遞歸調(diào)整子樹
if (largest != i) {
int tmp = arr[i];
arr[i] = arr[largest];
arr[largest] = tmp;
heapify(arr, n, largest);
}
}測試
下面是 Java 實(shí)現(xiàn)堆排序的測試代碼：
import java.util.Arrays;
public class HeapSortTest {
public static void main(String[] args) {
int[] arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
System.out.println("Before sorting: " + Arrays.toString(arr));
heapSort(arr);
System.out.println("After sorting: " + Arrays.toString(arr));
}
}
在上面的測試代碼中，定義了一個(gè)整數(shù)數(shù)組?
arr，并將其傳遞給?heapSort?方法進(jìn)行排序。排序完成后，使用?Arrays.toString?方法將排序后的數(shù)組輸出到控制臺。運(yùn)行測試代碼，將得到以下輸出結(jié)果：
Before sorting: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
After sorting: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
可以看到，排序后的數(shù)組已經(jīng)按照從小到大的順序排列。
圖書推薦
圖書名稱：
- 精通Hadoop3
- pandas1.X實(shí)例講解
- 人人都離不開的算法——圖解算法應(yīng)用
- Python數(shù)據(jù)清洗
精通Hadoop3
pandas1.X實(shí)例講解
人人都離不開的算法——圖解算法應(yīng)用
Python數(shù)據(jù)清洗
活動(dòng)說明
???618，清華社 IT BOOK 多得圖書活動(dòng)開始啦！活動(dòng)時(shí)間為 2023 年 6 月 7 日至 6 月 18 日，清華社為您精選多款高分好書，涵蓋了 C++、Java、Python、前端、后端、數(shù)據(jù)庫、算法與機(jī)器學(xué)習(xí)等多個(gè) IT 開發(fā)領(lǐng)域，適合不同層次的讀者。全場 5 折，掃碼領(lǐng)券更有優(yōu)惠哦！快來京東點(diǎn)擊鏈接 IT BOOK 多得，查看詳情吧！
活動(dòng)鏈接：IT BOOK
??
參與方式?
圖書數(shù)量：本次送出 3 本 ? ?。?！??????
活動(dòng)時(shí)間：截止到 2023-06-16?12:00:00抽獎(jiǎng)方式：
- 評論區(qū)隨機(jī)抽取小伙伴！
留言內(nèi)容，以下方式都可以：
- 根據(jù)文章內(nèi)容進(jìn)行高質(zhì)量評論
參與方式：關(guān)注博主、點(diǎn)贊、收藏，評論區(qū)留言?
中獎(jiǎng)名單?
???? 獲獎(jiǎng)名單????
?中獎(jiǎng)名單：請關(guān)注博主動(dòng)態(tài)
名單公布時(shí)間：2023-06-16?下午文章來源：http://www.zghlxwxcb.cn/news/detail-483146.html
名單詳情：https://bbs.csdn.net/topics/615944050文章來源地址http://www.zghlxwxcb.cn/news/detail-483146.html
到了這里，關(guān)于【算法系列 | 6】深入解析排序算法之——堆排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
