小白读懂堆排序 调整堆，新建堆

堆排序过程

1.首先建立大根堆，建堆的过程就是从数组的大小一半的位置开始，每一次都调用一次堆调整函数，进入堆调整函数之后，找到左孩子和右孩子，如果左右孩子有比当前节点更大值，则进行交换，交换完之后对交换的孩子节点做为当前节点继续进行堆调整，直到当前节点已经大于数组的一半，停止交换。

2.第二步就是进行堆排序 首先将一个无序的数组建立大根堆，然后将从数组的最后一个元素开始与第一个元素交换位置。交换完元素之后进行，对接剩下的无序的元素继续进行堆调整。最后得到的数组就是经过堆排序之后的数组。

/*注意：这个函数仅仅会在调整被交换的位置为大根堆。未交换的分支不会处理，
所以不能将一个非大根堆二叉树的根结点传递过来让这个函数将其处理为大根堆*/
void heap_ajust(int *a, int i, int size)  /*a为堆存储数组，size为堆的大小*/
{
    int lchild = 2*i;       //i的左孩子节点序号 
    int rchild = 2*i +1;     //i的右孩子节点序号 
    int max = i; /*存放三个顶点中最大的数的下标*/
	int temp;
    if(i <= size/2)          //假设i是叶节点就不用进行调整 
    {
        if(lchild<=size && a[lchild]>a[max])
        {
            max = lchild;
        }    
        if(rchild<=size && a[rchild]>a[max])
        {
            max = rchild;
        }
        if(max != i)
        {
            temp = a[i]; /*交换a[i]和a[max]的值*/
			a[i] = a[max];
			a[max] = temp;
            heap_ajust(a, max, size); /*被交换的位置曾经是大根堆，如今可能不是大根堆
			                            所以须要又一次调整使其成为大根堆结构*/ 
        }
    }        
}

void build_bheap(int *a, int size) /*建立大根堆*/ 
{
    int i;
    for(i=size/2; i >= 1; i--) /*非叶节点最大序号值为size/2*/
    {
        heap_ajust(a, i, size); /*每一个非叶子结点都须要调用这个函数*/   
    }    
} 

void heap_sort(int *a, int size) /*堆排序*/ 
{
    int i;
	int temp;

    build_bheap(a, size);
    for(i=size; i >= 1; i--)
    {
        temp = a[1];
		a[1] = a[i];
		a[i] = temp; /*交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面*/ 
        heap_ajust(a, 1, i-1); /*又一次调整堆顶节点成为大顶堆，仅仅有被交换的分支才有可能不是大根堆*/
    }
} 

int main(int argc, char *argv[])
{
    int a[]={0,16,20,3,11,17,8};
    int size = sizeof(a)/sizeof(int) -1;
	int i;

	printf("size = %d\n", size);
    heap_sort(a, size);
	printf("Sort over:"); 
    for(i=1;i <= size; i++)
        printf("%d ", a[i]);
    printf("\n");

    return 0;
}
           

程序运行结果