堆排序代码详解

  #include "stdio.h"
  # define MAXSIZE 10
  typedef struct {
      int r[MAXSIZE];             /* 用 于 存 储 要 排 序 数 组  */
      int length ;                /* 用 于 记 录 顺 序 表 的 长 度 */
  }SqList ;
  void swap ( SqList *L, int i, int j){           /* 交 换 L 中 数 组 r 的 下 标 为 i 和 j 的 值 */
      int temp = L->r[i];
      L->r[i] = L->r[j];
      L->r[j] = temp;
  }
  void HeapAdjust(SqList* L,int s,int m){         /* 结构体L的位置，第一个判断的结点的位置s，结点的个数m */
       int temp , j;
       temp = L->r[s];                            /* 传递给temp位置s上的值 */
       for (j = 2*s;j <= m;j *= 2) {              /* 比较位置s上和它的两个子孩子上的值 */
           if (j < m && L->r[j] < L->r[j+1])      /* 先找到s的两个子孩子，找出子孩子中较大的值 */
              ++j;                                /* j表示较大子孩子的下表 */
           if ( temp >= L->r[j])                  /* 如果temp大 则 当前结构不变 */
               break ;                            /* r[c] 应 插 入 在 位 置 s 上 */
           L->r[s] = L->r[j];                     /* 否则把最大值赋到s位置上 */
           s = j;                                 /* 为  L->r[s] = temp 做铺垫 */
       }
       L->r[s] = temp;                            /* 最后一步 */
  }
  void HeapSort(SqList* L){                        /* 对顺序表L进行堆排序 */
      int i;
      for (i = L->length/2; i > 0; i--)            /* 把 L 中 的 r 构 建 成 一 个 大 顶 堆 */
          HeapAdjust (L,i,L->length) ;             /* 传入结构体L的位置  第一个判断的结点的位置i  结点的个数length */
      for(i=0;i<MAXSIZE;i++){                      /* 查看堆化后的结果 */
          printf("%d  ",L->r[i]);
      }
      printf("\n");
      for (i = L->length; i > 1; i--) {
          swap (L, 1 , i) ;                      /* 把堆顶最大值放在数组最后面，i-1 后就不参与堆化过程了 */
          HeapAdjust (L, 1 , i-1);           /* 结构体L的位置，第一个结点的位置s，结点的个数m */
          for(int j=0;j<MAXSIZE;j++){              /* 查看过程 */
              printf("%d--",L->r[j]);
          }
          printf("\n");
      }
  }
  int main(){
      int i;
      int a[9]={50,10,90,30,70,40,80,60,20};        /* 初始化 */
      SqList L;
      L.length=MAXSIZE-1;                           /*  关键: r[0]是不用的 而且 有效长度需要在基础上减    1   */
      L.r[0]=9999999;
      for(i=1;i<MAXSIZE;i++){
          L.r[i]=a[i-1];                            /* r[0]是不用的 */
      }
      for(i=0;i<MAXSIZE;i++){
          printf("%d  ",L.r[i]);             /*  查看原本的排序  */
      }
      printf("\n");
      HeapSort(&L);                                  /* 进行堆化 */
      for(i=0;i<MAXSIZE;i++){                        /* 查看排序后结果 */
          printf("%d  ",L.r[i]);
      }
      return 0;
  }