内部排序之堆排序的实现详解

#include "iostream"
using namespace std;
#define MAXSIZE 20
typedef struct
{
 int key;
 //其他数据信息
}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之外均满足堆的定义，本函数调整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];      //将左、右孩子较大的结点与父节点进行交换，建成大顶堆
  s=j;
 }
 H.r[s]=rc;             //插入
}
void HeapSort(HeapType &H)      //对顺序表H进行堆排序
{
 int i;
 for(i=H.length/2;i>0;--i)   //由一个无序序列建成一个大顶堆，将序列看成是一个完全二叉树，则最后一个非终端节点是第n/2个元素
  HeapAdjust(H,i,H.length);
 for(i=H.length;i>1;--i)
 {
  H.r[0]=H.r[1];   //将堆顶记录和当前未经排序的子序列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]重新调整为大顶堆
 }
}//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++)    //从数组的第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)     //对堆进行调整，使下标从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--)    //由一个无序序列建成一个大顶堆，将序列看成是一个完全二叉树，则最后一个非终端节点是第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的记录重新调整为大顶堆
 }
}
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;
}