用C++实现堆排序-创新互联

堆数据结构是一种数组对象，它可以被视为一颗完全二叉树结构。

创新互联是创新、创意、研发型一体的综合型网站建设公司，自成立以来公司不断探索创新，始终坚持为客户提供满意周到的服务，在本地打下了良好的口碑，在过去的十多年时间我们累计服务了上千家以及全国政企客户，如木包装箱等企业单位，完善的项目管理流程，严格把控项目进度与质量监控加上过硬的技术实力获得客户的一致夸奖。

大堆：每个父节点都大于孩子节点。

最小堆：每个父节点都小于孩子节点。

堆排序的思想：对于给定的N个数据，初始时把这些记录看作是一颗顺序存储的二叉树，然后将其调整为一个大堆，然后将堆的最后一个元素与堆顶元素（即二叉树的根节点）进行交换，堆的最后一个元素即为大记录；接着将（N-1）个元素（即不包括大记录）重新调整为一个大堆，再将堆顶元素与堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆只剩下一个元素为止，该元素即为最小记录，此时可得到一个有序序列。

堆排序主要包括两个过程：一是构建堆；二是交换堆顶元素与最后一个元素的位置。

程序如下：

#include
#include
using namespace std;

void AdjustDown(int *array,int size,int root)
{
	assert(array);
	int child = 2 * root + 1;
	while (child < size)
	{
		if (child + 1 < size&&array[child] < array[child + 1])
		{
			++child;
		}
		if (array[child]>array[root])
		{
			swap(array[root],array[child]);
			root = child;
			child = 2 * root + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int *array, int size, int root)
{
	//找到第一个非叶子节点构建堆
	for (int i = (size - 2) / 2; i >= 0; --i)
	{
		AdjustDown(array,size,0);
	}
	for (int i = 0; i < size; ++i)
	{
		swap(array[0],array[size-1-i]);
		AdjustDown(array,size-1-i,0);
	}
}

int main()
{
	int array[10] = {12,10,16,6,8,9,11,9,7,13};
	for (int i = 0; i < 10; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	HeapSort(array,10,0);
	for (int i = 0; i < 10; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	return 0;
}

程序运行结果：

    

        堆排序方法对记录较少的文件效果一般，但对于 记录较多的文件还是很有效的，其运行时间主要耗费在创建堆和反复调整堆上。堆排序即使在最坏的情况下，其时间复杂度也为O（N*logN）。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

本文题目：用C++实现堆排序-创新互联
文章路径：http://cdiso.cn/article/dggphe.html