/*利用完全二叉树的性质，一个线性数组可以看做是完全二叉树的层次遍历每次循环把二叉树按照双亲大于左右孩子的规则调换位置，这样一轮下来，根结点就是最大的那个数把根结点和最后一个元素交换位置下一次循环继续调换位置，除了最后一个元素再一次循环继续调换位置，除了最后一个和倒数第二个元素依次类推。。。*/#include<stdio.h>#include <string.h>typedef struct {    int length;    int r[20]; }*SqList,List;void HeapAdjust(SqList L,int s,int m){    int temp,j;    temp = L->r[s];    for(j=2*s; j<=m; j*=2){        if(j<m &&  L->r[j] < L->r[j+1]){            /*左孩子和右孩子比较，选出大的数*/            ++j;        }        if(temp >= L->r[j]){            /*如果双亲大于刚才选出的比较大的数，就直接跳出*/            break;        }        /*否则的话，就交换位置，保证双亲结点是3个数中最大的数*/        L->r[s] = L->r[j];//把左右孩子中较大的值赋值给双亲，交换位置步骤1        s = j;    }    L->r[s] = temp;//把双亲的值赋值给孩子，交换位置步骤2}void swap(SqList L,int a, int j){    int temp;    temp = L->r[a];    L->r[a] = L->r[j];    L->r[j] = temp;}void heapSort(SqList L){    int i;        /*第1次循环先构建一个大顶堆*/    for(i=L->length/2; i>0; i--){        HeapAdjust(L,i,L->length);    }        /*每次HeapAdjust后，根结点就是最大的那个数，就把根结点和最后一个结点交换位置*/    for(i = L->length; i>1; i--){        swap(L,1,i);        HeapAdjust(L,1,i-1);//然后重新构建1到i-1的大顶堆，直到排序结束    }}void print(SqList list){    int i;    for(i=1;i<list->length;i++){        printf(" %d ",list->r[i]);    }}void main(){    SqList list = (SqList)malloc(sizeof(List));    list->length = 9;    list->r[0] = 0; //因为模拟一个树结构,第一个元素下标为1，所以0号位置用一个数占一个位置，但不用这个数，只是用它充数    list->r[1] = 50;    list->r[2] = 10;    list->r[3] = 90;    list->r[4] = 30;    list->r[5] = 70;    list->r[6] = 40;    list->r[7] = 80;    list->r[8] = 60;    list->r[9] = 20;    heapSort(list);    print(list);}