數據結構之---C語言實現堆排序

數據結構之---C語言實現堆排序

過程圖如下：（先建堆，在調整，插入，輸出）

代碼：

//堆排序（HeapSort）
//楊鑫
#include 
#include 
//堆調整，構建大頂堆，arr[]是待調整的數組，i是待調整的數組
//元素的位置，length是數組的長度
void HeapAdjust(int arr[], int i, int length)
{
	int Child;
	int temp;
	for(;2 * i + 1 < length; i = Child)
	{
		//子節點的位置 = 2 * (parent(父結點)) + 1
		Child = 2 * i + 1;
		//得到子結點中較大的結點
		if(Child < length - 1 && arr[Child + 1] > arr[Child])
				++Child;
		//如果較大的子結點大於父結點那麼把較大的子結點往上移動
		//替換它的父結點
		if(arr[i] < arr[Child])
		{
			temp = arr[i];
			arr[i] = arr[Child];
			arr[Child] = temp;
		}
		else
				break;
	}
}
//堆排序算法
void HeapSort(int arr[], int length)
{
	int i;
	//調整序列的前半部分元素，調整完之後第一個元素
	//是序列的最大元素，length/2-1是最後一個非葉子結點
	for(i = length/2 - 1; i >= 0; --i)
			HeapAdjust(arr, i, length);
	//從最後一個元素開始對序列進行調整，不斷的縮小調整
	//的范圍直到第一個元素
	//循環裡是把第一個元素和當前的最後一個元素交換
	//保證當前的最後一個位置的元素是現在這個序列的最大的
	//不斷的縮小調整heap的范圍，每一次調整完畢保證第一個
	//元素是當前序列的最大的元素
	for(i = length - 1; i > 0; --i)
	{
		arr[i] = arr[0]^arr[i];
		arr[0] = arr[0]^arr[i];
		arr[i] = arr[0]^arr[i];
		HeapAdjust(arr, 0, i);						//遞歸調整
	}
}

int main()
{
	int i;
	int num[] = {98, 48, 777, 63, 57, 433, 23, 1112, 1};	
	printf(==================堆排序==============
);
	printf(實質上是一顆完全二叉樹，利用樹的根結點
與子節點的性質進行排序
);
	printf(======================================

);
	printf(待排序的數據是：
);
	for(i = 0; i < sizeof(num)/sizeof(int); i++)
	{
		printf(%d , num[i]);
	}
	printf(
);
	HeapSort(num, sizeof(num)/sizeof(int));
	printf(排序後的數據是：
);
	for(i = 0; i < sizeof(num)/sizeof(int); i++)
	{
		printf(%d , num[i]);
	}
	printf(
);
	return 0;
}