綜合效能最好的堆排序（c語言實現）

綜合效能最好的堆排序（c語言實現）

思路：

把一個數組看成一棵完全二元樹，在把這棵二元樹調整爲大棧堆，此時最大值在根節點，然後把根節點與最後一個葉子節點交換，在把這棵樹調整爲大棧堆；回圈結束，則排序完成，爲升序。

程式碼：

/調整index下標節點
void reheap(int arr[],size_t n,int index){
	int key = arr[index];
	int child = 2*index+1;
	while(child<n){//存在子節點
		if(child+1<n && arr[child+1]>arr[child]){
			++child;	
		}
		if(key<arr[child]){
			arr[index] = arr[child];//把子節點中較大值放到根節點處
			index = child;
			child = 2*index+1;
		}else{
			break;	
		}
	}
	arr[index] = key;
}

void heapsort(int arr[],size_t n){
	//把arr調整大棧堆	
	int i;
	for(i=n/2-1;i>=0;--i){//從n/2-1開始的節點纔有子節點
		reheap(arr,n,i);	
	}
	for(i=n-1;i>=0;--i){
		int tmp = arr[0];
		arr[0] = arr[i];
		arr[i] = tmp;
		reheap(arr,i,0);//每次只需要調整根節點即可
	}
}

下面 下麪是測試程式碼

void showarr(int arr[],size_t n){
	int i;
	for(i=0;i<n;i++){
		printf("%d ",arr[i]);	
	}
	printf("\n");
}

int main(){
	int arr[] = {0,7,2,3,9,5,6,10,1,6,2,4,8};
	size_t n = sizeof(arr)/sizeof(arr[0]);
	heapsort(arr,n);
	showarr(arr,n);
	return 0;	
}

可以看到，排序結果是正確的。