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

【海贼王的数据航海】排序——直接选择排序|堆排序

目录

1 -> 选择排序

1.1 -> 基本思想

1.2 -> 直接选择排序

1.2.1 -> 代码实现

1.3 -> 堆排序

1.3.1 -> 代码实现


1 -> 选择排序

1.1 -> 基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

1.2 -> 直接选择排序

  • 在元素集合arr[i] -- arr[n - 1]中选择关键码最大(或最小)的数据元素
  • 若它不是这组元素中的最后一个(或第一个)元素,则将它与这组元素中的最后一个(或第一个)元素交换
  • 在剩余的arr[i] -- arr[n - 2] (arr[i + 1] -- arr[n - 1]) 集合中,重复上述步骤,直到集合剩余1个元素

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

  1. 好理解,但效率不是很好,实际中很少使用
  2. 时间复杂度:O(N^{2})
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

1.2.1 -> 代码实现

#define  _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 交换
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}// 打印
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++)printf("%d ", a[i]);printf("\n");
}// 选择排序
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int maxi = begin, mini = begin;for (int i = begin; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);// 如果maxi和begin重叠,修正一下即可if (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}void TestSelectSort()
{int a[] = { 9, 2, 6, 1, 7, 3 ,0, 5, 8, 4 };PrintArray(a, sizeof(a) / sizeof(int));SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestSelectSort();return 0;
}

1.3 -> 堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。

堆排序特性总结:

  1. 堆排序用堆来选数,效率较高
  2. 时间复杂度:O(N\cdot logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

1.3.1 -> 代码实现

#define  _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 交换
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}// 打印
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++)printf("%d ", a[i]);printf("\n");
}// 堆排序
void AdjustUp(int* a, int child)
{int father = (child - 1) / 2;while (child > 0){if (a[child] > a[father]){Swap(&a[child], &a[father]);//更新下标child = father;father = (father - 1) / 2;}else{break;//一旦符合小堆了,就直接退出}}
}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)
{// 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}void TestHeapSort()
{int a[] = { 9, 2, 6, 1, 7, 3 ,0, 5, 8, 4 };PrintArray(a, sizeof(a) / sizeof(int));HeapSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestHeapSort();return 0;
}


感谢大佬们的支持!!!

互三啦!!!

相关文章:

【海贼王的数据航海】排序——直接选择排序|堆排序

目录 1 -> 选择排序 1.1 -> 基本思想 1.2 -> 直接选择排序 1.2.1 -> 代码实现 1.3 -> 堆排序 1.3.1 -> 代码实现 1 -> 选择排序 1.1 -> 基本思想 每一次从待排序的数据元素中选出最小(或最大)的一个元素&#xff0c;存放在序列的起始位置&…...

Flutter 的 switch 语句补遗

我的 App 里&#xff0c;一个消息气泡变成空白了&#xff0c;非常奇怪&#xff0c;此前一直是没问题的&#xff0c;经过调试定位我发现&#xff1a; static TextSpan _buildRootSpan(BuildContext ctx, List<LinkifyElement> parts, TextStyle? style) {List<InlineS…...

Linux动态库*.so函数名修改

在某些学习或者特殊需求的情况下要对linux下动态库*.so文件内部的函数名进行修改。 比如一个函数ADD(int a,int b);修改为Add(int a,int b); 通过这篇文章你将了解到在linux下动态库函数名寻址的规则&#xff0c;截止2024年3月linux动态库的寻址规则已经出现多种&#xff0c;这…...

adb shell 指令集

1.connect device连接设备&#xff1a; adb devices #return: List of devices attached 0123456789ABCDEF device2.连接终端 adb shell从设备拷贝文件到本地 adb pull <remote> [local] 如: adb pull /sdcard/demo.txt e:\从到本地拷贝文件到设备 adb push &…...

【电子通识】CH340C与CH340G的区别

在USB转串口电路中&#xff0c;网上买到的模块常常用的到是CH340或是CP2102。 但是CH340也有很多的版本&#xff0c;比如CH340C和CH340G&#xff0c;那么他们到底都有哪些差别。 环境特性 从规格书中可以看出环境特性CH340G是-40度到85度&#xff0c;而CH340C批号不是4开头…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的吸烟检测系统(深度学习+Python代码+PySide6界面+训练数据集)

摘要&#xff1a;本文详细说明了如何利用深度学习开发一个用于监测吸烟行为的系统&#xff0c;并分享了完整的代码实现。该系统采用了先进的YOLOv8算法&#xff0c;同时还使用YOLOv7、YOLOv6、YOLOv5算法&#xff0c;并对它们进行了性能比较&#xff0c;呈现了不同模型的性能指…...

Apache Paimon 使用之 Lookup Joins 解析

Lookup Join 是流式查询中的一种 Join&#xff0c;Join 要求一个表具有处理时间属性&#xff0c;另一个表由lookup source connector支持。 Paimon支持在主键表和附加表上进行Lookup Join。 a) 准备 创建一个Paimon表并实时更新它。 -- Create a paimon catalog CREATE CAT…...

GO语言-切片底层探索(下)

目录 切片的底层数据结构 扩容机制 总结&#xff1a; 练习验证代码 这是切片的底层探索下篇&#xff0c;上篇地址请见&#xff1a;GO语言-切片底层探索&#xff08;上&#xff09; 在上篇我们讲解了切片的两个重要实现或者说是两个特征 切片是引用类型&#xff0c;会进行…...

物理隔离条件下,如何安全高效地进行内外网文件导入导出?

内外网文件导入导出通常指的是在内部网络&#xff08;内网&#xff09;和外部网络&#xff08;外网&#xff09;之间传输文件的过程。这在企业环境中尤其常见&#xff0c;因为内部网络通常包含敏感数据&#xff0c;而外部网络&#xff08;如互联网&#xff09;则允许更广泛的访…...

代码随想录 贪心算法-难度题目-区间问题

目录 55.跳跃游戏 45.跳跃游戏|| 452.用最少数量的箭引爆气球 435.无重叠区间 763.划分字母区间 56.合并区间 55.跳跃游戏 55. 跳跃游戏 中等 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大…...

地理数据 vs. 3D数据

在表示我们周围的物理世界时&#xff0c;地理空间数据和 3D 建筑数据是两个最常见的选择。 他们在各个行业和项目中发挥着至关重要的作用。 从构建数字孪生到可视化城市景观和创建沉浸式应用程序。 尽管地理空间和 3D 建筑数据有相似之处&#xff0c;但它们不可互换。 虽然地…...

Redis删除

一、del命令 del命令是Redis提供的一个常规的删除键的命令。它的语法如下&#xff1a; DEL key [key …] 其中&#xff0c;key是要删除的键名。可以指定多个键名&#xff0c;删除多个键。如果指定的键不存在&#xff0c;则会被忽略。 del命令会直接删除指定的键以及与之相关联…...

力扣细节题:字符串中的最大奇数

奇数只要找到第一位是奇数的即可&#xff0c;不是找单个数字 //即从最低位开始&#xff0c;找到第一位为奇数的位 //然后之前的就是需要的数字char * largestOddNumber(char * num){int i strlen(num) - 1;while(i > 0){if((num[i] - 0) % 2 1)break;i--;}//先找到低位开…...

Unity PS5开发 天坑篇 之 申请开发者与硬件部署01

腾了好几天终于把PS5开发机调试部署成功, 希望能帮到国内的开发者, 主机游戏PlayStation/Nintendo Switch都是比较闭塞的&#xff0c;开发者账号是必须的。 开发环境有两个部分&#xff0c;一是DEV Kit 开发机, TEST Kit测试机两部分组成&#xff0c;二是Unity的支持库(安装后…...

十四届蓝桥杯省赛Java B组 合并区域

就是将两个矩阵进行拼接&#xff0c;两矩阵可以旋转90 180 270 度。 因为数据比较小&#xff0c;所以这基本上就是一个大的枚举模拟加搜索&#xff0c;直接暴力求解。 import java.io.*; import java.util.*;public class Main{static int n;static int N 101;static int mo…...

SpringBoot高级

1.自动配置-Condition Condition是Spring4.0后引入的条件化配置接口&#xff0c;通过实现Condition接口可以完成有条件的加载相应的Bean 进入 SpringBoot 启动类&#xff0c;点击进入 run() 可以看到这个方法是有返回值的&#xff0c;返回值为 ConfigurableApplicationConte…...

机试:偶数分解

题目描述: 代码示例: #include <bits/stdc.h> using namespace std; int main(){ // 算法思想1:遍历小于该偶数的所有素数,存入数组中,遍历数组找出两个数之和等于偶数的数int n;cout << "输入样例" << endl;cin >> n;int nums[n];int k …...

一周学会Django5 Python Web开发-Jinja3模版引擎-安装与配置

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计35条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…...

python前端开发

前端开发 快速网站开发 from flask import Flask appFlask(__name__) #创建网址/show/info 和函数index的对应关系&#xff0c; #访问网站&#xff0c;执行index()函数 app.route("/show/info") def index():return "中国联通" if __name__"__main_…...

web学习笔记(三十三)

目录 1.严格模式 1.1严格模式的概念&#xff1a; 1.2严格模式在语义上更改的地方&#xff1a; 1.3如何开启严格模式 1.4严格模式应用上的变化 2.原型链 1.严格模式 1.1严格模式的概念&#xff1a; 严格模式有点像es5向es6过渡而产生的一种模式&#xff0c;因为es6的语法…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...

aurora与pcie的数据高速传输

设备&#xff1a;zynq7100&#xff1b; 开发环境&#xff1a;window&#xff1b; vivado版本&#xff1a;2021.1&#xff1b; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程&#xff0c;pc通过pcie传输给fpga&#xff0c;fpga再通过aur…...

Java严格模式withResolverStyle解析日期错误及解决方案

在Java中使用DateTimeFormatter并启用严格模式&#xff08;ResolverStyle.STRICT&#xff09;时&#xff0c;解析日期字符串"2025-06-01"报错的根本原因是&#xff1a;模式字符串中的年份格式yyyy被解释为YearOfEra&#xff08;纪元年份&#xff09;&#xff0c;而非…...

Kaggle-Predicting Optimal Fertilizers-(多分类+xgboost+同一特征值多样性)

Predicting Optimal Fertilizers 题意&#xff1a; 给出土壤的特性&#xff0c;预测出3种最佳的肥料 数据处理&#xff1a; 1.有数字型和类别型&#xff0c;类别不能随意换成数字&#xff0c;独热编码。cat可以直接处理category类型。 2.构造一些相关土壤特性特征 3.由于la…...