排序之堆排序

这篇具有很好参考价值的文章主要介绍了排序之堆排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在计算机科学中,排序是一种常见的操作。它的目标是将一组元素按照一定的顺序排列。不同的排序算法有不同的性能特性,选择哪种算法取决于具体的应用场景和需求。本文将介绍一种非常有效的排序算法——堆排序。

什么是堆排序?

堆排序是一种基于二叉堆的比较排序算法。它的主要思想是将待排序的序列构造成一个大顶堆(或小顶堆),然后将堆顶的最大元素与末尾元素进行交换,再调整剩余元素为大顶堆,如此反复,直到整个序列有序。

堆排序的步骤

  1. 构建大顶堆:首先,我们需要将待排序的序列构造成一个大顶堆。这个过程可以通过从最后一个非叶子节点开始,依次向上调整每个节点来实现。

  2. 堆顶堆底进行交换:然后,我们将堆顶的元素(即当前最大的元素)与堆底的元素进行交换。这样,最大元素就位于了正确的位置。

  3. 调整剩余元素为大顶堆:最后,我们需要将剩余的元素重新调整为大顶堆。这个过程同样可以通过从最后一个非叶子节点开始,依次向上调整每个节点来实现。

  4. 重复以上步骤,直到整个序列有序:这就是堆排序的基本过程。

时间复杂度

时间复杂度:O(nlogn)

空间复杂度:O(1)。

代码实现

package sort;

import java.util.Arrays;
//堆排序
public class HeapSort {

	public static void main(String[] args) {
		int[] arr = {5,7,4,2,0,3,1,6};
		//构建大顶堆
		for(int i =arr.length;i>=0;i--) {
			adjust(arr, i, arr.length);
		}
		//堆顶堆底进行交换
		for(int j = arr.length-1;j>=0;j--) {
			int temp = arr[j];
			arr[j] =arr[0];
			arr[0] = temp;
			adjust(arr, 0, j);
		}
		System.out.println(Arrays.toString(arr));
	}
	/**
	 * 堆的维护
	 * @param arr
	 * @param parent
	 * @param length
	 */
	public static void adjust(int[] arr,int parent,int length) {
		int child = 2*parent+1;
		while(child<length) {
			//定义右孩子,找到左右孩子的最大值
			int rchild = child+1;
			if(rchild<length && arr[child]<arr[rchild]) {
				child++;
			}
			//父节点进行对比
			if(arr[parent]<arr[child]) {
				//父节点进行交换
				int temp = arr[parent];
				arr[parent] = arr[child];
				arr[child] = temp;
				parent = child;
				child = 2*child+1;
			}else {
				break;
			}
		}	
	}
}

总结

堆排序是一种非常高效的排序算法,其时间复杂度为O(nlogn),空间复杂度为O(1)。虽然它的实现相对复杂一些,但是一旦理解了其基本思想,就可以很容易地掌握这种算法。希望这篇文章能帮助你更好地理解和应用堆排序。文章来源地址https://www.toymoban.com/news/detail-794948.html

到了这里,关于排序之堆排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之堆

    目录 前言 堆的概念与结构 堆的实现  堆的初始化 堆的销毁 堆的显示 堆的插入 堆的向上调整算法 堆的删除 堆的向下调整算法 堆的判空 获取堆顶元素  堆的数据个数 堆的创建 二叉树的顺序结构存储即使用数组存储,而 数组存储适用于完全二叉树 , 完全二叉树不会存在空

    2024年02月07日
    浏览(30)
  • 数据结构之堆的结构与实现

    目录 一、堆的概念及结构 1.1堆的概念  1.2堆的性质 1.3堆的结构 二、堆的实现 2.1堆向下调整算法(父亲与孩子做比较)  2.2堆的向上调整算法(孩子与父亲做比较) 2.3堆的创建(向下建堆)  2.4向下建堆的时间复杂度 2.5堆的插入 2.6堆的删除 2.7堆的完整代码实现 三、堆的应

    2024年02月08日
    浏览(38)
  • 数据结构之堆的应用

    在我们学习了堆之后我们知道,无论是大堆还是小堆,堆顶的元素要么最大,要么最小。 对于堆插入的时间复杂度为O(logn)也就是向上调整算法的复杂度,删除一个堆中的元素为O(logn),堆在我们日常生活中还是常用到的。 目录 1.top k问题(优质筛选问题) 2.堆排序 1.向

    2024年02月08日
    浏览(50)
  • 【数据结构之堆的实现】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续学习怎么实现基本的操作。所以先建议看完上篇知识点,才有助于消化知识和理解。 / 知识点汇总 / 概念 :堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看

    2024年01月19日
    浏览(42)
  • 数据结构初阶--二叉树的顺序结构之堆

    目录 一.堆的概念及结构 1.1.堆的概念 1.2.堆的存储结构 二.堆的功能实现 2.1.堆的定义 2.2.堆的初始化 2.3.堆的销毁 2.4.堆的打印 2.5.堆的插入 向上调整算法 堆的插入 2.6.堆的删除 向下调整算法 堆的删除 2.7.堆的取堆顶元素 2.8.堆的判空 2.9.堆的求堆的大小 三.堆的创建 3.1.向上调

    2024年02月14日
    浏览(42)
  • 【数据结构初阶】之堆(C语言实现)

    前言 :在二叉树基础篇我们提到了二叉树的顺序实现,今天让我们来学习一下特殊的二叉树———堆的相关知识。 📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月

    2024年04月09日
    浏览(80)
  • 数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中,由于第二个列表已经有序,所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中,每次插入时,只需要从上次插入的位置开始,继续向后寻找插入位置即可。这样一来,我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(42)
  • 【排序算法】数据结构排序详解

    前言: 今天我们将讲解我们数据结构初阶的最后一部分知识的学习,也是最为“炸裂”的知识---------排序算法的讲解!!!! 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,

    2023年04月08日
    浏览(49)
  • 数据结构和算法笔记4:排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下: 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程,下面是要排序

    2024年01月21日
    浏览(62)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(75)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包