堆排序

基本思想

步骤

By C++

  1. #include <stdio.h>
  2. #define MaxSize 100
  4. typedef int KeyType;        /*关键字类型*/
  6. typedef char ElemType[10];    /*其他数据项类型*/
  8. typedef struct 
  9. {    
  10.     KeyType key;               /*关键字域*/
  11.     ElemType data;             /*其他数据域*/
  12. } LineList;                    /*线性表元素类型*/
  14. void Sift(LineList R[],int low,int high)
  15. {
  16.     int i=low,j=2*i;             /*R[j]是R[i]的左孩子*/
  17.     LineList tmp=R[i];
  18.     while (j<=high) 
  19.     {    if (j<high && R[j].key<R[j+1].key)     /*若右孩子较大,把j指向右孩子*/
  20.             j++;                    /*j变为2i+1,指向右孩子结点*/
  21.         if (tmp.key<R[j].key) 
  22.         {    R[i]=R[j];           /*将R[j]调整到双亲结点位置上*/
  23.             i=j;                  /*修改i和j值,以便继续向下筛选*/
  24.             j=2*i;
  25.         }
  26.         else break;              /*筛选结束*/
  27.     }
  28.     R[i]=tmp;                     /*被筛选结点的值放入最终位置*/
  29. }
  31. void HeapSort(LineList R[],int n)
  32. {
  33.     int i;
  34.     LineList tmp;
  35.     for (i=n/2;i>=1;i--)      /*循环建立初始堆*/
  36.         Sift(R,i,n); 
  37.     for (i=n;i>=2;i--)       /*进行n-1次循环,完成堆排序*/
  38.     {      tmp=R[1];            /*将第一个元素同当前区间内R[1]对换*/
  39.         R[1]=R[i];
  40.         R[i]=tmp;
  41.         Sift(R,1,i-1);         /*筛选R[1]结点,得到i-1个结点的堆*/
  42.     }
  43. }
  45. void main()
  46. {
  47.     LineList R[MaxSize];
  48.     KeyType a[]={0,75,87,68,92,88,61,77,96,80,72};    /*有效数据从a[1]开始*/
  49.     int n=10,i;
  50.     for (i=0;i<=n;i++)
  51.         R[i].key=a[i];
  52.     printf("排序前:");
  53.     for (i=1;i<=n;i++)
  54.         printf("%3d",R[i].key);
  55.     printf("\n");
  56.     HeapSort(R,n);
  57.     printf("排序后:");
  58.     for (i=1;i<=n;i++)
  59.         printf("%3d",R[i].key);
  60.     printf("\n");
  61. }

By Golang

go