【数据结构】排序--选择排序(堆排序)
目录
一 堆排序
二 直接选择排序
一 堆排序
堆排序(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)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是 通过堆来进行选择数据。 需要注意的是排升序要建大堆,排降序建小堆。 直接选择排…...
C# 图解教程 第5版 —— 第2章 C# 和 .NET Core
文章目录 2.1 .NET 框架的背景2.2 为什么选择 .NET Core(和 Xamarin)2.3 .NET Core 的目标2.4 多平台支持2.5 快速发展和升级2.6 程序占用空间小、部署简单、版本问题少2.7 开源社区支持(*)2.8 改进的应用程序性能2.9 全新的开始&…...
数据结构 | Huffman TreeCode
构造参考: 赫夫曼树_关于huffman树,权值相同-CSDN博客 编码参考: 【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码_数据结构哈夫曼树编码-CSDN博客...
mysql拼接字符串函数
在MySQL中,可以使用CONCAT()函数来拼接字符串。CONCAT()函数接受一个或多个字符串作为参数,并将它们连接在一起。以下是CONCAT()函数的使用示例: 拼接两个字符串: 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 ,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在…...
RPA流程自动化的优势和好处
随着科技的发展,RPA机器人自动化过程已成为企业提高效率和降低人力成本的一种有效手段。RPA机器人可以模拟和执行人类操作,通过自动执行重复性和繁琐的任务,让员工能够将更多时间和精力投入到更有价值的工作中。 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…...
课题学习(七)----粘滑运动的动态算法
一、 粘滑运动的动态算法 在实际钻井过程中,钻柱会出现扭振和粘滑现象(粘滑运动–B站视频连接),但并不总是呈现均匀旋转。如下图所示,提取一段地下数据时,转盘转速保持在100 r/min,钻头转速在0-…...
python二次开发CATIA:测量曲线长度
以下代码是使用Python语言通过win32com库来控制CATIA应用程序的一个示例。主要步骤包括创建一个新的Part文件,然后在其中创建一个新的几何图形集,并在这个集合中创建一个样条线。这个样条线是通过一组给定的坐标点来创建的,这些点被添加到集合…...
从零开始学习调用百度地图网页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、先进先出调度器(FIFO)2、容量调度器(Capacity Scheduler)3、公平调度器(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的问题,模板解析后,switch:和第一个case:之间不能有有输出的,一个空格也不行,所以第一个要紧跟着 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,组成高速网络通信系统。该IP上传、下传数据B…...
Python与数据库存储
Python与数据库存储的最佳实践包括以下几个方面的内容: 连接数据库:使用合适的数据库连接库,如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…...
软件测试学习(四)自动测试和测试工具、缺陷轰炸、外包测试、计划测试工作、编写和跟踪测试用例
目录 自动测试和测试工具 工具和自动化的好处 测试工具 查看器和监视器 驱动程序 桩 压力和负载工具 干扰注入器和噪声发生器 分析工具 软件测试自动化 宏录制和回放 可编程的宏 完全可编程的自动测试工具 随机测试:猴子和大猩猩 使用测试工具和自动…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
