內(nèi)部排序之堆排序的實(shí)現(xiàn)
堆排序（Heap Sort）只需要一個(gè)記錄大小的輔助空間，每個(gè)待排序的記錄僅占有一個(gè)存儲(chǔ)空間。下面小編為大家整理了內(nèi)部排序之堆排序的實(shí)現(xiàn)，希望能幫到大家！
�。�1）基本概念
a）堆：設(shè)有n個(gè)元素的序列：
{k1, k2, ..., kn}
對(duì)所有的i=1,2,...,(int)(n/2)，當(dāng)滿(mǎn)足下面關(guān)系：
ki≤k2i，ki≤k2i+1
或 ki≥k2i，ki≥k2i+1
這樣的序列稱(chēng)為堆。
堆的兩種類(lèi)型：
根結(jié)點(diǎn)最小的堆----小根堆。
根結(jié)點(diǎn)最大的堆----大根堆。
根結(jié)點(diǎn)稱(chēng)為堆頂，即：在一棵完全二叉樹(shù)中，所有非葉結(jié)點(diǎn)的值均小于（或均大于）左、右孩子的值。
b）堆排序：是一種樹(shù)型選擇排序，特點(diǎn)是，在排序過(guò)程中，把R[1..n]看成是一個(gè)完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)的內(nèi)在關(guān)系，在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大（最小）的記錄。
�。�2）堆排序步驟：
1、從k-1層的最右非葉結(jié)點(diǎn)開(kāi)始，使關(guān)鍵字值大（或�。┑挠涗浿鸩较蚨鏄�(shù)的上層移動(dòng)，最大（或小）關(guān)鍵字記錄成為樹(shù)的根結(jié)點(diǎn)，使其成為堆。
2、逐步輸出根結(jié)點(diǎn)，令r[1]=r[i](i=n,,n-1,...,2)，在將剩余結(jié)點(diǎn)調(diào)整成堆。直到輸出所有結(jié)點(diǎn)。我們稱(chēng)這個(gè)自堆頂?shù)饺~子的調(diào)整過(guò)程為“篩選”。
�。�3）要解決的兩個(gè)問(wèn)題：
１、如何由一個(gè)無(wú)序序列建成一個(gè)堆；
�。�、輸出一個(gè)根結(jié)點(diǎn)后，如何將剩余元素調(diào)整成一個(gè)堆。
將一個(gè)無(wú)序序列建成一個(gè)堆是一個(gè)反復(fù)“篩選”的過(guò)程。若將此序列看成是一個(gè)完全二叉樹(shù)，則最后一個(gè)非終端結(jié)點(diǎn)是第floor(n/2)個(gè)元素，由此“篩選”只需從第floor(n/2)個(gè)元素開(kāi)始。
堆排序中需一個(gè)記錄大小的輔助空間，每個(gè)待排的記錄僅占有一個(gè)存儲(chǔ)空間。堆排序方法當(dāng)記錄較少時(shí)，不值得提倡。當(dāng)n很大時(shí)，效率很高。堆排序是不穩(wěn)定的。
堆排序的算法和篩選的算法如第二節(jié)所示。為使排序結(jié)果是非遞減有序排列，我們?cè)谂判蛩惴ㄖ邢冉ㄒ粋�(gè)“大頂堆”，即先選得一個(gè)關(guān)鍵字為最大的記錄并與序列中最后一個(gè)記錄交換，然后對(duì)序列中前n-1個(gè)記錄進(jìn)行篩選，重新將它調(diào)整為一個(gè)“大頂堆”，然后將選得的一個(gè)關(guān)鍵字為最大的記錄（也就是第一個(gè)元素）與當(dāng)前最后一個(gè)記錄交換（全局看是第n-1個(gè)），如此往復(fù)，直到排序結(jié)束。由到，篩選應(yīng)按關(guān)鍵字較大的孩子結(jié)點(diǎn)向下進(jìn)行。
堆排序的算法描述如下：
用C語(yǔ)言代碼實(shí)現(xiàn)如下：
復(fù)制代碼 代碼如下:
#include "iostream"
using namespace std;
#define MAXSIZE 20
typedef struct
{
int key;
/pic/p>
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}Sqlist;
typedef Sqlist HeapType; /pic/p>
void HeapAdjust(HeapType &H,int s,int m) /pic/p>
{
int j;
RedType rc;
rc=H.r[s];
for(j=2*s;j<=m;j*=2) /pic/p>
{
if(j<m && (H.r[j].key<H.r[j+1].key)) /pic/p>
++j;
if(rc.key>=H.r[j].key) /pic/p>
break;
H.r[s]=H.r[j]; /pic/p>
s=j;
}
H.r[s]=rc; /pic/p>
}
void HeapSort(HeapType &H) /pic/p>
{
int i;
for(i=H.length/2;i>0;--i) /pic/2個(gè)元素
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{
H.r[0]=H.r[1]; /pic/p>
H.r[1]=H.r[i];
H.r[i]=H.r[0];
HeapAdjust(H,1,i-1); /pic/p>
}
}/pic/p>
void InputL(Sqlist &L)
{
int i;
printf("Please input the length:");
scanf("%d",&L.length);
printf("Please input the data needed to sort:n");
for(i=1;i<=L.length;i++) /pic/p>
scanf("%d",&L.r[i].key);
}
void OutputL(Sqlist &L)
{
int i;
printf("The data after sorting is:n");
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("n");
}
int main(void)
{
Sqlist H;
InputL(H);
HeapSort(H);
OutputL(H);
system("pause");
return 0;
}
不使用上面的結(jié)構(gòu)體的另外一種方法如下：
復(fù)制代碼 代碼如下:
/*
*堆排序
*/
#include "iostream"
using namespace std;
#define N 10
int array[N];
void man_input(int *array)
{
int i;
for(i=1;i<=N;i++)
{
printf("array[%d]=",i);
scanf("%d",&array[i]);
}
}
void mySwap(int *a,int *b)/pic/p>
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void heap_adjust(int *heap,int root,int len) /pic/p>
{
int i=2*root;
int t=heap[root];
while(i<=len)
{
if(i<len)
{
if(heap[i]<heap[i+1])
i++;
}
if(t>=heap[i])
break;
heap[i/2]=heap[i];
i=2*i;
}
heap[i/2]=t;
}
void heapSort(int *heap,int len) /pic/p>
{
int i;
for(i=len/2;i>0;i--) /pic/2個(gè)元素
{
heap_adjust(heap,i,len);
}
for(i=len;i>=1;i--)
{
mySwap(heap+i,heap+1); /pic/p>
heap_adjust(heap,1,i-1); /pic/p>
}
}
void print_array(int *array,int n)
{
int k;
for(k=1;k<n+1;k++)
{
printf("%dt",array[k]);
}
}
int main(void)
{
man_input(array);
heapSort(array,N);
printf("nAfter sorted by the heap_sort algorithm:n");
print_array(array,N); /pic/p>
system("pause");
return 0;
}
【內(nèi)部排序之堆排序的實(shí)現(xiàn)】相關(guān)文章：
C#排序算法之堆排序11-16
堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆02-12
java堆排序的算法思想的分析11-29
如何實(shí)現(xiàn)歸并排序03-14
分析php選擇排序法實(shí)現(xiàn)數(shù)組排序的方法12-13
希爾排序（C語(yǔ)言實(shí)現(xiàn)）01-26
冒泡排序（C語(yǔ)言實(shí)現(xiàn)）12-01
C#排序算法之快速排序01-07