小白讀懂堆排序 調整堆，建立堆

堆排序過程

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

程式運作結果