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

常见排序算法之选择排序

目录

一、选择排序

1.1 什么是选择排序?

1.2 思路

1.2.1 思路一

1.2.2 优化思路

1.3 C语言源码

1.3.1 思路一

1.3.2 优化思路

二、堆排序

2.1 调整算法

2.1.2 向上调整算法

2.1.3 向下调整算法

2.2 建堆排序


一、选择排序

1.1 什么是选择排序?

选择排序是一种简单直观的排序算法。它的基本思想是从未排序的数据中选择最小(或最大)的元素,放到已排序数据的末尾,同时将该元素从未排序部分删除,直到所有元素都排序完成。

具体操作为,首先找到未排序部分的最小元素,并与未排序部分的第一个元素交换位置,这样就完成了一次选择。然后,将接下来未排序部分的第一个元素视为最小,找到最小元素并与未排序部分的第一个元素交换位置,以此类推,直到所有元素都排序完成。

选择排序的时间复杂度为O(n^2),是一种不稳定的排序算法。虽然它的效率相对较低,但由于其简单易实现,可以用于排序小规模的数据集合。然而对于大规模数据集合,选择排序通常不是一个最佳的选择。

1.2 思路

1.2.1 思路一

  1. 遍历第一趟数组,找出数组的最小值,与第一个数据交换
  2. 遍历第二趟数组,继续找出最小值,与第二个数据交换
  3. 重复上述动作

1.2.2 优化思路

  1. 一趟遍历找到最大和最小的元素,分别把他们放到数组的两端
  2. 缩小区间最大最小值包含的区间,找到次大,次小的元素
  3. 以此类推,直到头尾下标重合

该思路可能存在的问题:当maxi的位置与begin重合,则begin先与mini的位置交换,此时max位置的最大值被交换走,导致endmax交换的数值是错误的(图解见下)

1.3 C语言源码

1.3.1 思路一

//交换两个数据
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
//选择排序
void SelectSort(int* arr, int n)
{int i = 0;for (i = 0; i < n-1; i++){int min = i;for (int j = i+1; j < n; j++){if (arr[j] < arr[min]){min = j;}}Swap(&arr[i], &arr[min]);}
}

1.3.2 优化思路

//交换两个元素
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//插入排序
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;//在区间中找出最小的数和最大的数for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}//最小的数与首交换Swap(&a[begin], &a[mini]);//特殊情况修正if (begin == maxi)				{maxi = mini;}//最大的数与尾交换Swap(&a[end], &a[maxi]);begin++;end--;}
}

二、堆排序

2.1 调整算法

详细图解请见:二叉树的顺序实现-堆-CSDN博客

2.1.2 向上调整算法

void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

2.1.3 向下调整算法

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;}}
}

2.2 建堆排序

请点击:堆排序与TopK问题详解-CSDN博客

相关文章:

常见排序算法之选择排序

目录 一、选择排序 1.1 什么是选择排序&#xff1f; 1.2 思路 1.2.1 思路一 1.2.2 优化思路 1.3 C语言源码 1.3.1 思路一 1.3.2 优化思路 二、堆排序 2.1 调整算法 2.1.2 向上调整算法 2.1.3 向下调整算法 2.2 建堆排序 一、选择排序 1.1 什么是选择排序&#xf…...

Redis 事件机制 - AE 抽象层

Redis 服务器是一个事件驱动程序&#xff0c;它主要处理如下两种事件&#xff1a; 文件事件&#xff1a;利用 I/O 复用机制&#xff0c;监听 Socket 等文件描述符上发生的事件。这类事件主要由客户端&#xff08;或其他Redis 服务器&#xff09;发送网络请求触发。时间事件&am…...

Java | Leetcode Java题解之第118题杨辉三角

题目&#xff1a; 题解&#xff1a; class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret new ArrayList<List<Integer>>();for (int i 0; i < numRows; i) {List<Integer> row new…...

DNS 解析过程

文章目录 简介特点查询方式⚡️1. 浏览器缓存2. 系统缓存&#xff08;hosts文件&#xff09;3. 路由器缓存4. 本地域名服务器5. 根域名服务器6. 顶级域名服务器7. 权限域名服务器8. 本地域名服务器缓存并返回9. 操作系统缓存并返回10. 浏览器缓存并访问流程图 总结 简介 DNS&a…...

Golang | Leetcode Golang题解之第118题杨辉三角

题目&#xff1a; 题解&#xff1a; func generate(numRows int) [][]int {ans : make([][]int, numRows)for i : range ans {ans[i] make([]int, i1)ans[i][0] 1ans[i][i] 1for j : 1; j < i; j {ans[i][j] ans[i-1][j] ans[i-1][j-1]}}return ans }...

操作系统实验——线程与进程

如果代码或文章中&#xff0c;有什么错误或疑惑&#xff0c;欢迎交流沟通哦~ ## 进程与线程的区别 1. **各自定义**&#xff1a; 进程是操作系统进行资源分配和调度的一个独立单位&#xff0c;具有一定独立功能的程序关于某个数据集合的依次运行活动。 线程被称为轻量级的进程…...

最强端侧多模态模型MiniCPM-V 2.5,8B 参数,性能超越 GPT-4V 和 Gemini Pro

前言 近年来&#xff0c;人工智能领域掀起了一股大模型热潮&#xff0c;然而大模型的巨大参数量级和高昂的算力需求&#xff0c;限制了其在端侧设备上的应用。为了打破这一局限&#xff0c;面壁智能推出了 MiniCPM 模型家族&#xff0c;致力于打造高性能、低参数量的端侧模型。…...

Spring Boot中如何查询PGSQL分表后的数据

数据库用的pgsql&#xff0c;在表数据超过100w条的时候执行定时任务进行了分表&#xff0c;分表后表名命名为原的表名后面拼接时间&#xff0c;如原表名是card_device_trajectory_info&#xff0c;分表后拼接时间后得到card_device_trajectory_info_20240503&#xff0c;然后分…...

如何学习一个新技能

1. 提出想法 2.找到学习方法&#xff0c;学习路径 3.开始学 参考视频&#xff1a;如何成为超速学习者&#xff1f;快速学会任何新技能&#xff01;_哔哩哔哩_bilibili...

sklearn之logistic回归

文章目录 logistic回归logit logistic回归 logistic regression被称之为logistic回归&#xff0c;对于logistic这个单词来说&#xff0c;他本身的翻译其实不太容易&#xff0c;比较有名的译法是对数几率回归&#xff0c;我也认为这种译法是比较合适的&#xff0c;虽然并非logi…...

Warning: Each child in a list should have a unique “key“ prop.

问题描述&#xff1a; 使用ProTable的时候&#xff0c;报错如下 原因分析&#xff1a; 根据报错内容可以分析出&#xff0c;表格数据缺少唯一key&#xff0c; <PaginationTablecolumns{columns}pagination{{pageSize: 10,current: 1,showSizeChanger: true,showQuickJum…...

JavaSE:StringBuilder和StringBuffer类

1、引言 在上一篇文章中&#xff0c;我们理解了字符串的常用方法&#xff0c;细心的同学大概已经发现&#xff0c;不管是将字符串中的字符转变为大写或小写&#xff0c;或是完成字符串的替换&#xff0c;又或是去除空白字符等等&#xff0c;只要涉及到字符串的修改&#xff0c…...

C语言在线编程网站:探索编程的奥秘与深度

C语言在线编程网站&#xff1a;探索编程的奥秘与深度 在数字世界的浩瀚海洋中&#xff0c;编程已成为连接现实与虚拟的桥梁。而C语言&#xff0c;作为编程领域的经典之作&#xff0c;其深度与广度令无数探索者着迷。为了满足广大编程爱好者的需求&#xff0c;C语言在线编程网站…...

Android 之广播监听网络变化

网络状态变化监听帮助类 NetBroadcastReceiverHelper public class NetBroadcastReceiverHelper {private static final String TAG "NetBroadcastReceiverHelper";private static final String NET_CHANGE_ACTION "android.net.conn.CONNECTIVITY_CHANGE&qu…...

Hono 框架使用经验谈

Hono&#x1f525;是一个小型、快速并开源的 Serverless Web 框架&#xff0c;用 TypeScript 写就。它适用于任何JavaScript运行时&#xff1a;Cloudflare Workers&#xff0c;Fastly ComputeEdge&#xff0c;Deno&#xff0c;Bun&#xff0c;Vercel&#xff0c;Netlify&#x…...

mac 下配置mysql的全局环境变量

前言 如果你还没有安装mysql&#xff0c;请参考这篇文章手把手教你MAC本地数据库的安装与使用&#xff1a;mysql python (pymysql)【一】 - 知乎 正文 1.打开终端&#xff0c;输入命令”echo $SHELL“,显示当前的shell ⚠️本人使用的终端shell是zsh&#xff0c;如果你使用…...

小红书云原生 Kafka 技术剖析:分层存储与弹性伸缩

面对 Kafka 规模快速增长带来的成本、效率和稳定性挑战时&#xff0c;小红书大数据存储团队采取云原生架构实践&#xff1a;通过引入冷热数据分层存储、容器化技术以及自研的负载均衡服务「Balance Control」&#xff0c;成功实现了集群存储成本的显著降低、分钟级的集群弹性迁…...

Python实现解码二进制数据以匹配给定的C++结构体

要在Python中实现解码二进制数据以匹配给定的C结构体Ytest&#xff0c;你需要了解每个字段在结构体中的偏移量&#xff08;由于结构体内存对齐&#xff0c;这些偏移量可能与字段的顺序和大小不完全对应&#xff09;。不过&#xff0c;在没有指定内存对齐的情况下&#xff0c;我…...

实施阶段(2024年5月)

【项目活动1】斐波拉契数列第n项的值&#xff1f; 数学思想&#xff1a;第一项和第二项的值都为1&#xff0c;从第三项开始值为前两项的和。 方法一&#xff1a;迭代 迭代变量&#xff1a;f1和f2 迭代表达式&#xff1a;f1,f2f2,f1f2 计数器&#xff1a;i 迭代表达式运算…...

(delphi11最新学习资料) Object Pascal 学习笔记---第13章第3节 (弱引用是系统托管的 )

13.4.2 弱引用是系统托管的 ​ 弱引用的托管是一个非常重要的内容。换句话说&#xff0c;系统会在内存中保存一个弱引用列表&#xff0c;当对象被销毁时&#xff0c;系统会检查是否有任何弱引用指向该对象&#xff0c;如果有&#xff0c;系统会将实际引用赋值为 nil&#xff0…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

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* …...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...