堆排序算法小结

一时失言乱红尘 2022-04-02 14:54 188阅读 0赞

#  堆排序算法小结 #

## 1.前言 ##

堆排序算法基于的思想是基于选择排序的算法，是在树形选择排序基础上的排序算法的改进版本。

## 2.堆排序 ##

堆排序的实现，是构造一棵二叉树，使得二叉树中的每一个节点的值都要小于（大于）其左右节点的值。分别成为小顶堆，大顶堆。构造完成后，我们每次取二叉树的根节点，并从头开始改变原来数组中的值，那么我们最终可以得到一个有序的序列。那么难点在于如何去构造一棵这样的二叉树。我们先从**最靠近非叶子节点的节点开始从下往上进行调整**。用数组表示的话，就是从n/2这个节点处开始。逐步向上。从子节点中选出最大的节点与父亲节点进行比较，如果都小于那么不进行操作，如果有一个大于，那么我们需要将父节点变为子节点，但这个时候调整并没有完成，因为我们不知道，换下来的父亲节点与子节点的子节点的值的大小关系，所以我们需要在以子节点为父亲节点继续**向下调整**。

下面是代码

void heap_adjust(int *number,int s,int max)//构建一个大顶堆
    {
        
    	int rc = number[s];
    	for(int j=2*s;j<=max;j)
    	{
        
    		if (j<max&&number[j]<number[j + 1])//选择出两个子树中较大的那一个
    			j++;
    		if (rc > number[j])//如果number[s]>number[j]不进行操作
    			break;
    		number[s] = number[j];//否则就将j的值赋给s
    		s = j;//并继续以j为根节点向下调整，进行下一次比较时仍然是rc进行比较
    		//相当于从j开始继续向下调整，此时j的元素的值为number[s];
    	}
    	number[s] = rc;
    }
    
    void heap_sort(int *number,int n)
    {
        
    	for(int i=n/2;i>0;i--)
    	{
        
    		heap_adjust(number, i, n);//调整堆
    	}
    	for(int i=n;i>=1;--i)
    	{
        
    		int t = number[n];
    		number[n] = number[1];
    		number[1] = t;
    		heap_adjust(number, 1, i - 1);//对前n-1个元素继续进行调整
    	}
    }

## 3.堆的其他应用 ##

堆还可以应用于最小生成树的算法，因为每一个最小生成树的算法，都是取最短的那条边。而从堆中每次取最小点，只要O(1),建堆的过程是O(lgn),所以整个的时间复杂度为O(nlgn)

## 4. 杂言 ##

终于填上了之前的[坑][Link 1]:happy:大家有什么想说的都可以留言评论下呀。好希望得到反馈啊，**嘤嘤嘤**。

[Link 1]: https://blog.csdn.net/qq_40184139/article/details/85125891