基本思想

堆排序的基本思想是，將待排序的元素構(gòu)建成一個(gè)最大堆或最小堆。對(duì)于最大堆來(lái)說，堆頂是整個(gè)堆中的最大元素；對(duì)于最小堆來(lái)說，堆頂是整個(gè)堆中的最小元素。然后，將堆頂元素與堆中最后一個(gè)元素交換，并從堆中移除這個(gè)最大或最小元素，再調(diào)整剩余的堆，使其滿足堆的性質(zhì)。這個(gè)過程重復(fù)進(jìn)行，直到堆中只剩下一個(gè)元素，此時(shí)數(shù)組就被排序了。

算法步驟

1. 構(gòu)建最大堆：將待排序的數(shù)組從最后一個(gè)非葉子節(jié)點(diǎn)開始不斷向前使用向下調(diào)整，使之成為一個(gè)最大堆。
2. 交換堆頂元素與堆尾元素：將堆頂元素（最大值）與堆中最后一個(gè)元素交換，此時(shí)最后一個(gè)元素即為最大值，放置在數(shù)組的正確位置。
3. 調(diào)整堆：交換后的堆可能不滿足最大堆的性質(zhì)，因此需要從堆頂開始重新調(diào)整堆。
4. 重復(fù)步驟2和3：重復(fù)上述過程，每次都會(huì)將最大的元素放置在數(shù)組的正確位置，直至數(shù)組完全有序。

示例代碼（從小到大）

建堆有向上調(diào)整建堆和向下調(diào)整建堆兩種，使用向上調(diào)整建堆的時(shí)間復(fù)雜度為O(nlogn)，而向下調(diào)整建堆的時(shí)間復(fù)雜度為O(n)，所以我們選擇向下調(diào)整建堆（向下調(diào)整詳細(xì)請(qǐng)看我發(fā)布的堆博客）

向下調(diào)整

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void AdjustDown(HPDataType* a, int n, int parent)//n為a數(shù)組元素個(gè)數(shù)
{int child = (parent * 2) + 1; // 左子節(jié)點(diǎn)位置（假設(shè)法找大孩子）while (child < n) // 如果有左子節(jié)點(diǎn)，進(jìn)行循環(huán){if (a[child] < a[child + 1] && child + 1 < n) // 如果右子節(jié)點(diǎn)比左子節(jié)點(diǎn)大且右子節(jié)點(diǎn)存在child++; // 右子節(jié)點(diǎn)作為比較對(duì)象（大孩子）if (a[child] > a[parent]) // 如果子節(jié)點(diǎn)比父節(jié)點(diǎn)大{Swap(&a[child], &a[parent]); // 交換子節(jié)點(diǎn)和父節(jié)點(diǎn)的值parent = child; // 更新父節(jié)點(diǎn)位置child = (parent * 2) + 1; // 更新子節(jié)點(diǎn)位置}else{break; // 如果子節(jié)點(diǎn)比父節(jié)點(diǎn)小，則跳出循環(huán)}}
}

建大堆并排序

// 堆排序
void HeapSort(int* a, int n)//n為a數(shù)組元素個(gè)數(shù)
{// 建大堆for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(a, n, i); // 向下調(diào)整堆}// 排序for (int i = n - 1; i > 0; i--){Swap(&a[i], &a[0]); // 交換堆頂元素和最后一個(gè)元素，則最后一個(gè)元素為最大的元素AdjustDown(a, i, 0); // 向下調(diào)整堆，讓堆頂變?yōu)樽畲髷?shù)}
}

時(shí)間復(fù)雜度

堆排序的時(shí)間復(fù)雜度是O(nlogn)。構(gòu)建最大堆的時(shí)間復(fù)雜度是O(n)，每次調(diào)整堆的時(shí)間復(fù)雜度是O(logn)，由于需要調(diào)整n-1次，所以總的時(shí)間復(fù)雜度為O(nlogn)。

空間復(fù)雜度

堆排序的空間復(fù)雜度是O(1)。它是在原地進(jìn)行排序的，不需要額外的存儲(chǔ)空間。

優(yōu)點(diǎn)

• 性能穩(wěn)定：堆排序的時(shí)間復(fù)雜度在最好、最壞和平均情況下都是O(nlogn)，因此性能穩(wěn)定。
• 空間效率高：由于是原地排序算法，不需要額外的內(nèi)存空間。

缺點(diǎn)

• 實(shí)現(xiàn)復(fù)雜：相對(duì)于冒泡排序、插入排序等簡(jiǎn)單排序算法，堆排序的實(shí)現(xiàn)相對(duì)復(fù)雜。
• 不穩(wěn)定性：堆排序不是一個(gè)穩(wěn)定的排序算法，相等的元素可能在排序過程中改變它們的相對(duì)順序。

總結(jié)來(lái)說，堆排序是一種高效、穩(wěn)定的排序算法，適用于大規(guī)模數(shù)據(jù)的排序，盡管它的實(shí)現(xiàn)較為復(fù)雜。在實(shí)際應(yīng)用中，堆排序常用于需要性能穩(wěn)定且空間復(fù)雜度低的場(chǎng)景。