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

【数据结构】排序--选择排序(堆排序)

目录

一 堆排序

二 直接选择排序


一 堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是 通过堆来进行选择数据。

需要注意的是排升序要建大堆,排降序建小堆。

直接选择排序的特性总结:

1. 堆排序使用堆来选数,效率就高了很多。

2. 时间复杂度:O(N * logN)

3. 空间复杂度:O(1)

4. 稳定性:不稳定

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{//向下调整建堆//O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//堆排序//O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}int main()
{int arr[] = { 2, 3, 5, 7, 4, 6, 8};//InsertSort(arr, sizeof(arr) / sizeof(int));//排升序//InsertSort(arr, sizeof(arr) / sizeof(int));//排升序HeapSort(arr, sizeof(arr) / sizeof(int));//排升序for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("%d ", arr[i]);}
}

 

 

我们可以算算向下建堆的时间复杂度

 

 二 直接选择排序

直接选择排序的特性总结:

1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用

2. 时间复杂度:O(N^2)

3. 空间复杂度:O(1)

4. 稳定性:不稳定

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[mini], &a[begin]);//检查maxi是否被换走了if (maxi == begin){maxi = mini;}Swap(&a[maxi], &a[end]);begin++;end--;}
}

本节的重点是堆排序, 对二叉树的顺序结构基础要求很高, 大家如果基础不好或者不太理解,可以看看我二叉树的博客. 

继续加油!

相关文章:

【数据结构】排序--选择排序(堆排序)

目录 一 堆排序 二 直接选择排序 一 堆排序 堆排序(Heapsort)是指利用堆积树&#xff08;堆&#xff09;这种数据结构所设计的一种排序算法&#xff0c;它是选择排序的一种。它是 通过堆来进行选择数据。 需要注意的是排升序要建大堆&#xff0c;排降序建小堆。 直接选择排…...

C# 图解教程 第5版 —— 第2章 C# 和 .NET Core

文章目录 2.1 .NET 框架的背景2.2 为什么选择 .NET Core&#xff08;和 Xamarin&#xff09;2.3 .NET Core 的目标2.4 多平台支持2.5 快速发展和升级2.6 程序占用空间小、部署简单、版本问题少2.7 开源社区支持&#xff08;*&#xff09;2.8 改进的应用程序性能2.9 全新的开始&…...

数据结构 | Huffman TreeCode

构造参考&#xff1a; 赫夫曼树_关于huffman树,权值相同-CSDN博客 编码参考&#xff1a; 【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码_数据结构哈夫曼树编码-CSDN博客...

mysql拼接字符串函数

在MySQL中&#xff0c;可以使用CONCAT()函数来拼接字符串。CONCAT()函数接受一个或多个字符串作为参数&#xff0c;并将它们连接在一起。以下是CONCAT()函数的使用示例&#xff1a; 拼接两个字符串&#xff1a; SELECT CONCAT(Hello, , World); -- 输出: Hello World 拼接列中…...

python基础(5):深入理解 python 中的赋值、引用、拷贝、作用域

python基础(5):深入理解 python 中的赋值、引用、拷贝、作用域 目录 python基础(5):深入理解 python 中的赋值、引用、拷贝、作用域 1、先来看个问题吧: 2、引用 VS 拷贝: 3、增强赋值以及共享引用:...

《动手学深度学习 Pytorch版》 8.6 循环神经网络的简洁实现

import torch from torch import nn from torch.nn import functional as F from d2l import torch as d2lbatch_size, num_steps 32, 35 train_iter, vocab d2l.load_data_time_machine(batch_size, num_steps)8.6.1 定义模型 num_hiddens 256 rnn_layer nn.RNN(len(voca…...

leetcode做题笔记173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator &#xff0c;表示一个按中序遍历二叉搜索树&#xff08;BST&#xff09;的迭代器&#xff1a; BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在…...

RPA流程自动化的优势和好处

随着科技的发展&#xff0c;RPA机器人自动化过程已成为企业提高效率和降低人力成本的一种有效手段。RPA机器人可以模拟和执行人类操作&#xff0c;通过自动执行重复性和繁琐的任务&#xff0c;让员工能够将更多时间和精力投入到更有价值的工作中。 RPA(Robotic Process Automa…...

搭建 Hadoop 生态集群大数据监控告警平台

目录 一、部署 prometheus 环境 1.1 下载安装包 1.2 解压安装 1.3 修改配置文件 1.3.1 hadoop-env.sh 1.3.2 prometheus_config.yml 1.3.3 zkServer.sh 1.3.4 prometheus_zookeeper.yaml 1.3.5 alertmanager.yml 1.3.6 prometheus.yml 1.3.7 config.yml 1.3.8 t…...

课题学习(七)----粘滑运动的动态算法

一、 粘滑运动的动态算法 在实际钻井过程中&#xff0c;钻柱会出现扭振和粘滑现象&#xff08;粘滑运动–B站视频连接&#xff09;&#xff0c;但并不总是呈现均匀旋转。如下图所示&#xff0c;提取一段地下数据时&#xff0c;转盘转速保持在100 r/min&#xff0c;钻头转速在0-…...

python二次开发CATIA:测量曲线长度

以下代码是使用Python语言通过win32com库来控制CATIA应用程序的一个示例。主要步骤包括创建一个新的Part文件&#xff0c;然后在其中创建一个新的几何图形集&#xff0c;并在这个集合中创建一个样条线。这个样条线是通过一组给定的坐标点来创建的&#xff0c;这些点被添加到集合…...

从零开始学习调用百度地图网页API:二、初始化地图,鼠标交互创建信息窗口

目录 代码结构headbodyscript 调试 代码 <!DOCTYPE html> <html> <head><meta http-equiv"Content-Type" content"text/html; charsetutf-8" /><meta name"viewport" content"initial-scale1.0, user-scalable…...

Yarn基础入门

文章目录 一、Yarn资源调度器1、架构2、Yarn工作机制3、HDFS、YARN、MR关系4、作业提交之HDFS&MapReduce 二、Yarn调度器和调度算法1、先进先出调度器&#xff08;FIFO&#xff09;2、容量调度器&#xff08;Capacity Scheduler&#xff09;3、公平调度器&#xff08;Fair …...

element picker 时间控件,指定区间和指定月份置灰

直接上代码 <el-date-pickerv-model"fillingList.declareDate"type"month":disabled"isDisplayName"placeholder"选择填报时间"value-format"yyyy-MM":picker-options"pickerOptions"change"declareDate…...

thinkphp6

unexpected , expecting case (T_CASE) or default (T_DEFAULT) or } 在模板中应用{switch}{/switch}标签,报错,其实是switch的问题&#xff0c;模板解析后&#xff0c;switch:和第一个case:之间不能有有输出的&#xff0c;一个空格也不行&#xff0c;所以第一个要紧跟着 Thi…...

Android 13.0 USB鼠标右键改成返回键的功能实现

1.概述 在13.0设备定制化开发中,产品有好几个usb口,用来可以连接外设,所以USB鼠标通过usb口来控制设备也是常见的问题,在window系统中,鼠标右键是返回键的功能,可是android原生的系统 鼠标右键不是返回键根据产品开发需要鼠标修改成右键就需要跟代码, 2.USB鼠标右键改…...

超低延时 TCP/UDP IP核

实现以太网协议集当中的ARP、ICMP、UDP以及TCP协议 一、概述 TCP_IP核是公司自主开发的使用FPGA逻辑搭建的用于10G以太网通信IP。该IP能够实现以太网协议集当中的ARP、ICMP、UDP以及TCP协议。支持连接10G/25G以太网PHY&#xff0c;组成高速网络通信系统。该IP上传、下传数据B…...

Python与数据库存储

Python与数据库存储的最佳实践包括以下几个方面的内容&#xff1a; 连接数据库&#xff1a;使用合适的数据库连接库&#xff0c;如sqlite3、psycopg2、pymysql等来连接数据库。创建连接对象并通过该对象获取游标。 import sqlite3# 连接SQLite数据库 conn sqlite3.connect(sam…...

RN操作SQLite数据库的包(sqlite-helper.js)及其使用

先安装 yarn add react-native-sqlite-storagesqlite-helper.js工具包的具体代码 "use strict";var _interopRequireDefaultrequire("babel/runtime/helpers/interopRequireDefault");Object.defineProperty(exports,"__esModule",{value:true…...

软件测试学习(四)自动测试和测试工具、缺陷轰炸、外包测试、计划测试工作、编写和跟踪测试用例

目录 自动测试和测试工具 工具和自动化的好处 测试工具 查看器和监视器 驱动程序 桩 压力和负载工具 干扰注入器和噪声发生器 分析工具 软件测试自动化 宏录制和回放 可编程的宏 完全可编程的自动测试工具 随机测试&#xff1a;猴子和大猩猩 使用测试工具和自动…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...