堆排序（Heap Sort）堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大（或最小）的記錄.
堆排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近於最壞性能。
由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
堆排序是就地排序，輔助空間為O(1），
它是不穩定的排序方法。
如果需求是從很大的數據中選取特定的幾個最大活最小值，那麼堆排序是最好的選擇。
堆排序的基本步驟就是：
1.初始建堆
2.將堆頂元素與有序區的第一個元素交換
3.然後對堆頂元素開始調整堆，跳轉到2執行。直到全部有序。
聲明：下面算法的實現中，數組的存儲位於data[1]-------data[n]
該算法中最核心的算法是堆的調整算法：
[cpp]
//堆調整
//data[],要排序的數組
//target,要調整的元素位置
//n,數組大小
void AdjustHeap(int data[],int target,int n)
{
int nChild;
int nTemp;
nTemp = data[target];//暫存
while(target * 2 <= n)
{
nChild = target * 2;//nChild指向左孩子
if(nChild + 1 <= n && data[nChild] < data[nChild + 1])
{
nChild++;//nChild指向關鍵字大的孩子（看是否有左孩子，若有，則左右孩子比較）
}
if(nTemp < data[nChild])//孩子節點比父節點大，則進行孩子節點移到父節點的位置
{
data[target] = data[nChild];
target = nChild;//再處理剛剛調整過的節點的字節點
}
else break;
}
data[target] = nTemp;//最後將要調整的元素放到合適的位置
}
//堆調整
//data[],要排序的數組
//target,要調整的元素位置
//n,數組大小
void AdjustHeap(int data[],int target,int n)
{
int nChild;
int nTemp;
nTemp = data[target];//暫存
while(target * 2 <= n)
{
nChild = target * 2;//nChild指向左孩子
if(nChild + 1 <= n && data[nChild] < data[nChild + 1])
{
nChild++;//nChild指向關鍵字大的孩子（看是否有左孩子，若有，則左右孩子比較）
}
if(nTemp < data[nChild])//孩子節點比父節點大，則進行孩子節點移到父節點的位置
{
data[target] = data[nChild];
target = nChild;//再處理剛剛調整過的節點的字節點
}
else break;
}
data[target] = nTemp;//最後將要調整的元素放到合適的位置
}
整體實現代碼：
[cpp]
****************
* 堆排序算法
* 排序數組下標從1開始
*/
#include <stdio.h>
enum{MAX = 1000+1,};
int data[MAX];
static inline swap(int x,int y)
{/*
x ^= y;
y ^= x;
x ^= y;
*/
int tmp;
tmp = data[x];
data[x] = data[y];
data[y] = tmp;
}
//堆調整
//data[],要排序的數組
//target,要調整的元素位置
//n,數組大小
void AdjustHeap(int data[],int target,int n)
{
int nChild;
int nTemp;
nTemp = data[target];//暫存
while(target * 2 <= n)
{
nChild = target * 2;
if(nChild + 1 <= n && data[nChild] < data[nChild + 1])
{
nChild++;//nChild指向關鍵字大的孩子
}
if(nTemp < data[nChild])
{
data[target] = data[nChild];
target = nChild;//再處理剛剛調整過的節點的字節點
}
else break;
}
data[target] = nTemp;//最後將要調整的元素放到合適的位置
}
//堆排序算法
//data，要排序的數組
//n，數組大小
void HeapSort(int data[],int n)
{
int i;
//初始建堆
for(i = n/2;i > 0;--i)
{
AdjustHeap(data,i,n);
}
//每次循環將堆頂元素與有序區第一個元素交換，然後再調整堆
for(i = n;i > 1;--i)
{
swap(1,i);
AdjustHeap(data,1,i - 1);
}
}
int main()
{
freopen("random","r",stdin);
freopen("oder","w",stdout);
int i;
for(i = 1;i <= MAX;++i)
{
scanf("%d",&data[i]);
}
//stderr("開始排序\n");
HeapSort(data,MAX);
//stderr("排序結束\n");
for(i = 1;i <= MAX;++i)
{
printf("%d\n",data[i]);
}
return 0;
}
/****************
* 堆排序算法
* 排序數組下標從1開始
*/
#include <stdio.h>
enum{MAX = 1000+1,};
int data[MAX];
static inline swap(int x,int y)
{/*
x ^= y;
y ^= x;
x ^= y;
*/
int tmp;
tmp = data[x];
data[x] = data[y];
data[y] = tmp;
}
//堆調整
//data[],要排序的數組
//target,要調整的元素位置
//n,數組大小
void AdjustHeap(int data[],int target,int n)
{
int nChild;
int nTemp;
nTemp = data[target];//暫存
while(target * 2 <= n)
{
nChild = target * 2;
if(nChild + 1 <= n && data[nChild] < data[nChild + 1])
{
nChild++;//nChild指向關鍵字大的孩子
}
if(nTemp < data[nChild])
{
data[target] = data[nChild];
target = nChild;//再處理剛剛調整過的節點的字節點
}
else break;
}
data[target] = nTemp;//最後將要調整的元素放到合適的位置
}
//堆排序算法
//data，要排序的數組
//n，數組大小
void HeapSort(int data[],int n)
{
int i;
//初始建堆
for(i = n/2;i > 0;--i)
{
AdjustHeap(data,i,n);
}
//每次循環將堆頂元素與有序區第一個元素交換，然後再調整堆
for(i = n;i > 1;--i)
{
swap(1,i);
AdjustHeap(data,1,i - 1);
}
}
int main()
{
freopen("random","r",stdin);
freopen("oder","w",stdout);
int i;
for(i = 1;i <= MAX;++i)
{
scanf("%d",&data[i]);
}
//stderr("開始排序\n");
HeapSort(data,MAX);
//stderr("排序結束\n");
for(i = 1;i <= MAX;++i)
{
printf("%d\n",data[i]);
}
return 0;
}
