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

选择排序和快速排序(1)

目录

选择排序

基本思想

选择排序的实现

图片实现

代码实现

快速排序

基本思想

快速排序的实现

图片实现

 代码实现


选择排序

基本思想

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

选择排序的实现

图片实现

如图,是一组数据。让4为起始位置,从2开始遍历到8,找到最小的那个数字 1(必须要小于4),然后交换 4和 1。然后再从2开始,直到全部遍历完。

代码实现

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;int min = begin;while (begin < end){for (int i = begin + 1;i <= end;++i){if (a[i] < a[min]){min = i;}}Swap(&a[begin], &a[min]);++begin;min = begin;}
}

如果同时把最小的放在起始位置,最大的放到末尾位置,我们就能得到这个代码

代码如下:

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, 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[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

理解一下这个代码,会比较能理解下面所讲的快速排序了。

快速排序

基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,基本思想是:任取待排序元素序列中的某元素作为基准值,按照该排序码将排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排序完成。

快速排序的实现

图片实现

 代码实现

代码如下:

void QuickSort(int* a, int begin,int end)
{if (begin >= end)return;//注意一下int left = begin, right = end;int keyi = begin;while (left < right){//右边,找到比a[keyi]小的,然后放到左边//注意条件是<=while (left < right && a[keyi] <= a[right]){--right;}//左边,找到比a[keyi]大的,然后放到右边//注意条件是>=while (left < right && a[keyi] >= a[left]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort(a, begin, keyi - 1);QuicktSort(a, keyi+1, end);
}

这个快速排序是Hoare版本的快速排序,要注意的事情非常多,一不小心就会弄错。

比如while循环的条件,还有交换,以及keyi。

下一篇文章会介绍改进版本的快速排序。

相关文章:

选择排序和快速排序(1)

目录 选择排序 基本思想 选择排序的实现 图片实现 代码实现 快速排序 基本思想 快速排序的实现 图片实现 代码实现 选择排序 基本思想 每一次从待排序的数据元素中选出最小&#xff08;最大&#xff09;的元素&#xff0c;存放在序列的起始位置&#xff0c;直到全部…...

得物面试:Redis用哈希槽,而不是一致性哈希,为什么?

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50)中&#xff0c;最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格&#xff0c;遇到很多很重要的面试题&#xff1a; Redis为何用哈希槽而不用一致性哈希&#xff1f; 最近…...

matlab发送串口数据,并进行串口数据头的添加,我们来看下pwm解析后并通过串口输出的效果

uintt16位的话会在上面前面加上00&#xff0c;16位的话一定是两个字节&#xff0c;一共16位的数据 如果是unint8的话就不会&#xff0c; 注意这里给的是13&#xff0c;但是现实的00 0D&#xff0c;这是大小端的问题&#xff0c;在matlanb里设置&#xff0c;我们就默认用这个模式…...

二分、快排、堆排与双指针

二分 int Binary_Search(vector<int> A,int key){int nA.size();int low0,highn-1,mid;while(low<high){mid(lowhigh)/2;if(A[mid]key)return mid;else if(A[mid]>key)highmid-1;elselowmid1; }return -1; }折半插入排序 ——找到第一个 ≥ \ge ≥tem的元素 voi…...

微信小程序步数返还的时间戳为什么返回的全是1970?

微信小程序步数返还的时间戳为什么返回的全是1970&#xff1f; 将返回的时间 乘以 1000 再 new Date() 转化就对了 微信返回的是秒S单位的&#xff0c;我们要转化为毫秒ms单位&#xff0c;才能进行格式化日期。 微信给我们下了个坑&#xff0c; 参考&#xff1a; https://d…...

Python函数——函数介绍

一、引言 在Python编程中&#xff0c;函数是构建高效代码的关键。通过创建可重用的代码块&#xff0c;我们可以使程序更加清晰、易读且易于维护。在本文中&#xff0c;我们将深入了解Python函数的基本概念及其特性。 二、Python函数的基本概念 函数是一段具有特定功能的代码块…...

【Linux系统化学习】文件重定向

目录 文件内核对象 文件描述符的分配规则 重定向 重定向的概念 dup2系统调用 输出重定向 追加重定向 输入重定向 stderr解析 重定向到同一个文件中 分离常规输出和错输出 文件内核对象 上篇文章中我们介绍到了操作系统中的文件&#xff0c;操作系统为了方…...

防火墙工作模式详解

防火墙工作模式是指防火墙在网络中的工作方式和策略。常见的防火墙工作模式包括以下几种&#xff1a; 1. 包过滤工作模式&#xff1a;根据事先确定的规则集合&#xff0c;对进出网络的网络包进行过滤和检查。根据规则&#xff0c;防火墙可以允许或阻止特定的网络流量。 2. 代…...

CCF编程能力等级认证GESP—C++6级—20231209

CCF编程能力等级认证GESP—C6级—20231209 单选题&#xff08;每题 2 分&#xff0c;共 30 分&#xff09;判断题&#xff08;每题 2 分&#xff0c;共 20 分&#xff09;编程题 (每题 25 分&#xff0c;共 50 分)闯关游戏工作沟通 答案及解析单选题判断题编程题1编程题2 单选题…...

ES6 ~ ES11 学习笔记

课程地址 ES6 let let 不能重复声明变量&#xff08;var 可以&#xff09; let a; let b, c, d; let e 100; let f 521, g "atguigu", h [];let 具有块级作用域&#xff0c;内层变量外层无法访问 let 不存在变量提升&#xff08;运行前收集变量和函数&#…...

001 - Hugo, 创建一个网站

001 - Hugo, 创建一个网站安装hugoWindows系统Macos Hugo博客搭建初始化博客主题安装配置博客各个页面开始创作创建 GitHub Page 仓库本地调试和预览发布内容 教程及鸣谢文字教程视频教程 001 - Hugo, 创建一个网站 这篇文章假设你已经&#xff1a; 了解基本的终端命令行知识&…...

前端开发:Vue框架与前端部署

Vue Vue是一套前端框架&#xff0c;免除原生)avaScript中的DOM操作&#xff0c;简化书写。是基于MVVM(Model–View-ViewModel)思想&#xff0c;实现数据的双向绑定&#xff0c;将编程的关注点放在数据上。简单来说&#xff0c;就是数据变化的时候, 页面会自动刷新, 页面变化的时…...

【leetcode】深搜、暴搜、回溯、剪枝(C++)3

深搜、暴搜、回溯、剪枝&#xff08;C&#xff09;3 一、解数独1、题目描述2、代码3、解析 二、单词搜索1、题目描述2、代码3、解析 三、黄金矿工1、题目描述2、代码3、解析 四、不同路径III1、题目描述2、代码3、解析 一、解数独 1、题目描述 leetcode链接 2、代码 class…...

社区养老|社区养老服务系统|基于springboot社区养老服务系统设计与实现(源码+数据库+文档)

社区养老服务系统目录 目录 基于springboot社区养老服务系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员部分功能 &#xff08;1&#xff09; 用户管理 &#xff08;2&#xff09;服务种类管理 &#xff08;3&#xff09;社区服务管理 &#xff08…...

云计算基础-存储虚拟化(深信服aSAN分布式存储)

什么是存储虚拟化 分布式存储是利用虚拟化技术 “池化”集群存储卷内通用X86服务器中的本地硬盘&#xff0c;实现服务器存储资源的统一整合、管理及调度&#xff0c;最终向上层提供NFS、ISCSI存储接口&#xff0c;供虚拟机根据自身的存储需求自由分配使用资源池中的存储空间。…...

数学实验第三版(主编:李继成 赵小艳)课后练习答案(十二)(3)

实验十二&#xff1a;微分方程模型 练习三 1.分别用数值解命令ode23t和ode45 计算示例3中微分方程的数值解,同用命令ode23 算得的数值解以及解析解比较,哪种方法精度较高?你用什么方法比较它们之间的精度? clc;clear; f(x,y)2*yx2; figure(1) [x,y]ode23t(f,[1,2],1); plo…...

CSS Transition:为网页元素增添优雅过渡效果

随着互联网的发展&#xff0c;网页的视觉效果和用户体验变得尤为重要。CSS Transition作为一种能够让网页元素在状态改变时呈现平滑过渡效果的工具&#xff0c;受到了广大前端开发者的青睐。本文将详细介绍CSS Transition的基本概念、使用方法以及常见应用&#xff0c;帮助读者…...

JDK 17 新特性 (一)

既然 Springboot 3.0 强制使用 JDK 17 那就看看 JDK17 有哪些新特性吧 参考链接 介绍一下 新特性的历史渊源 JDK 17是Java Development Kit&#xff08;JDK&#xff09;的一个版本&#xff0c;它是Java编程语言的一种实现。JDK 17于2021年9月14日发布&#xff0c;并作为Java …...

杨中科 ASP.NET DI综合案例

综合案例1 需求说明 1、目的:演示DI的能力; 2、有配置服务、日志服务&#xff0c;然后再开发一个邮件发送器服务。可以通过配置服务来从文件、环境变量、数据库等地方读取配置&#xff0c;可以通过日志服务来将程序运行过程中的日志信息写入文件、控制台、数据库等。 3、说明…...

蓝桥杯嵌入式第12届真题(完成) STM32G431

蓝桥杯嵌入式第12届真题(完成) STM32G431 题目 程序 main.c /* USER CODE BEGIN Header */ /********************************************************************************* file : main.c* brief : Main program body**************************…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...