堆排序代码详解

 堆的图示

• 堆是一个完全二叉树；

• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的 值。

 左侧为大顶堆       右侧为小顶堆

 下列代码建立的是大顶堆

	#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;
	}