[数据结构与算法]堆排序c/c++实现

主要有两个步骤，一个是建堆（时间复杂度nlgn），一个是排序（时间复杂度nlgn），总的时间复杂度为nlgn,细节见代码。

下面给出从小到大排序的代码。

#include <bits/stdc++.h>
using namespace std;
void MaxHeap(int* A,int n);
void MaxHeapFixUp(int* A,int i,int n);
void Heapsort(int* A,int n);
int main() {
	int A[] = {38,6,34,105,81,18,0,47,-9,7};
	int n = sizeof(A)/sizeof(A[0]);//数组元素个数的计算要在main函数中进行 
	Heapsort(A,n);
	for(int i=0;i<n;i++)
		printf("%d ",A[i]);
	return 0;
} 

void MaxHeap(int* A,int n) {
	//从n/2-1开始因为叶子节点可以将其看作小顶堆或者大顶堆，所以直接从n/2-1的地方开始调整 
	for(int i=n/2-1;i>=0;i--)
		MaxHeapFixUp(A,i,n);	
}
		
void MaxHeapFixUp(int* A,int i,int n) {
	//先找到左右孩子,用max指向最大值 
	int left = 2*i+1;
	int right = 2*i+2;
	if(left>=n) return;//注意判断是否越界，这也是递归的出口 
	int max = left;
	if(right>=n) max = left;//如果程序能执行到这，说明左孩子没有越界，对右孩子进行判断
	else {
		if(A[right]>A[left]) max = right;
	}
	//将max调整至当前根节点
	if(A[i]>A[max]) return;
	else swap(A[i],A[max]); 
	//i变更为小孩子的位置，递归调整
	MaxHeapFixUp(A,max,n);
}
	
void Heapsort(int* A,int n) {
	//数组堆化
	MaxHeap(A,n);
	//每一个节点都要进行调整 
	for(int x=n-1;x>=0;x--) {
		//把堆顶（整个堆的堆顶）和最后一个元素（缩小范围后的最后一个元素）进行交换
		swap(A[0],A[x]);//交换完最后一个元素一定是最大 
		//缩小堆的范围，对堆顶元素进行向下调整
		MaxHeapFixUp(A,0,x-1); 
	}
} 

若要进行从大到小的排序，只需调整MaxHeapFixUp函数，建立小树堆即可。代码如下：

void MinHeapFixDown(int* A,int i,int n) {
	//先找到左右孩子,用min指向最小值 
	int left = 2*i+1;
	int right = 2*i+2;
	if(left>=n) return;//注意判断是否越界，这也是递归的出口 
	int min = left;
	if(right>=n) min = left;
	else {
		if(A[right]<A[left]) min = right;
	}
	//将min调整至当前根节点
	if(A[i]<A[min]) return;
	else swap(A[i],A[min]); 
	//i变更为小孩子的位置，递归调整
	MinHeapFixDown(A,min,n);
}