堆排序 算法

适用范围

• 数据量大且数据呈流式输入

优点:

1. 比快速排序稍微慢一点点, 属于第一梯队的速度, 且速度稳定
2. 空间复杂度为O(1)

1. 相关概念:

use::二叉堆 顶堆

2. 算法思想:

1. 每次取大顶堆中最大的数
2. 再维护大顶堆, 使下一个最大数浮现上来, 方便下一次取用
3. 依次执行以上, 直到大顶堆取完

3. 在c语言中的实现

梗概:

1. 交换根结点与最后的叶结点
   1. 即得到的最大数序列, 又补上了二叉堆的根结点
2. 维护大顶堆, 只需要维护根结点的大树枝序列即可 代码:

void HeapSort(RecordType Records[],int len){
//实际传入的是Records[0...len-1]
//故堆排序中凡是对实际数组操作的,都要通过PHASE映射回原数组
	crt_heap(Records,len);//把传入数组化为有相位差的大顶堆
    len+=PHASE;//把上一步创建的大顶堆的相位差忽略
    /*把原数组看成Records[1...len],才算是二叉堆*/
	/*每次都把最大的数拿出来,并维护不断缩小的大顶堆*/
	for(int i=len;i>=2;--i){
		/*根结点与最后叶结点互换*/
		RecordType temp=Records[1-PHASE];
		Records[1-PHASE]=Records[i-PHASE];
		Records[i-PHASE]=temp;
        /*只需要维护根结点的大树枝序列*/
		sift(Records,1,i-1);//把拿出来的树排除在外
	}
}