堆排序总结

1.算法原理

1. 算法基于顺序存储的“完全二叉树”：结点i的左孩子是2i;右孩子是2i+1;父节点是i/2；编号小于n/2的结点都是分支结点。
2. 大根堆（根>=左、右），小根堆（根<=左、右）
3. 建堆：编号<=n/2的所有结点依次”下坠“调整（自底向上处理分支结点），调整规则：小元素逐层”下坠“（与关键字更大的孩子交换）。
4. 排序：将栈顶元素加入有序子序列（栈顶元素与栈底元素交换），栈底元素换到栈顶后，需要进行”下坠“调整，恢复”大根堆“的特性；重复上述重复n-1趟。

2.具体代码

//第一部分：排序算法
//9-7 堆排序（以大根堆为例） 
//2020.09.26 
void BuildMaxHeap(int A[],int len)
{
	int i;
	for(i=len/2;i>0;i--)
	HeadAdjust(A,i,len);
} 
void HeadAdjust(int A[],int k,int len)
{
	int i;
	A[0]=A[k];//将需要下坠的值暂存在A[0]中 
	for(i=k*2;i<=len;i*=2)
	{
		if(i<len&&A[i+1]>A[i])//若分支结点包含左右孩子节点，且右孩子大于左孩子 
		  i++;
		if(A[i]<A[0]) break;//若分支结点比孩子结点都大，则该节点下坠结束 
		else {
			A[k]=A[i];//把较大的孩子结点的值赋给分支结点 
			k=i;//继续循环，直到下坠结束 
		}		
	}
		A[k]=A[0];//下坠结束条件：1.循环到了叶子结点；2.分支结点大于左右孩子结点 
}
//基于大根堆进行排序
void Swap(int *x,int *y)
{
	int temp;
	temp=*x;
	*x=*y;
	*y=temp;
}
void HeapSort(int A[],int len)
{
	int i;
	BuildMaxHeap(A,len);//先建立大根堆 
	for(i=len;i>1;i--)//len-1趟的交换和建堆 
	{
		Swap(&A[1],&A[i]);//栈顶元素和栈底元素交换 
		HeadAdjust(A,1,i-1);//把剩余的待排序元素整理成堆 
	}
} 
//小根堆的插入操作
void InsertHeap(int A[],int len,int num)//num表示需要插入到小根堆的数值 
{
	int i,k=len+1;//将K值定义为需要判断的位置 
	A[0]=num;
	A[k]=num;
	for(i=k/2;i>0;i/=2)//插入的数值不断上浮，直到不能上浮为止 
	{
		if(A[i]<A[0]) break;//分支结点小于孩子节点，插入操作结束 
		else {
			A[i]=A[k];
			k=i;
		}
	}
	A[k]=A[0];
} 
//小根堆的删除操作
void DeleteHeap(int A[],int len,int index)
{
	A[index]=A[len];
	HeadAdjust(int A[],int index,int len-1);
} 

3.性能分析
空间复杂度：O（1）
时间复杂度：建堆：O（n）,排序：O（nlog₂n）;总的时间复杂度：O（nlog₂n）;
稳定性：不稳定
基于大根堆的堆排序得到”递增序列“，基于小根堆的堆排序得到”递减序列“。