內(nèi)部排序之堆排序的實現(xiàn)詳解

更新時間：2013年05月24日 14:56:36 作者：

本篇文章是對堆排序的實現(xiàn)進行了詳細的分析介紹，需要的朋友參考下

堆排序（Heap Sort）只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。
（1）基本概念
a）堆：設有n個元素的序列：
{k1, k2, ..., kn}
對所有的i=1,2,...,(int)(n/2)，當滿足下面關系：
                                                                  ki≤k2i，ki≤k2i+1
                                                  或            ki≥k2i，ki≥k2i+1
這樣的序列稱為堆。
堆的兩種類型：
   根結點最小的堆----小根堆。
   根結點最大的堆----大根堆。
根結點稱為堆頂，即：在一棵完全二叉樹中，所有非葉結點的值均小于（或均大于）左、右孩子的值。
b）堆排序：是一種樹型選擇排序，特點是，在排序過程中，把R[1..n]看成是一個完全二叉樹的存儲結構，利用完全二叉樹雙親結點和孩子結點的內(nèi)在關系，在當前無序區(qū)中選擇關鍵字最大（最?。┑挠涗?。
2）堆排序步驟：
1、從k-1層的最右非葉結點開始，使關鍵字值大（或?。┑挠涗浿鸩较蚨鏄涞纳蠈右苿樱畲螅ɑ蛐。╆P鍵字記錄成為樹的根結點，使其成為堆。
2、逐步輸出根結點，令r[1]=r[i](i=n,,n-1,...,2)，在將剩余結點調(diào)整成堆。直到輸出所有結點。我們稱這個自堆頂?shù)饺~子的調(diào)整過程為“篩選”。
（3）要解決的兩個問題：
１、如何由一個無序序列建成一個堆；
２、輸出一個根結點后，如何將剩余元素調(diào)整成一個堆。
將一個無序序列建成一個堆是一個反復“篩選”的過程。若將此序列看成是一個完全二叉樹，則最后一個非終端結點是第floor(n/2)個元素，由此“篩選”只需從第floor(n/2)個元素開始。
堆排序中需一個記錄大小的輔助空間，每個待排的記錄僅占有一個存儲空間。堆排序方法當記錄較少時，不值得提倡。當n很大時，效率很高。堆排序是不穩(wěn)定的。
堆排序的算法和篩選的算法如第二節(jié)所示。為使排序結果是非遞減有序排列，我們在排序算法中先建一個“大頂堆”，即先選得一個關鍵字為最大的記錄并與序列中最后一個記錄交換，然后對序列中前n-1個記錄進行篩選，重新將它調(diào)整為一個“大頂堆”，然后將選得的一個關鍵字為最大的記錄（也就是第一個元素）與當前最后一個記錄交換（全局看是第n-1個），如此往復，直到排序結束。由到，篩選應按關鍵字較大的孩子結點向下進行。
堆排序的算法描述如下：

用C語言代碼實現(xiàn)如下：

復制代碼代碼如下:

#include "iostream"
using namespace std;
#define MAXSIZE 20
typedef struct
{
 int key;
 //其他數(shù)據(jù)信息
}RedType;
typedef struct
{
 RedType r[MAXSIZE+1];
 int length;
}Sqlist;
typedef Sqlist HeapType;  //堆采用順序表存儲表示
void HeapAdjust(HeapType &H,int s,int m)   //已知H.r[s...m]中記錄的關鍵字出H.r[s].key之外均滿足堆的定義，本函數(shù)調(diào)整H.r[s]的關鍵字，使H.r[s...m]成為一個大頂堆（對其中記錄的關鍵字而言）
{
 int j;
 RedType rc;
 rc=H.r[s];
 for(j=2*s;j<=m;j*=2)   //沿key較大的孩子結點向下篩選
 {
  if(j<m && (H.r[j].key<H.r[j+1].key))     //j為key較大的記錄的下標
   ++j;
  if(rc.key>=H.r[j].key)           //rc應插入在位置s上
   break;
  H.r[s]=H.r[j];      //將左、右孩子較大的結點與父節(jié)點進行交換，建成大頂堆
  s=j;
 }
 H.r[s]=rc;             //插入
}
void HeapSort(HeapType &H)      //對順序表H進行堆排序
{
 int i;
 for(i=H.length/2;i>0;--i)   //由一個無序序列建成一個大頂堆，將序列看成是一個完全二叉樹，則最后一個非終端節(jié)點是第n/2個元素
  HeapAdjust(H,i,H.length);
 for(i=H.length;i>1;--i)
 {
  H.r[0]=H.r[1];   //將堆頂記錄和當前未經(jīng)排序的子序列H.r[1...i]中最后一個記錄相互交換
  H.r[1]=H.r[i];
  H.r[i]=H.r[0];
  HeapAdjust(H,1,i-1);    //將H.r[1...i-1]重新調(diào)整為大頂堆
 }
}//HeapSort
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++)    //從數(shù)組的第1個下標開始存儲，第0個下標作為一個用于交換的臨時變量
  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;
}

不使用上面的結構體的另外一種方法如下：

復制代碼代碼如下:

/*
*堆排序
*/
#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)//交換
{
 int temp;
 temp=*a;
 *a=*b;
 *b=temp;
}
void heap_adjust(int *heap,int root,int len)     //對堆進行調(diào)整，使下標從root到len的無序序列成為一個大頂堆
{
 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)      //堆排序
{
 int i;
 for(i=len/2;i>0;i--)    //由一個無序序列建成一個大頂堆，將序列看成是一個完全二叉樹，則最后一個非終端節(jié)點是第len/2個元素
 {
  heap_adjust(heap,i,len);
 }
 for(i=len;i>=1;i--)
 {
  mySwap(heap+i,heap+1);    //將堆頂記錄與最后一個記錄相互交換
  heap_adjust(heap,1,i-1);   //將下標為1~i-1的記錄重新調(diào)整為大頂堆
 }
}
void print_array(int *array,int n)
{
 int k;
 for(k=1;k<n+1;k++)
 {
  printf("%d\t",array[k]);
 }
}
int main(void)
{
 man_input(array);
 heapSort(array,N);
 printf("\nAfter sorted by the heap_sort algorithm:\n");        
 print_array(array,N);   //打印堆排序結果
 system("pause");
 return 0;
}