经典算法（七）----堆排序----图解法让你快速入门

二、什么是堆排序？

说起堆排序，我们目标就是对给定的数组进行排序，这个排序方法采取堆的形式进行。所有我们堆排序分以下几步：

1. 把我们要排序的数组构造成一个大顶堆（从小到大排序），这里要注意，我们一开始有一个数组，数组有下标，这里的下标就和我们的角标一样。所以我们如果一旦有了一个数组，其实就有了一个堆，只不过这个对可能不满足最大堆或者最小堆的情况。假如我们要排序的数组是20，30，50，40，10，70，60，80，那我们就有下面这个堆。
2. 
3. 既然我们要对这个数组从小到大排序，那就把现有的堆变成大顶堆（至于为啥是大顶堆后面说）。
4. 变成大顶堆之后，堆定元素就是最大值，再把这个最大值和这个数组的最后一个元素交换位置，这样一来数组的最大值就放到了数组的尾部。再看这个堆（这时候这个堆不包括数组的最后一个元素了），这时候堆就不是最大堆了，又把这个堆需要变成最大堆，等变成最大堆之后，再把堆顶元素放到数组的倒数第二个位置。
5. 重复上面的操作，就可以实现数组的从小到大排序了。
6. 如果采取的是小顶堆，那么每次是把最小的数放到数组后面，重复这个操作，就可以实现从大到小排序了

三、堆排序的具体过程是什么？

在概括一下上面说的堆排序的步骤，其实就分两大步：

1. 第一步，把这个堆变成大顶堆
2. 第二步，把最大元素放到数组尾部，再重复第一步

下面先看第一步，假设我们要排序的数组为 20，30，50，40，10，70，60，80。（为了方便，数组下标从1开始）

上面是我们要排序的数组，下面是数组对应的堆。既然要变成大顶堆，就要最大的数移动到顶部，

那我们的一个堆怎样变成大顶堆呢，那我们就可以从根结点开始遍历，如果这个根结点的左孩子和右孩子有比根结点大的，那就选择一个较大的孩子，和这个根结点交换值，这样就达到较大的值在根部了。

上面的根结点函数就是可以把一个结点的值和他的孩子结点比较，如果孩子结点大于他，然后交换值。但是他有限制，他只能和他的孩子结点交换，并不能和他孩子结点的孩子结点交换， 所以通过调用这一个函数并不能直接把一个任意的堆变成大顶堆，这个函数能实现的功能就是把某个结点和他的对应的孩子结点交换，如果交换成功，孩子结点还可以和孩子的孩子结点交换，达到一个下沉的效果。下面看这个函数代码：

void HeapAdjust(int arr[],int first,int last)
{
	int temp=arr[first];//暂存“根”结点 
	int j;//子结点 
	for(j=2*first;j<=last;j=j*2)
	{
		//下面if语句的作用是找出子结点中比较大的那个 
		//j是左节点，j+1是右节点，
		//如果右节点大，那j+1就可以了，如果左节点大那就不用+1
		//执行完下面的语句，j下标是较大的那个子结点的下标 
		if(j<last &&arr[j]<arr[j+1])
			j++;
		
		//下面if语句的作用是如果“根”结点大于子结点，
		//结束查找即可
		if(temp>arr[j])
			break; 
		
		//理解下面两条语句可以类比插入排序，
		//还记得插入排序中的元素后移吗？ 这里是“下移” 
		arr[first]=arr[j];
		first=j; //如果下移，记录对应的下标，方便下次下移 
	}
	//同样类比插入排序，把要插入的元素，放到合适的位置 
        //不过这个first会在循环中会更新
	arr[first]=temp; 
} 

截止到现在为止，我们要知道这个函数的功能，更要知道这个函数的限制(不能直接把任意一个堆变成大顶堆)。

上面的所有就是实现大顶堆的函数，但是它并不能完成实现大顶堆，下面看第二步

第二步也是写一个函数来实现把最大元素放到数组尾部，重复第一步，但是这执行把最大元素放到数组尾部的时候，要处理第一步留下的问题。

 

---

 

解决办法：

我们首先看上面的图，我们函数的功能是可以交换一个结点和他的孩子结点的值，那么我们再看上图的所有绿色的叶子结点。

如果我们从这些绿色的叶子结点的根结点（也可说上图的非叶子结点，白色的圆圈）都使用一遍那个函数（从角标大的开始，因为角标大的可能作为角标小的孩子结点），那么我们是不是就可以实现从任意一个堆到大顶堆的转换了。

比如从角标为4的叶子结点使用大顶堆函数，那么40就会和80互换位置，

再对角标为2和角标3（他的两个孩子结点是80和10，而不是交换之前的40和10）的结点使用大顶堆函数，那50就会和70（70比60大，选择孩子结点中较大的）交换位置，20和80交换位置

再对角标为1的结点使用大顶堆函数，20就会和80交换位置。

经过上面的步骤就实现了堆向大顶堆转换（注意大顶堆的顶部最大，对其他位置没有要求）。 

上面的步骤就可以用下面的三行代码实现。（注意是从非叶子结点的角标最大值开始，往角标小的遍历）

注意，上面的非叶子结点的角标最大值是数值最后一个元素角标除以2得到的。遍历下面代码即可。

for(int i=len/2;i>0;i--)
{
		HeapAdjust(arr,i,len);
}

 

---

 

下面就需要把大顶堆的元素和这棵树的最后一个元素交换位置就可了，等到交换完位置，这时候这个堆就不是大顶堆了，然后调用一次大顶堆函数，就又可以把大顶堆变换出来了（想想为啥这时候调用一个函数就可以，初始的堆调 函数为啥就不可以变成大顶堆），下面看代码

void HeapSort(int arr[],int len) 
{
	for(int i=len/2;i>0;i--)//把堆变成大顶堆
	{
		HeapAdjust(arr,i,len);
	}


	for(int i=len;i>0;i--)//需要交换几次位置的次数 
	{
		//下面三行的代码是把堆顶最大的元素和堆尾最后一个元素换位置
		//这样一来，最大元素就在数组尾部了，
		//因此大顶堆 是用来从小 到大排序的 
		int temp=arr[1];
		arr[1]=arr[i];
		arr[i]=temp;
		
		//对堆剩下的元素继续排序。 
		HeapAdjust(arr,1,i-1);
	}
}

四、堆排序的代码实现

下面看完整的代码

#include<iostream>
using namespace std;
//堆排序函数    稳定 

void HeapAdjust(int arr[],int first,int last)
{
	int temp=arr[first];//暂存“根”结点 
	int j;//子结点 
	for(j=2*first;j<=last;j=j*2)
	{
		//下面if语句的作用是找出子结点中比较大的那个 
		//j是左节点，j+1是右节点，
		//如果右节点大，那j+1就可以了，如果左节点大那就不用+1
		//执行完下面的语句，j下标是较大的那个子结点的下标 
		if(j<last &&arr[j]<arr[j+1])
			j++;
		
		//下面if语句的作用是如果“根”结点大于子结点，
		//结束查找即可
		if(temp>arr[j])
			break; 
		
		//理解下面两条语句可以类比插入排序，
		//还记得插入排序中的元素后移吗？ 这里是“下移” 
		arr[first]=arr[j];
		first=j; //如果下移，记录对应的下标，方便下次下移 
	}
	//同样类比插入排序，把要插入的元素，放到合适的位置 
	arr[first]=temp; 
} 

void HeapSort(int arr[],int len) 
{
	for(int i=len/2;i>0;i--)
	{
		HeapAdjust(arr,i,len);
	}
	for(int i=len;i>0;i--)//需要交换几次位置的次数 
	{
		//下面三行的代码是把堆顶最大的元素和堆尾最后一个元素换位置
		//这样一来，最大元素就在数组尾部了，
		//因此大顶堆 是用来从小 到大排序的 
		int temp=arr[1];
		arr[1]=arr[i];
		arr[i]=temp;
		
		//对堆剩下的元素继续排序。 
		HeapAdjust(arr,1,i-1);
	}
}


//输出数组的值
void printf(int arr[],int len)
{
	for(int i=1;i<=len;i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}
int main()
{
	//要排序的数组 ,为了方便理解，数组下标从1开始 
	int arr[]={0,3, 44,38, 5,47,15,36,26,27,2 ,46,4 ,19,50,48};
	int len=15;//要排序的数组长度 
	
	//排序 
	HeapSort(arr,len);
	
	//输出 
	printf(arr,len);
	return 0;
}

运行结果：

五、堆排序的代码详解

1. 首先是要了解转换大顶堆的函数，在符合条件的情况下，他是一个可以把根结点逐渐下称的过程。并不能可以把随便一个堆变成大顶堆
2. 懂得怎样把随便一个堆变成大顶堆
3. 交换堆顶元素和堆的最后一个元素，在调用大顶堆函数

本文参考以及引用：

百度百科

 

如果对其他的算法还有兴趣，可以点击下面的链接。

1. 经典算法（一）----冒泡排序----图解法让你快速入门

2. 经典算法（二）----选择排序----图解法让你快速入门

3. 经典算法（三）----插入排序----图解法让你快速入门

4. 经典算法（四）----希尔排序----图解法让你快速入门

5. 经典算法（五）----归并排序----图解法让你快速入门

6. 经典算法（六）----快速排序----图解法让你快速入门

7. 经典算法（七）----  堆排序 ----图解法让你快速入门

8. 经典算法（八）----计数排序----图解法让你快速入门

9. 经典算法（九）----基数排序----图解法让你快速入门

10. 经典算法（十）----  桶排序  ----图解法让你快速入门

 

创作不易，如果本文对你起到了一些帮助，何不点个赞再走呢！！！