数据结构与算法--堆排序

• 堆排序由来
• 堆排序代码实现
• 堆排序优化
• 堆排序优缺点分析

基于选择排序得到的堆排序
选择排序实现：
每次找到最小元素所在的位置，将该位置的元素与前面待放入元素交换，即每次都选择最小的放在当前位置

void Selection_sort(ElementType A[],int n)
{
	int MinPosition;
	for(int i=0;i 
算法看起来时间复杂度是O(n)，但其实不是，ScanForMin()找最小值这个函数复杂度也为O(n),整体复杂度仍然为O(n^2)
 所以我们想有没有什么办法可以将ScanForMin函数的复杂度降低呢？得到最小值，自然想到了最小堆，最小堆每次得到最小值即根节点元素，复杂度为O(logn),整体就可以保证排序算法复杂度为O(nlongn)
 
堆排序代码实现 
主要代码思路：
 
void  Heap_sort(ElementType A[],int n)
{
	ElementType tmpA[n];
	BuildHeap(A,n);    //O(N)
	for(int i=0;i 
最后需要将排序好的tmpA导回到A中，实现用户的需求，即将A排好序
 
完整可运行代码：
 
#include
using namespace std;
typedef int ElementType ;
void Swap(ElementType &a,ElementType &b)
{
	int t=a;
	a=b;
	b=t;
} 

//下沉函数 
void percdown(ElementType A[],int i,int n)
{
	int temp=A[i];
	int pare=i,child=i; //注意当我们的堆数组元素下标从0开始标注时，左孩子为 2*i+1,右孩子为2*i+2
	while((pare*2+1)A[child+1]))  child++;     //得到相对较小的 
		if(temp>A[child])
		{
			A[pare]=A[child];
			pare=child;
		}	
		else break;
	}
	A[pare]=temp;
}
//将数组调整为最小堆 
void BuildHeap(ElementType A[],int n)
{
	for(int i=n/2-1;i>=0;i--)
	{
		percdown(A,i,n);
	}
}
//删除堆中最小元素并返回最小值 
int DeleteMin(ElementType A[],int n)
{
	int temp=A[0];
	Swap(A[0],A[n]);
	percdown(A,0,n);
	return temp;
}
//堆排序
void  Heap_sort(ElementType A[],int n)
{
	ElementType tmpA[n];
	BuildHeap(A,n);    //O(N)
	for(int i=0;i>n;
	ElementType A[n];
	for(int i=0;i>A[i];
	Heap_sort(A,n);
	for(int i=0;i 
堆排序优化 
可以看出这种堆排序算法能保证时间复杂度为O(nlogn),唯一不足的就是需要开一个tmpA数组存储由A构造的最小堆，再仔细想想，真的有必要这么做吗？
 可以看出，在最小堆中删除最小元素时，我们采取的是将最小元素与堆中的最后一个元素交换，然后对剩下的堆元素进行下面的操作，最后再回过头去看堆数组，很神奇，发现堆数组居然是按从大到小排序好的（肯定啊，每次都拿最小的放在后面）
 于是我们利用这个思路对堆排序进行一下改进，这次我们不构造最小堆了，我们构造最大堆
 
//下沉函数 
void PercDown(ElementType A[],int i,int n)
{
	int temp=A[i];
	int pare=i,child=i;
	while((pare*2+1)=0;i--)   //BuildHeap 构造最大堆
	{
		PercDown(A,i,n);
	}
	for(int i=n-1;i>0;i--)
	{
		Swap(A[0],A[i]);
		PercDown(A,0,i);     
	} 
}
 
堆排序优缺点分析 
优点：堆排序是很好的排序方法，时间复杂度始终为O(nlogn)，不存在什么最坏情况，平均情况的，并且是稳定的排序，并且如果只是想采用这种思想，不想写堆实现代码，可以利用c++STL里的优先队列得到最小值，赞
 缺点：？？？我觉得不存在吧，一个字：好