当前位置: 首页 > 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的语法…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...