【游戏算法】编程实现堆排序

参考答案：

堆排序编程实现：

void createHeep(int ARRAY[], int sPoint, int Len) //生成大根堆
{
	while ((2 * sPoint + 1) < Len)
	{
		int mPoint = 2 * sPoint + 1;
		if ((2 * sPoint + 2) < Len)
		{
			if (ARRAY[2 * sPoint + 1] < ARRAY[2 * sPoint + 2])
			{
				mPoint = 2 * sPoint + 2;
			}
		}
		if (ARRAY[sPoint] < ARRAY[mPoint]) //堆被破坏，需要重新调整
		{
			int tmpData = ARRAY[sPoint]; //交换 sPoint 与 mPoint 的数据
			ARRAY[sPoint] = ARRAY[mPoint];
			ARRAY[mPoint] = tmpData;
			sPoint = mPoint;
		}
		else
		{
			break; //堆未破坏，不再需要调整
		}
	}
	return;
}
void heepSort(int ARRAY[], int Len) //堆排序
{
	int i = 0;
	for (i = (Len / 2 - 1); i >= 0; i--) //将 Hr[0，Lenght-1]建成大根堆
	{
		createHeep(ARRAY, i, Len);
	}
	for (i = Len - 1; i > 0; i--)
	{
		int tmpData = ARRAY[0]; //与最后一个记录交换
		ARRAY[0] = ARRAY[i];
		ARRAY[i] = tmpData;
		createHeep(ARRAY, 0, i); //将 H.r[0..i]重新调整为大根堆
	}
	return;
}
int main(void)
{
	int ARRAY[] = { 5, 4, 7, 3, 9, 1, 6, 8, 2 };
	printf("Before sorted:\n"); //打印排序前数组内容
	for (int i = 0; i < 9; i++)
	{
		printf("%d ", ARRAY[i]);
	}
	printf("\n");
	heepSort(ARRAY, 9); //堆排序
	printf("After sorted:\n"); //打印排序后数组内容
	for (i = 0; i < 9; i++)
	{
		printf("%d ", ARRAY[i]);
	}
	printf("\n");
}

说明：堆排序，虽然实现复杂，但是非常的实用，另外读者可是自己设计实现小堆排序的算法；虽然和大堆排序的实现过程相似，但是却可以加深对堆排序的记忆和理解。