---

一、概述

堆排序是J.W.J. Williams于1964年提出的。他提出了一種利用堆的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序的算法，并將其稱為堆排序。堆排序是基于選擇排序的一種改進(jìn)，通過(guò)維護(hù)一個(gè)堆來(lái)選擇最大（或最小）的元素，并將其放置在數(shù)組的末尾，然后對(duì)剩余的元素進(jìn)行遞歸調(diào)用堆排序。

堆排序在其初期的版本中存在一些性能問(wèn)題，例如在構(gòu)建堆的過(guò)程中需要頻繁的調(diào)整堆的結(jié)構(gòu)，導(dǎo)致性能的下降。為了改進(jìn)這個(gè)問(wèn)題，人們提出了一種稱為“堆調(diào)整”的操作，將調(diào)整堆的過(guò)程優(yōu)化為一次遍歷，從而提高了性能。此外，還有一些其他的改進(jìn)方法，如使用二叉堆來(lái)代替普通堆，使用自底向上的構(gòu)建堆的方法等。

堆排序作為一種經(jīng)典的排序算法，經(jīng)過(guò)多年的發(fā)展與改進(jìn)，已經(jīng)成為一種高效穩(wěn)定的排序算法，并在實(shí)際應(yīng)用中得到廣泛的應(yīng)用。

---

二、思路解讀

我們知道堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法，所以堆排序分為以下幾步：

①：構(gòu)建大堆（或小堆）。這里我們從數(shù)組的最后一個(gè)數(shù)據(jù)的父節(jié)點(diǎn)開(kāi)始，采用向下調(diào)整算法來(lái)建堆。
向下調(diào)整算法有一個(gè)前提：左右子樹(shù)必須是一個(gè)堆，才能調(diào)整。同時(shí)還要注意是調(diào)大堆還是小堆。
調(diào)小(大)堆：堆頂元素和孩子中最小（大）的節(jié)點(diǎn)比較，如果父節(jié)點(diǎn)大于（小于）較小的子節(jié)點(diǎn)子，兩者交換。不斷向下調(diào)整到合適位置。（調(diào)大堆，和較大孩子比較）

②：將堆中最大（或最小）的元素即堆頂元素與數(shù)組中最后一個(gè)元素交換位置，然后將堆的大小減1。將交換后的堆頂元素進(jìn)行向下調(diào)整，直到堆再次滿足堆性質(zhì)。

③： 重復(fù)上述步驟，直到堆的大小為1，此時(shí)整個(gè)數(shù)組就有序了

---

三、代碼實(shí)現(xiàn)（大堆為例）

void AdjustDown(int* a, int n, int parent)
{//建大堆int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//升序，建大堆for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

時(shí)間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(1)