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

排序算法学习记录-快速排序

快速排序

快速排序关键在于确定一个中间值,使得小于这个中间值的数在左边,大于这个中间值的数在右边。那么中间值该如何确定呢?有以下几种做法

  • 首元素,也就是arr[l]
  • 尾元素,也就是arr[r]
  • 中间元素,也就是arr[(l+r)>>1]这里是位运算,等价于arr[(l+r)/2^1]
  • 中间的一个随机元素
void Qsort(int arr[],int l,int r){if(l>=r) return;int begin = l,end = r,x = arr[(l+r)>>1];//上面是位运算,表示(l+r)/2^1while(begin<=end){while(arr[begin]<x) begin++;while(arr[end]>x) end--;if(begin<=end) swap(&arr[begin++],&arr[end--]);}Qsort(arr,l,end);Qsort(arr,begin,r);
}
//除了和x的比较不带=,其他的都带

快速排序相关变体

题目如下:
在这里插入图片描述
求第k大(小)的数,一种做法是堆排序把前k个数找出来就行,另一种就是利用快速排序的思想去做。现暂把中间的分界点称为pivot,左边的数都小于pivot,右边的数都大于pivot。那么假如左边有m个数,右边有n个数。求第k大的数。如果k<n,那么这个数肯定在右边,反之这个数肯定在左边。以此来缩小这个数所在的范围。

归并排序

归并排序的核心思想在于将两个有序的数组合并为一个全局有序的数组。

int tmp[100000];
void merge_sort(int arr[],int begin,int end){if(begin>=end) return;int mid = (begin+end)>>1;merge_sort(arr,begin,mid);merge_sort(arr,mid+1,end);int l_begin = begin,r_begin = mid+1,tmp_index = 0;while(l_begin<=mid && r_begin<=end){if(arr[l_begin]<=arr[r_begin]) tmp[tmp_index++] = arr[l_begin++];else tmp[tmp_index++] = arr[r_begin++];}while(l_begin<=mid) tmp[tmp_index++] = arr[l_begin++];while(r_begin<=end) tmp[tmp_index++] = arr[r_begin++];int k = 0;while(begin<=end){arr[begin++] = tmp[k++];}
}

相关文章:

排序算法学习记录-快速排序

快速排序 快速排序关键在于确定一个中间值&#xff0c;使得小于这个中间值的数在左边&#xff0c;大于这个中间值的数在右边。那么中间值该如何确定呢&#xff1f;有以下几种做法 首元素&#xff0c;也就是arr[l]尾元素&#xff0c;也就是arr[r]中间元素&#xff0c;也就是ar…...

安装windows版本的ros2 humble的时候,最后报错

"[rti_connext_dds_cmake_module][warning] RTI Connext DDS environment script not found (\resource\scripts\rtisetenv_x64Win64VS2017.bat). RTI Connext DDS will not be available at runtime, unless you already configured PATH manually." 意思是没找到。…...

Nginx 学习(十)高可用中间件的配置与实现

一 Keepalived热备 1 概述 调度器出现单点故障&#xff0c;如何解决?Keepalived实现了高可用集群Keepalived最初是为LVS设计的&#xff0c;专门监控各服务器节点的状态Keepalived后来加入了VRRP功能&#xff0c;防止单点故障 2 运行原理 Keepalived检测每个服务器节点状…...

[刷题记录]牛客面试笔刷TOP101

牛客笔试算法必刷TOP101系列,每日更新中~ 1.合并有序链表2023.9.3 合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com) 题意大致为: 将两个链表中的元素按照从小到大的顺序合并成为一个链表. 所给予的条件: 给出的所要合并的链表都是从小到大顺序排列的. 思路: 创建一…...

降水预报之双重惩罚

在降水预报中&#xff0c;通常会出现 "双重惩罚问题 "的指标或度量包括那些常用于预报验证的指标或度量。当假阴性&#xff08;漏报降水事件&#xff09;和假阳性&#xff08;误报&#xff09;受到同等惩罚或加权时&#xff0c;就会出现双重惩罚问题&#xff0c;这在…...

一条SQL语句的执行过程(附一次两段式提交)

一条SQL语句的完整执行过程是怎样的呢&#xff1f;我们用select和update语句来举例。 注意在mysql8后&#xff0c;进入服务层后&#xff0c;取消了去查询缓存(属于Server服务层)这个步骤&#xff0c;缓存中key是SQL语句&#xff0c;value是值&#xff0c;这样其实并不会提升性…...

Python基础知识详解:数据类型、对象结构、运算符完整分析

文章目录 python基础知识数据类型类型检查对象&#xff08;object&#xff09;对象的结构变量和对象类型转换运算符(操作符)1. 算术运算符2. 赋值运算符3. 比较运算符&#xff08;关系运算符&#xff09;4. 逻辑运算符5. 条件运算符&#xff08;三元运算符&#xff09; 总结 py…...

基于Streamlit的应用如何通过streamlit-authenticator组件实现用户验证与隔离

Streamlit框架中默认是没有提供用户验证组件的&#xff0c;大家在基于streamlit快速实现web应用服务过程中&#xff0c;不可避免的需要配置该应用的访问范围和权限&#xff0c;即用户群体&#xff0c;一般的做法有两种&#xff0c;一种是通过用户密码验证机制&#xff0c;要求只…...

[虚幻引擎插件介绍] DTGlobalEvent 蓝图全局事件, Actor, UMG 相互回调,自由回调通知事件函数,支持自定义参数。

本插件可以在虚幻的蓝图 Actor&#xff0c; Obiect&#xff0c;UMG 里面指定绑定和执行消息&#xff0c;可带自定义参数。 参数支持 Bool&#xff0c;Byte&#xff0c;Int&#xff0c;Int64&#xff0c;Float&#xff0c;Name&#xff0c;String&#xff0c;Text&#xff0c;Ve…...

2023数学建模国赛选题建议及BC题思路

大家好呀&#xff0c;全国大学生数学建模竞赛今天下午开赛啦&#xff0c;在这里先带来初步的选题建议及思路。 目前团队正在写B题和C题完整论文&#xff0c;后续还会持续更新哈&#xff0c;以下只是比较简略的图文版讲解&#xff0c;团队目前正在写B、C题完整论文&#xff0c;…...

vue3:4、组合式API-setup选项

setup每次都要return&#xff0c;好麻烦。怎么解决&#xff1f; 使用 <script setup> 语法糖&#xff08;底层帮你return了&#xff09; 写法如下...

【C刷题训练营】第三讲(c语言入门训练)

前言: 大家好&#xff0c;我决定日后逐渐更新c刷题训练营的内容&#xff0c;或许能帮到入门c语言的初学者&#xff0c;如果文章有错误&#xff0c;非常欢迎你的指正&#xff01; &#x1f4a5;&#x1f388;个人主页:​​​​​​Dream_Chaser&#xff5e; &#x1f388;&…...

简述视频智能分析EasyCVR视频汇聚平台如何通过“AI+视频融合”技术规避八大特殊作业风险

视频智能分析EasyCVR视频汇聚平台可以根据不同的场景需求&#xff0c;让平台在内网、专网、VPN、广域网、互联网等各种环境下进行音视频的采集、接入与多端分发。在视频能力上&#xff0c;视频云存储平台EasyCVR可实现视频实时直播、云端录像、视频云存储、视频存储磁盘阵列、录…...

2023年9月NPDP产品经理国际认证报名,找弘博创新

产品经理国际资格认证NPDP是新产品开发方面的认证&#xff0c;集理论、方法与实践为一体的全方位的知识体系&#xff0c;为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会&#xff08;PDMA&#xff09;成立于1979年&#xff0c;是…...

【MySQL】MySQL的安装,登录,配置和相关命令

文章目录 前言一. 卸载不需要的环境二. 获取MySQL的yum源三. 安装MySQL和启动四. 尝试登录MySQL方法1&#xff1a;获取临时root密码方法2&#xff1a;没有密码方法3&#xff1a;配置文件 五. 简单配置结束语 前言 本篇文章是基于云服务器&#xff1b;Linux&#xff1a;Centos7…...

攻防世界-WEB-php_rce

打开靶机链接 搜村ThinkPhP V5存在远程命令执行的漏洞 构建payload /index.php?sindex/think\app/invokefunction&functioncall_user_func_array&vars[0]system&vars[1][]ls 查询当前目录文件&#xff0c;没有发现flag。调整payload 得到flag文件&#xff0c;修…...

WRFDA资料同化实践技术

数值预报已经成为提升预报质量的重要手段&#xff0c;而模式初值质量是决定数值预报质量的重要环节。资料同化作为提高模式初值质量的有效方法&#xff0c;成为当前气象、海洋和大气环境和水文等诸多领域科研、业务预报中的关键科学方法。资料同化新方法的快速发展&#xff0c;…...

C++11新特性② | 左值、左值引用、右值与右值引用

目录 1、引言 2、值类别及相关概念 3、左值、右值 4、左值引用、右值引用 5、移动语义 5.1、为什么需要移动语义 5.2、移动语义定义 5.3、转移构造函数 5.4、转移赋值函数 6、标准库函数 std::move 7、完美转发 std::forward VC常用功能开发汇总&#xff08;专栏文章…...

Python Opencv实践 - Harris角点检测

参考资料&#xff1a;https://blog.csdn.net/wsp_1138886114/article/details/90415190 import cv2 as cv import numpy as np import matplotlib.pyplot as pltimg cv.imread("../SampleImages/chinease_tower.jpg", cv.IMREAD_COLOR) plt.imshow(img[:,:,::-1])#…...

el-upload上传图片到七牛云或阿里云

&#xff08;1&#xff09;绑定上传地址&#xff0c;上传数据对象 <el-upload class"upload-demo" :action"uploadUrl" :data"uploadData":on-success"handleSuccess" :file-list"[]" :show-file-list"false"…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析

MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录&#xff0c;这个目录下存放着许多可执行文件。与其他系统的可执行文件类似&#xff0c;这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中&#xff0c;用…...

2025.6.9总结(利与弊)

凡事都有两面性。在大厂上班也不例外。今天找开发定位问题&#xff0c;从一个接口人不断溯源到另一个 接口人。有时候&#xff0c;不知道是谁的责任填。将工作内容分的很细&#xff0c;每个人负责其中的一小块。我清楚的意识到&#xff0c;自己就是个可以随时替换的螺丝钉&…...

验证redis数据结构

一、功能验证 1.验证redis的数据结构&#xff08;如字符串、列表、哈希、集合、有序集合等&#xff09;是否按照预期工作。 2、常见的数据结构验证方法&#xff1a; ①字符串&#xff08;string&#xff09; 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...

NoSQL——Redis配置与优化

目录 关系型&非关系型数据库 一、核心原理对比‌ ‌二、核心特性对比‌ ‌三、关键区别剖析‌ ‌四、典型产品示例‌ ‌总结‌ Redis Redis核心原理 核心特性 技术意义 配置文件解析 1. 基础配置 2. 持久化配置 3. 内存管理 4. 高可用配置 5. 性能调优 6.…...