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

八大排序——选择排序/堆排序

news 来源：原创 2025/7/6 2:26:11

八大排序——选择排序/堆排序

一、选择排序

二、堆排序

2.1 大顶堆（升序）

2.1.1 步骤

2.1.2 代码实现

2.2 小顶堆（降序）

一、选择排序

每一趟从待排序序列中找到其最小值，然后和待排序序列的第一个值进行交换，则此时这个值变有序，待排序序列个数-1，继续下一趟，直到待排序序列个数为1时结束

void Select_Sort(int arr[], int len)
{for (int i = 0; i < len - 1; i++){int min = i;for (int j = i; j < len; j++)//找最小值 用min保存下标{if (arr[j] < arr[min])//j指向的值比min的值更小，则min更新一下，更新为j{min = j;}}if (min != i){int tmp = arr[min];arr[min] = arr[i];arr[i] = tmp;}}
}

时间复杂度O(n^2) 循环嵌套都是

空间复杂度O(1)

稳定性：不稳定

二、堆排序

树：n个节点组成的有限集合，树有且只有一个根节点“ROOT”，树除了根节点之外剩余节点还可以组成m个互不相交的有限集合（称为子树）

二叉树：每个节点最多有俩个孩子节点

满二叉树：一颗二叉树层数为k，且有2^-1和节点。换句话说，一个二叉树，有多少层就把多少层摆满。

完全二叉树：相较于满二叉树，可以少节点，但只能从最后一层，从右至左少节点

节点的度：孩子的个数

叶子节点：度为0的节点，最外的一层

非叶子节点：度不为0的节点

2.1 大顶堆（升序）

是一个特殊的完全二叉树，父节点都大于等于孩子节点

2.1.1 步骤

每次确定一个最大值，然后和最后一个位置进行交换

为什么每次都能获取一个最大值，因为堆排序的核心时维护一个大顶堆（默认升序），大顶堆的唯一特征是根节点是所有值中的最大值

1. 首先将给的数组，想象成一个完全二叉树

2.将这颗完全二叉树调整成一个大顶堆（首次调整是由内到外的调整：从最后一个非叶子节点作为根节点的分支二叉树开始调整，然后从右至左，从下之上）

3. 将这课大顶堆的根节点（最大的值）和其最后一个节点进行交换，交换完成后，让此时这个节点断开连接，不参与后续排序、

4. 此时这颗完全二叉树不再是大顶堆，我们需要重新调整为大顶堆，不需要从上面那样从内到外调整，只需要调整最外层的

5. 反复执行三四直到大顶堆中剩下一个节点

2.1.2 代码实现

#include <stdio.h>// 函数声明，用于显示排序后的数组
void Show(int arr[], int len);// 调整堆的函数，使其满足大顶堆的性质
void Adjust_Heap(int arr[], int start, int end) {int tmp = arr[start]; // 保存当前起始节点的值int max_child = start * 2 + 1; // 初始化最大子节点索引为起始节点的左子节点// 循环，直到最后一个节点for (; max_child <= end; max_child = start * 2 + 1) {// 如果右子节点存在且大于左子节点，则更新最大子节点索引if (max_child + 1 <= end && arr[max_child + 1] > arr[max_child]) {max_child++;}// 如果最大子节点的值大于保存的起始节点的值，则交换它们if (arr[max_child] > tmp) {arr[start] = arr[max_child];start = max_child; // 更新起始节点为最大子节点} else {break; // 如果最大子节点的值不大于保存的起始节点的值，则结束循环}}arr[start] = tmp; // 将保存的起始节点的值放到最终位置
}// 堆排序函数
void Heap_Sort(int arr[], int len) {// 构建大顶堆for (int i = ((len - 1) - 1) / 2; i >= 0; i--) {Adjust_Heap(arr, i, len - 1); // 从最后一个非叶子节点开始调整堆}// 排序过程for (int i = 0; i < len - 1; i++) {int tmp = arr[0]; // 保存堆顶元素arr[0] = arr[len - 1 - i]; // 将堆顶元素与未排序部分的最后一个元素交换arr[len - 1 - i] = tmp; // 完成交换Adjust_Heap(arr, 0, len - 1 - i - 1); // 重新调整堆}
}// 主函数
int main() {int arr[] = { 10000, 20000, -100, 195, 71, 89, 42, 8, 902, 894, 194, 80, 194, 128, 90, 18, 490, 18, 409, 180, 95, 12, 489, 404 };int len = sizeof(arr) / sizeof(arr[0]); // 计算数组长度Heap_Sort(arr, len); // 调用堆排序函数对数组进行排序Show(arr, len); // 显示排序后的数组return 0;
}// 显示数组的函数
void Show(int arr[], int len) {for (int i = 0; i < len; i++) {printf("%d ", arr[i]); // 打印数组元素}printf("\n"); // 打印换行符
}

2.2 小顶堆（降序）

是一个特殊的完全二叉树，父节点都小于等于孩子节点。

八大排序——选择排序/堆排序

八大排序——选择排序/堆排序目录一、选择排序二、堆排序 2.1 大顶堆（升序） 2.1.1 步骤 2.1.2 代码实现 2.2 小顶堆（降序） 一、选择排序每一趟从待排序序列中找到其最小值，然后和待排序序列的第一个值进行交换&am…...

编程日记 2025/7/6 2:26:11

【KWDB 创作者计划】_深度学习篇---归一化反归一化

文章目录前言一、归一化（Normalization）1. 定义2. 常用方法Min-Max归一化Z-Score标准化（虽常称“标准化”，但广义属归一化）小数缩放（Decimal Scaling）3. 作用4. 注意事项二、反归一化（Denormalization）1. 定义2.方法3. 应用场景三、Python示例演示四、归一化 vs. 标准…...

编程日记 2025/7/6 3:23:51

windows端远程控制ubuntu运行脚本程序并转发ubuntu端脚本输出的网页

背景对于一些只能在ubuntu上运行的脚本，并且这个脚本会在ubuntu上通过网页展示运行结果。我们希望可以使用windows远程操控ubuntu，在windows上查看网页内容。方法 start cmd.exe /k "sshpass -p passwd ssh namexxx.xxx.xxx.xxx "cd /hom…...

编程日记 2025/7/4 5:49:32

推荐系统（二十四）：Embedding层的参数是如何在模型训练过程中学习的？

近来有不少读者私信我关于嵌入层（Embedding层）参数在模型训练过程中如何学习的问题。虽然之前已经在不少文章介绍过 Embedding，但是为了读者更好地理解，笔者将通过本文详细解读嵌入层（Embedding Layer）的参…...

编程日记 2025/7/3 16:54:24

【Ubuntu】关于系统分区、挂载点、安装位置的一些基本信息

在ubuntu22及以前的版本中，最好是手动配置分区及其挂载点，通常我们会配置成3/4个分区： 引导区，交换区，根挂载点，home挂载点（有时根挂载点和home合二为一） 配置各种环境所占用的内存 …...

编程日记 2025/6/29 10:43:27

概率dp总结

概率 DP 用于解决概率问题与期望问题，建议先对概率 & 期望的内容有一定了解。一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环，如果定义的状态转移方程存在后效性问题，还需要用到高斯消元来优…...

编程日记 2025/7/5 12:13:16

深入解析：RocketMQ、RabbitMQ和Kafka的区别与使用场景

互联网大厂Java求职者面试：RocketMQ、RabbitMQ和Kafka的深入解析故事场景：严肃且专业的面试官与架构师程序员马架构在一家知名的互联网大厂，Java求职者正在接受一场严格的面试。面试官是一位经验丰富的技术专家，他将通过多轮提…...

编程日记 2025/6/28 22:31:25

探秘Transformer系列之（30）--- 投机解码

探秘Transformer系列之（30）— 投机解码文章目录探秘Transformer系列之（30）--- 投机解码0x00 概述0x01 背景1.1 问题1.2 自回归解码 0x02 定义 & 历史2.1 投机解码2.2 发展历史 0x03 Blockwise Parallel Decoding3.1 动机3.2…...

编程日记 2025/6/29 9:24:19

【CSS】层叠，优先级与继承（三）：超详细继承知识点

目录继承一、什么是继承？2.1 祖先元素2.2 默认继承/默认不继承二、可继承属性2.1 字体相关属性2.2 文本相关属性2.3 列表相关属性三、不可继承属性3.1 盒模型相关属性3.2 背景相关属性四、属性初始值4.1 根元素4.2 属性的初始值4.3 得出结论五、强制继承5.1 in…...

编程日记 2025/7/4 1:13:12

SpringBoot中6种自定义starter开发方法

在SpringBoot生态中，starter是一种特殊的依赖，它能够自动装配相关组件，简化项目配置。自定义starter的核心价值在于： • 封装复杂的配置逻辑，实现开箱即用 • 统一技术组件的使用规范，避免"轮子"泛滥 • 提高开发效率，减少重复代码方法一：基础配置类方式 …...

编程日记 2025/7/4 2:03:13

时间自动填写——电子表格公式的遗憾（DeepSeek）

now()/today()缘源来，人肉值粘胜无依。用函数抓取系统时间，人肉CTRLC“永葆青春”——直接时间数据存储。笔记模板由python脚本于2025-04-23 23:21:44创建，本篇笔记适合想要研究电子表格日期自动填写的coder翻阅。【学习的细节是欢悦的历程…...

编程日记 2025/6/28 16:36:34

AUTODL关闭了程序内存依然占满怎么办

AutoDL帮助文档关闭了程序，使用nvidia-smi查看，内存任然爆满： 执行 ps -ef | grep train | awk {print $2} | xargs kill -9...

编程日记 2025/6/29 9:24:24

Spark集群搭建之Yarn模式

1.把spark安装包复制到你存放安装包的目录下，例如我的是/opt/software cd /opt/software，进入到你存放安装包的目录然后tar -zxvf 你的spark安装包的完整名字 -C /opt/module，进行解压。例如我的spark完整名字是spark-3.1.1-bin-hadoop3.2.…...

编程日记 2025/7/4 8:28:46

CSS-跟随图片变化的背景色获取图片的主要颜色并用于背景渐变需要安装依赖 colorthief获取图片的主要颜色. 并丢给背景注意 getPalette并不是个异步方法 import styles from ./styles.less; import React, { useState } from react; import Colortheif from colorthief;cons…...

编程日记 2025/7/6 2:58:56

一,开发环境安装

环境安装选择的版本如下 Python3.7 Anaconda5.3.1 CUDA 10.0 Pycharm Anaconda安装:下载地址 CUDA 10.0安装,包下载地址...

编程日记 2025/6/29 9:25:22

局部最小实验--用最小成本确保方向正确

### **将「局部最小实验」融入「简单、专注、本分」认知框架的实践方案** 你的核心认知框架是 **「简单、专注、本分」**，而 **「局部最小实验」**（MVP思维）本质上是一种 **低成本验证、快速迭代** 的方法论。二者看似矛盾（简单…...

编程日记 2025/6/29 19:37:27

【网络应用程序设计】实验三：网络聊天室

个人博客：https://alive0103.github.io/ 代码在GitHub：https://github.com/Alive0103/XDU-CS-lab 能点个Star就更好了，欢迎来逛逛哇~❣ 主播写的刚够满足基本功能，多有不足，仅供参考，还请提PR指正&#xff…...

编程日记 2025/7/4 1:10:38

【泊松过程和指数分布】

泊松过程的均值函数与方差函数计算 1. 泊松过程的定义泊松过程是一个计数过程 { N ( t ) , t ≥ 0 } \{N(t), t \geq 0\} {N(t),t≥0}，满足以下条件： 独立增量：在不相交时间段内事件发生次数相互独立；平稳增量：在时…...

编程日记 2025/6/29 10:31:28

leetcode-排序

排序面试题 01.01. 判定字符是否唯一题目实现一个算法，确定一个字符串 s 的所有字符是否全都不同。示例 1： 输入: s "leetcode" 输出: false 示例 2： 输入: s "abc" 输出: true限制： 0 < len(s) &…...

编程日记 2025/6/29 10:45:39

Axure中继器表格：实现复杂交互设计的利器

在产品原型设计领域，Axure凭借其强大的元件库和交互功能，成为设计师们手中的得力工具。其中，中继器元件在表格设计方面展现出了独特的优势，结合动态面板等元件，能够打造出功能丰富、交互体验良好的表格原型。本文将深入…...

编程日记 2025/6/29 11:30:10

容器内部无法访问宿主机服务的原因及解决方法

容器内部无法访问宿主机服务的原因及解决方法问题原因当你在Docker容器内部尝试访问宿主机上的服务(如192.168.130.148:8000)时失败，通常有以下几种原因：网络隔离：Docker容器默认使用自己的网络命名空间，与宿主机网络隔离IP地址误解：容器内看到的宿主机IP与外部网络不…...

编程日记 2025/6/29 11:49:33

IMU---MPU6050

一、芯片概述 1. 基本定位型号：MPU6050，InvenSense（现TDK）推出的全球首款6轴MEMS运动传感器，集成3轴加速度计、3轴陀螺仪，内置温度传感器（非6轴核心功能）。定位：低成本…...

编程日记 2025/6/29 10:46:21

提高Spring Boot开发效率的实践

Spring Boot开发效率的重要性 Spring Boot 作为一个开源的 Java 框架，旨在简化新 Spring 应用和微服务的创建与开发 1。其核心特性，如自动配置、约定优于配置以及内嵌服务器，极大地降低了开发门槛，使得开发者可以更专注于业务逻辑的实现 1。在现代应用开发领域，Spring Bo…...

编程日记 2025/7/6 2:26:57

Spring Boot的优点：赋能现代Java开发的利器

Spring Boot 是基于 Spring 框架的快速开发框架，自 2014 年发布以来，凭借其简洁性、灵活性和强大的生态系统，成为 Java 后端开发的首选工具。尤其在 2025 年，随着微服务、云原生和 DevOps 的普及，Spring Boot 的优势更…...

编程日记 2025/6/29 11:21:14

Python内置函数---breakpoint()

用于在代码执行过程中动态设置断点，暂停程序并进入调试模式。 1. 基本语法与功能 breakpoint(*args, kwargs) - 参数：接受任意数量的位置参数和关键字参数，但通常无需传递（默认调用pdb.set_trace()）。 - 功能&#x…...

编程日记 2025/7/4 8:28:51

2.RabbitMQ - 入门

RabbitMQ 入门文章目录 RabbitMQ 入门一、快速入门1.1 介绍1.2 创建项目1.3 简单入门二、Work模型三、交换机3.1 Fanout3.2 Direct3.3 Topic 四、声明队列和交换机4.1 配置文件4.2 注解五、消息转换器一、快速入门 1.1 介绍官方的API较为麻烦，我们使用官方推…...

编程日记 2025/7/5 1:23:46

智能配送机器人控制系统设计

标题:智能配送机器人控制系统设计内容:1.摘要随着物流行业的快速发展，智能配送机器人的需求日益增长。本文的目的是设计一套高效、稳定的智能配送机器人控制系统。方法上，采用了先进的传感器技术、定位算法和路径规划策略，确保机器人能准确…...

编程日记 2025/6/29 9:25:15

2025.04.23华为机考第一题-100分

📌 点击直达笔试专栏 👉《大厂笔试突围》 💻 春秋招笔试突围在线OJ 👉 笔试突围OJ 01. 星空探索者问题描述 LYA是一位天文学爱好者，她拍摄了一张星空照片并将其数字化为二维亮度图。在这张图像中，每个像素点的值代表该位置的亮度。现在，LYA想要寻找特定亮度的星…...

编程日记 2025/6/29 11:35:12

MCP 基于 TypeScript 的完整示例，包含stdio、sse多种用法和调试，对于构建自己的API工具链很有用

typescript-mcp-demo 这是一个基于 Model Context Protocol (MCP) 的 TypeScript 示例项目，展示了如何创建一个简单的 MCP 服务器，包含基本的工具（tools）和资源（resources）功能。官网：https:…...

编程日记 2025/7/6 2:26:49

【计算机视觉】CV项目实战- SORT 多目标跟踪算法

SORT 多目标跟踪算法：从原理到实战的完整指南一、SORT算法核心解析1.1 算法架构1.2 关键技术组件二、实战环境搭建2.1 基础环境配置2.2 数据准备三、核心功能实战3.1 基础跟踪演示3.2 自定义检测器集成3.3 性能评估四、高级应用与优化4.1 针对遮挡场景的改进4.2…...

编程日记 2025/6/29 9:30:00

常用第三方库精讲：cached_network_image图片加载优化

常用第三方库精讲：cached_network_image图片加载优化在Flutter应用开发中，图片加载是一个非常重要的环节。合理的图片加载策略不仅能提升用户体验，还能优化应用性能。本文将深入讲解cached_network_image库的使用，以及如何通过它…...

编程日记 2025/7/6 2:26:45

xcode 16 遇到contains bitcode

问题 "id" : "xxx-xxx-xxx","status" : "409","code" : "STATE_ERROR.VALIDATION_ERROR","title" : "Validation failed","detail" : "Invalid Executable. The executable …...

编程日记 2025/7/4 23:44:18

MySQL数据库精研之旅第十期：打造高效联合查询的实战宝典（一）

专栏：MySQL数据库成长记个人主页：手握风云目录一、简介 1.1. 为什么要使用联合查询 1.2. 多表联合查询时的计算 1.3. 示例二、内连接 2.1. 语法 2.2. 示例三、外连接 4.1. 语法 4.2. 示例一、简介 1.1. 为什么要使用联合查询一次查询需…...

编程日记 2025/6/29 9:25:11

Sentinel源码—9.限流算法的实现对比二

大纲 1.漏桶算法的实现对比 (1)普通思路的漏桶算法实现 (2)节省线程的漏桶算法实现 (3)Sentinel中的漏桶算法实现 (4)Sentinel中的漏桶算法与普通漏桶算法的区别 (5)Sentinel中的漏桶算法存在的问题 2.令牌桶算法的实现对比 (1)普通思路的令牌桶算法实现 (2)节省线程的…...

编程日记 2025/6/29 11:23:30

单片机外设模块汇总与介绍

一、基础外设 GPIO（通用输入输出） 功能：数字信号输入/输出，支持推挽、开漏模式。应用：控制LED、按键检测、数字传感器接口。配置要点： 输入模式：上拉/下拉电阻配置输出模式：…...

编程日记 2025/7/5 8:36:05

git lfs下载大文件限额

起因是用 model.load_state_dict(torch.load())加载pt权重文件时，出现错误：_pickle.UnpicklingError: invalid load key, ‘v’. GPT告诉我：你的 pt 文件不是权重文件，而是模型整体保存（或根本不是 PyTorch 文件&#…...

编程日记 2025/7/6 2:55:06

第4天：Linux开发环境搭建

🧰 第4天：Linux开发环境搭建一、GCC 编译器 📌 1. 什么是 GCC？ GCC（GNU Compiler Collection）是 GNU 工程开发的编译器集合，主要支持 C、C、Fortran 等语言的编译，是 Linux 系统中…...

编程日记 2025/6/29 10:02:33

“在中国，为中国” 英飞凌汽车业务正式发布中国本土化战略

3月28日，以“夯实电动化，推进智能化，实现高质量发展”为主题的2025中国电动汽车百人会论坛在北京举办。众多中外机构与行业上下游嘉宾就全球及中国汽车电动化的发展现状、面临的挑战与机遇，以及在技术创新、市场布局、供应链协同等…...

编程日记 2025/6/29 10:48:17

【AI应用】免费代码仓构建定制版本的ComfyUI应用镜像

免费代码仓构建定制版本的ComfyUI应用镜像 1 创建代码仓1.1 注册登陆1.2 创建代码仓1.5 安装中文语言包1.4 拉取ComfyUI官方代码2 配置参数和预装插件2.1 保留插件和模型的版本控制2.2 克隆插件到代码仓2.2.1 下载插件2.2.2 把插件设置本仓库的子模块管理3 定制Docker镜像3.1 创…...

编程日记 2025/6/29 9:25:00

新市场环境下新能源汽车电流传感技术发展前瞻

新能源革命重构产业格局在全球碳中和战略驱动下，新能源汽车产业正经历结构性变革。国际清洁交通委员会（ICCT）最新报告显示，2023年全球新能源汽车渗透率突破18%，中国市场以42%的市占率持续领跑。这种产业变革正沿着&q…...

编程日记 2025/6/29 9:24:38

ctfhub-RCE

关于管道操作符 windows： 1. “|”：直接执行后面的语句。 2. “||”：如果前面的语句执行失败，则执行后面的语句，前面的语句只能为假才行。 3. “&”：两条命令都执行，如果前面的语句为假则直…...

编程日记 2025/6/29 9:24:32

SSE（Server-Sent Events）技术详解：轻量级实时通信的全能方案

一、实时通信技术演进与SSE定位 1.1 主流实时通信技术对比 #mermaid-svg-1VQcZqAOmMoxosiW {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-1VQcZqAOmMoxosiW .error-icon{fill:#552222;}#mermaid-svg-1VQcZqAOmMox…...

编程日记 2025/6/29 9:24:37

QT项目----电子相册(4)

文章目录前言一、右侧区域PicShow1.创建PicShow2.创建PicButton3.效果图qss 4.设置动画QGraphicsOpacityEffectQPropertyAnimation 5.双击左侧图片目录右侧显示图片解决缩放时卡顿的问题二、删除相册实现思路代码实现总结前言提示：这里可以添加本文要记录的大…...

编程日记 2025/7/5 23:21:43

Sentinel源码—9.限流算法的实现对比一

编程日记 2025/7/6 2:27:25

46. 全排列

题目给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。示例 1： 输入：nums [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2： 输入&#xff1a…...

编程日记 2025/6/29 9:25:01

UML 顺序图：电子图书馆管理系统的交互之道

目录一、初识 UML 顺序图二、电子图书馆管理系统顺序图解析 （一）借阅流程 （二）归还流程三、顺序图绘画四、顺序图的优势与价值五、总结 UML 顺序图是描绘系统组件交互的有力工具。顺序图直观展示消息传递顺序与对象协…...

编程日记 2025/6/29 11:25:31

前端渲染pdf文件解决方案-pdf.js

目录一、前言二、简介 1、pdf.js介绍 2、插件版本参数三、通过viewer.html实现预览（推荐） 1、介绍 2、部署【1】下载插件包【2】客户端方式【3】服务端方式（待验证） 3、使用方法【1】预览PDF文件【2】外部搜索…...

编程日记 2025/6/29 10:38:47

接口测试和功能测试详解

🍅 点击文末小卡片 ，免费获取软件测试全套资料，资料在手，涨薪更快本文主要分为两个部分： 第一部分：主要从问题出发，引入接口测试的相关内容并与前端测试进行简单对比，总结两者…...

编程日记 2025/6/29 9:24:30

LeetCode热题100--283.移动零--简单

1.题目给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。示例 1: 输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2: 输入: nums [0]…...

编程日记 2025/6/29 12:19:27

CoT 数据集如何让大模型学会「一步一步思考」？

目前，大模型的回答路径基本遵循input-output的方式，在面对复杂任务时表现不佳。反之，人类会遵循一套有条理的思维流程，逐步推理得出正确答案。这种差异促使人们深入思考：如何才能让大模型“智能涌现”，学会…...

编程日记 2025/6/29 9:24:33

一、选择排序

二、堆排序

2.1 大顶堆（升序）

2.1.1 步骤

2.1.2 代码实现

2.2 小顶堆（降序）

相关文章：