栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

排序——堆排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

排序——堆排序

堆排序
  • 创建成堆
    • 向上调整建堆
      • 时间复杂度分析
    • 向下调整建堆
      • 时间复杂度分析
  • 堆排序


给我一组数据,如果对他进行堆排序,那么前提就需要把它变成一个堆的形式

创建成堆

升序——建大堆
堆顶一定是最大的,那么我们每一次把堆顶的元素和堆尾的数据进行交换,那么最后一个元素为最大的元素,最后再次调整成堆的形式,这样依次可以得到次大的,最后的最后得到一个升序的数组。

降序——建小堆
堆顶一定是最小的,那么我们每一次把堆顶的元素和堆尾的数据进行交换,那么最后一个元素为最小的元素,最后再次调整成堆的形式,这样依次可以得到次小的,最后的最后得到一个降序的数组。

以降序为例

向上调整建堆
void adjustdown(HPDataType* a,int n, int father)
{
	int child = 2 * father + 1;
	if (child < n - 1&&a[child + 1] < a[child])
		child++;
	if (child > n - 1 || a[father] <= a[child])
		return;
	swap(&a[child], &a[father]);
	adjustdown(a, n, child);
}
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		adjustdown(a,n, i);
	}

时间复杂度分析

给我父节点找子节点
设该二叉树的高度为h。
向上调整建堆,是从完全二叉树的倒数第二层开始。
第h-1层,每一个节点都要调整1次。——共调整2h-2

时间复杂度O(N)

向下调整建堆
void adjustup(HPDataType* a, int child)
{
	int father = (child - 1) / 2;
	if (child <= 0 || a[father] <= a[child])
		return;
	swap(&a[child], &a[father]);
	adjustup(a, father);
}

	int i = 0;
	for (i = 1; i 
		adjustup(a, i);
	}
时间复杂度分析

给我子节点找父节点
我们从完全二叉树的第2层开始调整建堆。
具体的实现看下面的这张图

时间复杂度O(N*logN)

堆排序

时间复杂度O(N*logN)

void HeapSort(int* a, int n)
{
	//建小堆
	//向上建堆O(N)
	int i = 0;
	//for (i = (n - 1 - 1) / 2; i >= 0; i--)
	//{
	//	adjustdown(a,n, i);
	//}
	//向下建堆O(N*logN)
	for (i = 1; i 
		adjustup(a, i);
	}
	//排序O(N*logN)
	for (i = 0; i < n; i++)
	{
		swap(&a[0], &a[n - 1 - i]);
		adjustdown(a, n-i-1, 0);
	}
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937441.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号