簡單選擇排序中，沒一趟比較的結果沒有保存下來，在下一趟的比較過程中，有許多比較在前一趟已經做過了，因而比較的次數較多。如果可以在每次比較的同時，將比較結果保存下來，那樣排序的總體效率就會非常高了，堆排序就是一種改進。
堆是具有下列性質的完全二叉樹：每個節點的值都大於或等於左右孩子節點的值，稱為大頂堆；或者每個節點都小於或等於其左右孩子節點的值，稱為小頂堆。
堆排序思路：
1、初始化堆。將待排序的關鍵字存放到數組r[1...n]中，將r看成是一個完全二叉樹的順序表示，每個節點表示一個記錄，任意節點r[i]的左孩子是r[2i]，右孩子是r[2i+1]，雙親是r[i/2];
2、建初堆。對這棵二叉樹進行調整，使得各節點的關鍵字值滿足下列條件：r[i].key>=r[2i].key 且r[i].key>=r[2i+1].key；構造成一個大頂堆。
3、重建堆。整個序列的最大值就是堆頂的根節點，將它移走其實就是將其與堆數組的末尾元素交換，此時末尾元素就是最大值），然後將剩余的n-1個序列重新構造成一個大頂堆,這樣會得到n個元素的次小值。如此反復執行，便能得到一個有序序列了。
#include <stdio.h>
#include <stdlib.h>
void swap(int arr[] ,int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void HeapAdjust(int arr[], int s, int m)
{
int temp;
int j;
temp=arr[s];
for(j=2*s+1; j<m; j*=2)
{
if(j<m-1 && arr[j]<arr[j+1])
++j; /* j為關鍵字中較大的記錄的下表*/
if(temp>=arr[j])
break;
arr[s]=arr[j];
s=j;
}
arr[s]=temp;
}
void HeapSort(int arr[], int n)
{
int i;
for(i=n/2 - 1; i>0; i--) //構建大頂堆
HeapAdjust(arr,i,n);
for(i=n-1; i>0;i--)
{
swap(arr,0,i);
HeapAdjust(arr,0,i-1);
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前：\n");
print(arr, n);
HeapSort(arr,n);
printf("排序後：\n");
print(arr, n);
system("pause");
return 0;
}
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282235
