排序算法5---堆排序算法，改进的简单选择排序

简单选择排序没有把每一趟的比较结果保存下来，堆排序做到了在每次选择到最小记录的同时，根据比较结果对其他的记录做出相应的调整。

#include <stdio.h>

#define MAXSIZE 9  /* 用于要排序数组中元素个数最大值，可根据需要修改 */
typedef struct
{
    int r[MAXSIZE+1];        /* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
    int length;            /* 用于记录顺序表的长度 */
}SqList;

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j) 
{ 
    int temp=L->r[i]; 
    L->r[i]=L->r[j]; 
    L->r[j]=temp; 
}

void print(SqList L)
{
    int i;
    for(i=1;i<=L.length;i++)
        printf("%3d,",L.r[i]);
    printf("
");
}

/* 堆排序********************************** */

/* 注：已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义， */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList * L, int s, int m){
    int j,temp;
    temp=L->r[s];
    for(j=2*s; j<=m; j*=2){
        //j<m 防止下标越界
        if(j<m && L->r[j]<L->r[j+1]){//注意：两次比较，一次交换
            j=j+1;
        }
        if(temp > L->r[j]){
            break;
        }
        L->r[s]=L->r[j];
        s=j;
    }
    L->r[s]=temp;
}

/* 对顺序表L作堆排序 */
void heapsort(SqList * L){
    int i,j;
    //构建大根堆
    for(i=L->length/2; i>0; i--){
        HeapAdjust(L, i, L->length);
    }

    //将大根堆的第一个元素交换至堆的最后一个元素,重新调整新的堆
    for(j=L->length; j>1; j--){
    swap(L, j, 1);//交换后，在L->[1]到L->[j-1]中，除了第一个元素关键字L->[1]外，均满足堆的定义
    HeapAdjust(L, 1, j-1);
    }
    print(*L);
}

int main(){
    SqList L;
    int num[10] = {9,5,3,2,4,6,1,7,8,9};    
    for(int i=0; i<10; i++){
        L.r[i]=num[i];
    }//注意给数组赋值的方法
    L.length=9;
    //堆排序
    heapsort(&L);
    return 0;
}

完全二叉树的某个结点到根结点的距离为；向下取整 [logi]+1。

　　堆排序的过程

建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。
调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。
堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)。参考：大话数据结构