堆排序-笔记(防止标题重复)

迈不过友情╰ 2022-12-27 07:57 130阅读 0赞

选择类排序  
简单选择排序:每一趟选出当前最小的记录, 将其交换到无序块的最前面.  
如此,无序块逐渐变小,N-1 趟完成  
(贪心,递归,动态规划)

引入:每一趟选择极值记录时,能否对序列做些特殊处理,方便后续各趟求  
极值的操作呢?

1 堆排序的原理  
1.1 一个序列,设它对应某完全二叉树的层序序列,  
若该二叉树任意节点局比起左右孩子结点大  
则称该序列为大顶堆  
1.2 堆排序原理:  
原始序列 -> 初始大顶堆 -> 由于根节点是无序块的最大值,堆顶和堆尾互换  
\-> 调整建堆,筛选 -> 堆顶堆尾互换  
1.3 筛选:  
堆顶和子节点比较, 兄弟结点之间比较 ->(保证双亲最大,必要时交换)  
如此重复直到每个结点均大于孩子  
1.4 初始大顶堆的构建:  
我记得是从后(二叉树的倒数第二层)往前实现的  
2 堆排序的算法实现

void HeapAdjust(SqList &L, int head, int tail)
    {
        
    	//备份
    	rc = H.r[head];
    	lchild = 2 * head;
    	rchild = 2 * head + 1;
    	//只要结点没有超出树节点的范围, 这里只是 左子树, 右子树无所谓超不超?
    	while (lchild <= tail)
    	{
        
    		if (rchild <= tail && H.r[lchild].key < H.r[rchild].key)
    			bigchild = rchild;
    		if (rc.key < H.r[bigchild].key)
    		{
        
    			//大孩子上移
    			H.r[head] = H.r[bigchild];
    			//这里head下降了, 降到了原来bigchild的位置
    			head = bigchild;
    			lchild = 2 *head;
    			rchild = 2 * head + 1;
    		}
    		else break;
    	}
    	//最终head的位置就是 备份元素应该填入的位置
    	H.r[head] = rc;
    }

初始大顶堆的构建:
    从最后一个非叶子结点开始,逐步筛选建堆,直到根节点

//这里的length其实是指最后一个序列的最后一个元素的位置
    //所以 /2 是为了求它的双亲
    for (i = H.length / 2; i > 0; i--)
    {
        
    	HeapAdjust(H, i, H.length);
    }
    堆排序的包装:
    void HeapSort(HeapType &H)
    {
        
    	for (int i = length / 2; i > 0; i--)
    		HeapAdjust(H.r, i, H.length);
    	for (int i = 1; i <= H.length - 1; i++)
    	{
        
    		//和无序块的尾部交换位置
    		swap(H.r[1], H.r[H.length - i + 1];
    		//这里(HeapAdjust)注意需要确保 无序块的 堆尾的位置
    		HeapAdjust(H.r, 1, H.length - i);
    	}
    }

3 总结与推广