当前位置: 首页 > news >正文

十大排序——4.堆排序

前面我们讲了堆,现在我们来看一下队排序。

堆排序的步骤:

  • 首先将一个无序数组建立成一个大顶堆
  • 然后,将堆顶的元素和堆低的元素进行交换(即将最大的元素交换的到堆底),缩小并下潜调整堆
  • 重复上一步,直到堆中只剩一个元素为止

下面来看一下代码实现:

下面看一下具体的代码:

package Sorts;
//堆排
public class HeapSort {public static void main(String[] args) {int[] arr = {16, 7, 3, 20, 17, 8};heapSort(arr);for (int i : arr) {System.out.print(i + " ");}}/*** 创建堆*/private static void heapSort(int[] arr) {//创建堆for (int i = (arr.length - 1) / 2; i >= 0; i--) {//从第一个非叶子结点从下至上,从右至左调整结构adjustHeap(arr, i, arr.length);}//调整堆结构+交换堆顶元素与末尾元素for (int i = arr.length - 1; i > 0; i--) {//将堆顶元素与末尾元素进行交换int temp = arr[i];arr[i] = arr[0];arr[0] = temp;//重新对堆进行调整adjustHeap(arr, 0, i);}}/*** 调整堆* @param arr 待排序列* @param parent 父节点* @param length 待排序列尾元素索引*/private static void adjustHeap(int[] arr, int parent, int length) {//将temp作为父节点int temp = arr[parent];//左孩子int lChild = 2 * parent + 1;while (lChild < length) {//右孩子int rChild = lChild + 1;// 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点if (rChild < length && arr[lChild] < arr[rChild]) {lChild++;}// 如果父结点的值已经大于孩子结点的值,则直接结束if (temp >= arr[lChild]) {break;}// 把孩子结点的值赋给父结点arr[parent] = arr[lChild];//选取孩子结点的左孩子结点,继续向下筛选parent = lChild;lChild = 2 * lChild + 1;}arr[parent] = temp;}
}

堆排序主要就是运用了堆的特性,对于堆,堆元素的下潜操作一顶要熟悉。

相关文章:

十大排序——4.堆排序

前面我们讲了堆&#xff0c;现在我们来看一下队排序。 堆排序的步骤&#xff1a; 首先将一个无序数组建立成一个大顶堆然后&#xff0c;将堆顶的元素和堆低的元素进行交换&#xff08;即将最大的元素交换的到堆底&#xff09;&#xff0c;缩小并下潜调整堆重复上一步&#xf…...

独辟蹊径”之动态切换进程代理IP

前言 项目中遇到这样一个需求&#xff0c;需要动态切换指定进程Sockets5代理IP&#xff0c;目前了解到可通过编写驱动拦截或者劫持LSP实现&#xff0c;LSP劫持不太稳定&#xff0c;驱动无疑是相对较好的解决方案&#xff0c;奈何水平不足便有了这"蹊径"。 初步尝试…...

redis漏洞修复:(CNVD-2019-21763)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、漏洞内容二、镜像准备1.确认镜像版本2.下载镜像 三、配置文件准备1.获取配置文件2.修改配置文件 四、启动redis容器五、修改iptables文件总结 前言 漏扫发…...

手刻 Deep Learning -第壹章-PyTorch入门教学-基础概念与再探线性回归

一、前言 本章会需要 微分、线性回归与矩阵的基本观念 这次我们要来做 PyTorch 的简单教学&#xff0c;我们先从简单的计算与自动导数&#xff08; auto grad / 微分 &#xff09;开始&#xff0c;使用优化器与误差计算&#xff0c;然后使用 PyTorch 做线性回归&#xff0c;还有…...

深入学习 Redis - 如何使用 Redis 作缓存?缓存更新策略?使用需要注意哪些问题(工作/重点)

目录 一、Redis 作为缓存 1.1、缓存的基本概念 1.1.1、理解 1.1.2、缓存存什么样的数据&#xff1f;二八定律 1.2、如何使用 redis 作为缓存 1.3、缓存更新策略&#xff08;redis 内存淘汰机制 / 重点&#xff09; 1.3.1、定期生成 1.3.2、实时生成 内存淘汰策略&#…...

好用的软件测试框架有哪些?测试框架的作用是什么?

软件测试框架是现代软件开发过程中至关重要的工具&#xff0c;它可以帮助开发团队更加高效地进行测试和验证工作&#xff0c;从而大大提高软件质量和用户体验。 一、好用的软件测试框架 1. Selenium&#xff1a;作为一种开源的自动化测试框架&#xff0c;Selenium具有功能强大…...

PAT 1035 插入与归并

PAT 1035 插入与归并 题目描述思路讲解代码展示 题目描述 思路讲解 分析&#xff1a;先将i指向中间序列中满足从左到右是从小到大顺序的最后一个下标&#xff0c;再将j指向从i1开始&#xff0c;第一个不满足a[j] b[j]的下标&#xff0c;如果j顺利到达了下标n&#xff0c;说明…...

K-means 聚类算法学习笔记

K-means 聚类算法 是一种无监督学习算法&#xff0c;用来将 n n n 个样本点分成 k k k 类&#xff0c;使得整个数据集的误差平方和 S S E SSE SSE 最小。在本例中&#xff0c;样本点是指平面直角坐标系上的点&#xff0c;聚类中心也是平面直角坐标系上的点&#xff0c;而每个…...

API文档搜索引擎

导航小助手 一、认识搜索引擎 二、项目目标 三、模块划分 四、创建项目 五、关于分词 六、实现索引模块 6.1 实现 Parser类 6.2 实现 Index类 6.2.1 创建 Index类 6.2.2 创建DocInfo类 6.2.3 创建 Weight类 6.2.4 实现 getDocInfo 和 getInverted方法 6.2.5 实现 …...

文案内容千篇一律,软文推广如何加深用户印象

随着互联网技术的发展&#xff0c;企业营销的方式逐渐转向软文推广&#xff0c;但是现在软文推广的内容同质化越来越严重&#xff0c;企业应该如何让自己的软文推广保持差异性&#xff0c;在用户心中留下独特的印象呢&#xff1f;下面就让媒介盒子告诉你。 一、 找出产品独特卖…...

十二、流程控制-循环

流程控制-循环 1.while循环语句★2.do...while语句★3.for循环语句 —————————————————————————————————————————————————— 1.while循环语句★ while语句也称条件判断语句&#xff0c;它的循环方式是利用一个条件来控制是否…...

五、回溯(trackback)

文章目录 一、算法定义二、经典例题&#xff08;一&#xff09;排列1.[46.全排列](https://leetcode.cn/problems/permutations/description/)&#xff08;1&#xff09;思路&#xff08;2&#xff09;代码&#xff08;3&#xff09;复杂度分析 2.[LCR 083. 全排列](https://le…...

什么是分布式锁?他解决了什么样的问题?

相信对于朋友们来说&#xff0c;锁这个东西已经非常熟悉了&#xff0c;在说分布式锁之前&#xff0c;我们来聊聊单体应用时候的本地锁&#xff0c;这个锁很多小伙伴都会用 ✔本地锁 我们在开发单体应用的时候&#xff0c;为了保证多个线程并发访问公共资源的时候&#xff0c;…...

Ubuntu 12.04增加右键命令:在终端中打开增加打开文件

Ubuntu 12.04增加右键命令&#xff1a;在终端中打开 软件中心&#xff1a;搜索nautilus-open-terminal安装 用快捷键CtrlT打开命令行输入&#xff1a; sudo apt-get install nautilus-open-terminal 重新加载文件管理器 nautilus -q 或注销再登录即要使用...

Centos 7 访问局域网windows共享文件夹

Refer: centos7 访问windows系统的共享文件夹_centos访问windows共享_三希的博客-CSDN博客 一、在CentOS中配置CIFS网络存储服务 CIFS&#xff08;Common Internet File System&#xff09;是一种在网络上共享文件的协议&#xff0c;也称为SMB&#xff08;Server Message Blo…...

GDB的TUI模式(文本界面)

2023年9月22日&#xff0c;周五晚上 今晚在看GDB的官方文档时&#xff0c;发现GDB居然有文本界面模式 TUI (Debugging with GDB) (sourceware.org) GDB开启TUI的条件 GDB的文本界面的开启条件是&#xff1a;操作系统有适当版本的curses库 The TUI mode is supported only on…...

深入了解Python和OpenCV:图像的卡通风格化

前言 当今数字时代&#xff0c;图像处理和美化已经变得非常普遍。从社交媒体到个人博客&#xff0c;人们都渴望分享独特且引人注目的图片。本文将介绍如何使用Python编程语言和OpenCV库创建令人印象深刻的卡通风格图像。卡通风格的图像具有艺术性和创意&#xff0c;它们可以用…...

【算法挨揍日记】day06——1004. 最大连续1的个数 III、1658. 将 x 减到 0 的最小操作数

1004. 最大连续1的个数 III 1004. 最大连续1的个数 III 题目描述&#xff1a; 给定一个二进制数组 nums 和一个整数 k&#xff0c;如果可以翻转最多 k 个 0 &#xff0c;则返回 数组中连续 1 的最大个数 。 解题思路&#xff1a; 首先题目要我们求出的最多翻转k个0后&#x…...

华为云HECS安装docker

1、运行安装指令 yum install docker都选择y&#xff0c;直到安装成功 2、查看是否安装成功 运行版本查看指令&#xff0c;显示docker版本&#xff0c;证明安装成功 docker --version 或者 docker -v 3、启用并运行docker 3.1启用docker 指令 systemctl enable docker …...

力扣669 补9.16

最近大三上四天有早八&#xff0c;真的是受不了了啊&#xff0c;欧嗨呦&#xff0c;早上困如狗&#xff0c;然后&#xff0c;下午困如狗&#xff0c;然后晚上困如狗&#xff0c;尤其我最近在晚上7点到10点这个时间段看力扣&#xff0c;看得我昏昏欲睡&#xff0c;不自觉就睡了1…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...