一起学习交流~

排序-03-堆排序

算法 laomuji 12个月前 (10-09) 335次浏览 已收录 0个评论

一、什么是堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序 的最好、最差、平均时间复杂度都是nlogn

二、堆排序的思路

假设有一个数组int nums[10] = { 1,9,2,8,3,7,4,6,5,10 };

把它当作一个二叉树, 树的每个节点的左孩子和右孩子的下标为2n+1和2n+2

堆排序的思想是,当前节点、左孩子、右孩子进行比较,把三个中间最大的放到顶部

下标和值如下图

比较:3 10 左孩子的值最大 swap:3 10

比较:8 6 5 当前节点的值最大 不交换

比较:2 7 4 左孩子的值最大 swap:2 7

比较:9 8 10 右孩子的值最大 swap:9 10

比较:1 10 7 左孩子的值最大 swap:1 10

得到下图的结果

此时最大的值就在数组最前方,再将剩余的数字当作一个数组,重新建立一个二叉树,如图

比较:9 5 3 当前节点的值最大 不交换

比较:8 4 6 当前节点的值最大 不交换

比较:7 9 2 左孩子的值最大 swap:7 9

比较:1 9 8 左孩子的值最大 swap:1 9

得到下图结果:

此时最大的值又在最前方,和之前的思想一样,再将剩余的数字当作一个数组,重新建立一个二叉树树,直到树的深度为0时,终止.

树的深度通过数组个数/2-1得到,得到的是最后一个拥有孩子的节点的下标.

所有过程如下:

三、具体代码

#include<iostream>
//堆排序 速度都为nlogn
//把数组当作二叉树处理,每次把最大的节点与顶点交换
//1,9,2,8,3,7,4,6,5,10
//树顶是1,找到最大的节点,10,交换后为:10,9,2,8,3,7,4,6,5,1
//然后数组后移 9,2,8,3,7,4,6,5,1
//树顶是9,找到最大的节点,9,交换后为:9,2,8,3,7,4,6,5,1
//然后数组后移 2,8,3,7,4,6,5,1
//树顶是2,找到最大的节点,8,交换后为8,2,3,7,4,6,5,1
//依次循环到最后
using namespace std;
template<typename T>
void heapSort(T nums[], int length)
{
	for (; length > 0; length--, nums++)
	{
		int depth = length / 2 - 1;//二叉树深度
		for (int i = depth; i >= 0; i--)
		{
			int top = i;//假设当前节点最大
			int leftChild = i * 2 + 1;//左孩子
			int rightChild = i * 2 + 2;//右孩子
			//获取最大的节点
			if (leftChild < length && nums[leftChild] > nums[top])top = leftChild;
			if (rightChild < length && nums[rightChild] > nums[top]) top = rightChild;
			//如果当前节点不是最大 就与最大的孩子节点交换
			if (i != top)
			{
				T temp = nums[i];
				nums[i] = nums[top];
				nums[top] = temp;
			}
		}
	}


}

int main()
{
	int nums[10] = { 1,9,2,8,3,7,4,6,5,10 };
	heapSort(nums, 10);
	for (int i = 0; i < 10; i++)
	{
		cout << nums[i] << " ";
	}

}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论