数据结构-堆排序笔记

1  思路

总体思路

首先我们会拿到一个无序的数组,我们需要先对其构建成一个堆。下面我们示例将会构建成大顶堆。然后我们对顶堆的元素进行位置之间的交换。交换的同时继续对其维护大顶堆的性质,直至大顶堆只剩下一个元素。

具体思路

首先我们先将一个无序数据将其构建成一个大顶堆。我们将数据模拟成一个大顶堆,并不是真实地去构建。其实就是按照堆中元素下标对应关系来实现。

元素之间下标关系:

下标为  i  的节点的父节点下标为  (i + 1) / 2

下标为  i  的节点的左孩子的下标为  i   *  2  +  1

下标为  i  的节点的右孩子的下标为  i   *  2  +  2

然后我们来调整这个数组让他符合大顶堆的规则,就是调整对应的下标,交换数组内的元素

然后我们把整个数组看成未排序和已排序两个部分,也就是未排序的数组的最大的元素和最小的元素的位置。在交换之后最大的元素已经在数组最后面,此时最后面就是有序的数组。然后我们在维护这个顶堆的规则。

2  具体实现

import java.util.*;public class Main {// 主函数入口public static void main(String[] args) {// 初始化一个整型数组int arr[] = new int[]{2, 1, 8, 122, 3, 6, 10, 11};// 调用sort方法对数组进行排序sort(arr);// 遍历排序后的数组并打印每个元素for (int i : arr) {System.out.print("" + i + " ");}}// 排序方法,使用堆排序算法static void sort(int arr[]) {int n = arr.length; // 获取数组长度// 从最后一个非叶子节点开始,向下调整每个节点,构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heap_sort(arr, n, i);}// 从最后一个元素开始,将其与堆顶元素交换,然后对堆进行调整for (int i = n - 1; i > 0; i--) {swap(i, 0, arr); // 将当前元素与堆顶元素交换heap_sort(arr, i, 0); // 对堆进行调整}}// 堆排序的辅助方法,用于向下调整堆private static void heap_sort(int[] arr, int n, int i) {int largest = i; // 初始化最大元素索引为当前节点int lson = i * 2 + 1; // 左子节点索引int rson = i * 2 + 2; // 右子节点索引// 如果左子节点存在且值大于当前最大元素,则更新最大元素索引if (lson < n && arr[lson] > arr[largest]) {largest = lson;}// 如果右子节点存在且值大于当前最大元素,则更新最大元素索引if (rson < n && arr[rson] > arr[largest]) {largest = rson;}// 如果最大元素不是当前节点,则交换它们,并递归地调整堆if (largest != i) {swap(largest, i, arr);heap_sort(arr, n, largest);}}// 交换数组中的两个元素private static void swap(int maxIndex, int minIndex, int arr[]) {int temp = arr[maxIndex]; // 临时变量用于交换arr[maxIndex] = arr[minIndex];arr[minIndex] = temp;}
}

3  总结

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/18107.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

如何在react中使用react-monaco-editor渲染出一个编辑器

一、效果展示 二、基于vite配置 1.首先安装react-monaco-editor和monaco-editor包 npm add react-monaco-editor npm i monaco-editor 2.其次创建一个单独的文件&#xff08;此处是tsx、直接用app或者jsx也行&#xff09; import { useState, useEffect } from react impo…

跨平台WPF框架Avalonia教程 六

添加交互性 用户界面的一个基本功能是与用户进行交互。在Avalonia中&#xff0c;您可以通过使用事件和命令来为应用程序添加交互性。本指南将通过简单的示例介绍事件和命令。 处理事件​ Avalonia中的事件提供了一种响应用户交互和控件特定操作的方式。您可以按照以下步骤处…

【传知代码】VRT_ 关于视频修复的模型

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀ VRT_ 关于视频修复的模型 背景介绍&#xff1a;重要性&#xff1a; VRT的重要性和研究背景VRT的背景&#xff1a;VRT的重要性&#xff1a; 视…

药界互联:中药实验管理的网络化

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了中药实验管理系统的开发全过程。通过分析中药实验管理系统管理的不足&#xff0c;创建了一个计算机管理中药实验管理系统的方案。文章介绍了中药实验管理系统的系…

【Linux】进程字段、环境变量与进程地址空间

&#x1f308; 个人主页&#xff1a;谁在夜里看海. &#x1f525; 个人专栏&#xff1a;《C系列》《Linux系列》《算法系列》 ⛰️ 丢掉幻想&#xff0c;准备斗争 目录 一、查看进程字段 1.字段说明 2.进程优先级 二、环境变量 1.概念 2.指令与PATH 3.环境变…

基于isSpring的PPT转换

背景 PPT课件目前还是一项在教学中高度频繁使用的工具&#xff0c;对于在线教学就更为重要了。如何把PPT转换为在线web&#xff0c;同时保留更多的PPT特性&#xff08;动画、音效、视频&#xff09;呢&#xff1f;这里介绍一种基于iSpring的PPT转换工具。用以解决在线PPT的这一…

【论文笔记】LoRA: Low-Rank Adaptation of Large Language Models

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: LoRA: Low-Rank Adaptatio…

RHCE的学习(21)

第三章 Shell条件测试 用途 为了能够正确处理Shell程序运行过程中遇到的各种情况&#xff0c;Linux Shell提供了一组测试运算符。 通过这些运算符&#xff0c;Shell程序能够判断某种或者几个条件是否成立。 条件测试在各种流程控制语句&#xff0c;例如判断语句和循环语句中…

智能购物时代:AI在电商平台的革命性应用

在当今数字化时代&#xff0c;人工智能&#xff08;AI&#xff09;技术已成为推动电商行业发展的关键力量。AI技术的应用不仅改变了电商的运营模式&#xff0c;还极大地丰富了消费者的购物体验。随着技术的不断进步&#xff0c;AI在电商领域的应用越来越广泛&#xff0c;从个性…

【Linux】环境变量

目录 一、什么是环境变量: 1、系统命令搜索路径&#xff08;PATH&#xff09;&#xff1a; 2、HOME&#xff1a; 3、SHELL&#xff1a; 4、添加环境变量&#xff1a; 二、通过代码获取环境变量&#xff1a; 三、主函数参数&#xff1a; argc表&#xff1a; envp表&…

28.<Spring博客系统④(使用MD5摘要算法对数据库密码进行加密)>

密码算法简介 1.对称加密算法&#xff1a;加密和解密算法一样 2.非对称加密算法&#xff1a;公钥加密、私钥解密 3.摘要算法&#xff1a;不能解密&#xff0c;不可逆 简单介绍了解一下&#xff1a; 一、对称密码算法 是指加密秘钥和解密秘钥相同的密码算法. 常见的对称密码算法…

如何用GPT-4o解读视频

OpenAI在去年推出的GPT-4V已经支持了多模态识别&#xff0c;但一直仅限于图片输入&#xff0c;不支持视频。相比之下&#xff0c;Google的Gemini早已支持视频识别。最近&#xff0c;我司业务场景中出现了一个需要识别视频的需求&#xff0c;而我们只采购了GPT-4o模型。这就引发…

计算机毕业设计Python美食推荐系统 美团爬虫 美食可视化 机器学习 深度学习 混合神经网络推荐算法 Hadoop Spark 人工智能 大数据毕业设计

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

华为HCIP——MSTP/RSTP与STP的兼容性

一、MSTP/RSTP与STP的兼容性的原理&#xff1a; 1.BPDU版本号识别&#xff1a;运行MSTP/RSTP协议的交换机会根据收到的BPDU&#xff08;Bridge Protocol Data Unit&#xff0c;桥协议数据单元&#xff09;版本号信息自动判断与之相连的交换机的运行模式。如果收到的是STP BPDU…

vim配置 --> 在创建的普通用户下

在目录/etc/ 下面&#xff0c;有个名为vimrc 的文件&#xff0c;这是系统中公共的vim配置文件对所有用户都有效 我们现在创建一个普通用户 dm 创建好以后&#xff0c;我们退出重新链接 再切换到普通用户下 再输入密码&#xff08;是不显示的&#xff0c;输入完后&#xff0c;…

Vue通过file控件上传文件到Node服务器

功能&#xff1a; 多文件同步上传、拖动上传、实时上传进度条、上传前的删除文件、原生file控件的美化 搁置的功能: 取消上传(上传过程中取消,即取消网络请求abort)、上传文件夹、大文件切片、以及很多限制条件未处理(重复上传、文件格式。。。) bug: 文件总大小(。。。竟然从d…

VScode学习前端-01

小问题合集&#xff1a; vscode按&#xff01;有时候没反应&#xff0c;有时候出来&#xff0c;是因为------>必须在英文状态下输入&#xff01; 把鼠标放在函数、变量等上面&#xff0c;会自动弹出提示&#xff0c;但挡住视线&#xff0c;有点不习惯。 打开file->pre…

Qwen2.5-3B-Instruct-GGUF部署

注册账号&#xff1a; 魔搭社区 等一会&#xff1a; 部署好了&#xff1a; 立即使用&#xff1a; 您部署的服务提供OpenAI API接口&#xff0c;可通过OpenAI SDK进行调用。请确保您的服务处于正常运行状态&#xff0c;并预先安装OpenAI SDK: pip install openai 在本地新建…

数据库管理-第262期 崖山:知其不可而为之(20241116)

数据库管理262期 2024-11-16 数据库管理-第262期 崖山&#xff1a;知其不可而为之&#xff08;20241116&#xff09;1 崖山之名2 绝地反击3 不止崖山总结 数据库管理-第262期 崖山&#xff1a;知其不可而为之&#xff08;20241116&#xff09; 作者&#xff1a;胖头鱼的鱼缸&am…

C语言:指针的变量运算及数组指针

1、指针的变量运算 指针变量保存的是地址&#xff0c;二地址本质上是一个整数&#xff0c;所以指针变量可以进行部分运算&#xff0c;列如加法减法、比较等&#xff0c;请看下面的代码&#xff1a; 1. #include <stdio.h> 2. 3. int main(){ 4. int a 10, *pa &a…