使用C++模版实现堆排序算法

lichaoyin

于 2011-11-04 14:43:52 发布

阅读量1.5k

点赞数

分类专栏：算法文章标签： c++ 算法 class 测试

本文链接：https://blog.csdn.net/lichaoyin/article/details/6935800

版权

堆排序是一种优秀的排序算法，它结合了插入排序和合并排序的优点，拥有O(nlogn)的时间复杂度且不需额外空间。本文将详细介绍如何使用C++模板实现堆排序的过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

合并排序具有较好的运行时间复杂度O(nlogn)，但却需要额外的O(n)的空间；插入排序不需要开辟新的空间，但其时间开销却维持在O(n^2)。这两种算法各有所长，但都不尽如人意，综合看来：不是用时间买空间，就是用空间换时间。有没有这样一种集众家所长的算法？既保持一个较好的时间复杂度，又不必开辟额外的空间。堆排序无疑是不二选择。

以下即是用模版实现的堆排序的算法。

#include<iostream>
usingnamespace std;

#define MAX_HEAP_SIZE 100

//
// 使用大顶堆进行堆排序

template<class T>
struct MaxHeap
{
	int size;
	T data[MAX_HEAP_SIZE+1];
	MaxHeap(){size = 0;}
};

template<class T>
void MaxHeapify(MaxHeap<T> &maxHeap,int k)
{
	int left, right, largest;
	while(k <= maxHeap.size/2)
	{
		largest = k;
		left = k*2;
		right = k*2+1;
		if (left<=maxHeap.size && maxHeap.data[left]>maxHeap.data[largest])
			largest = left;
		if (right<=maxHeap.size && maxHeap.data[right]>maxHeap.data[largest])
			largest = right;
		if (largest !&

最低0.47元/天解锁文章