簡介
堆排序（英語：Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
堆的操作
在堆的數據結構中，堆中的最大值總是位于根節點（在優先隊列中使用堆的話堆中的最小值位于根節點）。堆中定義以下幾種操作：
最大堆調整（Max Heapify）：将堆的末端子節點作調整，使得子節點永遠小于父節點
創建最大堆（Build Max Heap）：将堆中的所有數據重新排序
堆排序（HeapSort）：移除位在第一個數據的根節點，并做最大堆調整的遞歸運算。
實現示例
C語言
#include
#include
void swap(int* a， int* b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[]， int start， int end)
{
//建立父節點指标和子節點指标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子節點指标在範圍内才做比較
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else //否則交換父子内容再繼續子節點和孫節點比較
{
swap(&arr[dad]， &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[]， int len)
{
int i;
//初始化，i從最後一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr， i， len - 1);
//先将第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
for (i = len - 1; i > 0; i--)
{
swap(&arr[0]， &arr[i]);
max_heapify(arr， 0， i - 1);
}
}
int main() {
int arr[] = { 3， 5， 3， 0， 8， 6， 1， 5， 8， 6， 2， 4， 9， 4， 7， 0， 1， 8， 9， 7， 3， 1， 2， 5， 9， 7， 4， 0， 2， 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr， len);
int i;
for (i = 0; i < len; i++)
printf("%d "， arr[i]);
printf("n");
return 0;
}
C++
#include
#include
using namespace std;
void max_heapify(int arr[]， int start， int end)
{
//建立父節點指标和子節點指标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子節點指标在範圍内才做比較
{
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else //否則交換父子内容再繼續子節點和孫節點比較
{
swap(arr[dad]， arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[]， int len)
{
//初始化，i從最後一個父節點開始調整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr， i， len - 1);
//先将第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完畢
for (int i = len - 1; i > 0; i--)
{
swap(arr[0]， arr[i]);
max_heapify(arr， 0， i - 1);
}
}
void main()
{
int arr[] = { 3， 5， 3， 0， 8， 6， 1， 5， 8， 6， 2， 4， 9， 4， 7， 0， 1， 8， 9， 7， 3， 1， 2， 5， 9， 7， 4， 0， 2， 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr， len);
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
system("pause");
}
Java語言
/**
* 選擇排序-堆排序
* @param array 待排序數組
* @return 已排序數組
*/
public static int[] heapSort(int[] array) {
//這裡元素的索引是從0開始的，所以最後一個非葉子結點array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array， i， array.length); //調整堆
}
// 上述邏輯，建堆結束
// 下面，開始排序邏輯
for (int j = array.length - 1; j > 0; j--) {
// 元素交換，作用是去掉大頂堆
// 把大頂堆的根元素，放到數組的最後；換句話說，就是每一次的堆調整之後，都會有一個元素到達自己的最終位置
swap(array， 0， j);
// 元素交換之後，毫無疑問，最後一個元素無需再考慮排序問題了。
// 接下來我們需要排序的，就是已經去掉了部分元素的堆了，這也是為什麼此方法放在循環裡的原因
// 而這裡，實質上是自上而下，自左向右進行調整的
adjustHeap(array， 0， j);
}
return array;
}
/**
* 整個堆排序最關鍵的地方
* @param array 待組堆
* @param i 起始結點
* @param length 堆的長度
*/
public static void adjustHeap(int[] array， int i， int length) {
// 先把當前元素取出來，因為當前元素可能要一直移動
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1為左子樹i的左子樹(因為i是從0開始的)，2*k+1為k的左子樹
// 讓k先指向子節點中最大的節點
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子樹，并且右子樹大于左子樹
k++;
}
//如果發現結點(左右子結點)大于根結點，則進行值的交換
if (array[k] > temp) {
swap(array， i， k);
// 如果子節點更換了，那麼，以子節點為根的子樹會受到影響，所以，循環對子節點所在的樹繼續進行判斷
i = k;
} else { //不用交換，直接終止循環
break;
}
}
}
/**
* 交換元素
* @param arr
* @param a 元素的下标
* @param b 元素的下标
*/
public static void swap(int[] arr， int a， int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
Python語言
def big_endian(arr，start，end):
root=start
child=root*2+1 #左孩子
while child<=end:
#孩子比最後一個節點還大，也就意味着最後一個葉子節點了，就得跳出去一次循環，已經調整完畢
if child+1<=end and arr[child]
#為了始終讓其跟子元素的較大值比較，如果右邊大就左換右，左邊大的話就默認
child+=1
if arr[root]
#父節點小于子節點直接交換位置，同時坐标也得換，這樣下次循環可以準确判斷：是否為最底層，
#是不是調整完畢
arr[root]，arr[child]=arr[child]，arr[root]
root=child
child=root*2+1
else:
break
def heap_sort(arr): #無序區大根堆排序
first=len(arr)//2 - 1
for start in range(first，-1，-1):
#從下到上，從左到右對每個節點進行調整，循環得到非葉子節點
big_endian(arr，start，len(arr)-1) #去調整所有的節點
for end in range(len(arr)-1，0，-1):
arr[0]，arr[end]=arr[end]，arr[0] #頂部尾部互換位置
big_endian(arr，0，end-1) #重新調整子節點的順序，從頂開始調整
return arr
def main():
l=[3，1，4，9，6，7，5，8，2，10]
print(heap_sort(l))
if __name__=="__main__":
main()
PHP語言
function hsort(array &$arr， $len){
$idx = $len - 1;
//創建堆操作，并使得堆有序
for($k=floor($len/2); $k>=0; $k--){
sink($arr， $k， $idx);
}
//排序操作
while($idx>0){
//獲取最大值操作
list($arr[0]， $arr[$idx]) = [$arr[$idx]， $arr[0]];
$idx--;
//堆調整下沉
sink($arr， 0， $idx);
}
}
//堆調整下沉，小數字下沉
function sink(array &$arr， $low， $high){
//從$low開始找子節點
while($low*2+1<=$high){
//獲取low的直接左子節點
$j = $low*2+1;
//判斷$low位置節點子節點中的較大子節點
if($j<$high && $arr[$j]<$arr[$j+1]){
$j++;
}
if($arr[$low]>$arr[$j]){
break;
}
//交換low節點和子節點的值
list($arr[$low]， $arr[$j]) = [$arr[$j]， $arr[$low]];
//繼續排查下沉後子節點是否需要進行下沉操作
$low = $j;
}
}
$a = [4，3，6，7，5，1，9，0，2];
hsort($a， count($a));
print_r($a);
