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

【每日一题】洛谷 - 快速排序模板

今天的每日一题来自洛谷,题目要求对给定的 N N N 个正整数进行从小到大的排序,并输出结果。我们将使用经典的**快速排序算法(QuickSort)**来解决这一问题。下面我将从问题分析、代码实现、及快速排序的核心思想进行详细说明。

题目分析

我们需要将输入的 N N N 个整数进行排序。根据题目给定的提示, N N N 的范围可以高达 1 0 5 10^5 105,因此我们需要选用高效的排序算法。快速排序具有平均时间复杂度为 O ( N log ⁡ N ) O(N \log N) O(NlogN)

如果你不知道什么是快速排序,以及不了解原理的可以看我另外几篇博客:

  • 【数据结构】分治算法经典: 快速排序详解
  • 【数据结构】时间复杂度和空间复杂度是什么?

代码实现

//
// Created by XuanRan on 2024/10/18.
//#include "iostream"using namespace std;int n;
long long arr[10 * 10 * 10 * 10 * 10 + 5];void quickSort(int l, int r)
{int x = l, y = r, mid = arr[(r + l) / 2];while (x < y){while (arr[x] < mid) x++;while (arr[y] > mid) y--;if (x <= y){swap(arr[x], arr[y]);x++;y--;}}if (y > l) quickSort(l, y);if (x < r) quickSort(x, r);
}int main(int argc, char* argv[])
{cin >> n;for (int i = 0; i < n; i++){cin >> arr[i];}quickSort(0, n - 1);for (int i = 0; i < n; i++){cout << arr[i] << " ";}
}

代码详解

输入与数组初始化

首先,程序读取输入的整数 N N N,并通过 cin 将 N N N 个元素存入数组 arr 中。为了确保数组足够大,这里将数组大小设定为 1 0 5 10^5 105 以上。

快速排序的实现

quickSort(int l, int r) 函数是快速排序的核心部分:

  • 我们选择数组中间的元素 mid 作为基准值。
  • 通过两个指针 x 和 y,分别从左侧和右侧开始扫描数组,将比基准值小的元素放在基准值左边,比基准值大的元素放在基准值右边。
  • 当 x 和 y 指针相遇后,递归地对左右两部分数组分别进行排序,直到整个数组有序。

输出结果

排序完成后,程序遍历数组,并将排序好的元素输出。

快速排序的优缺点

优点:

快速排序的平均时间复杂度是 O ( N log ⁡ N ) O(N \log N) O(NlogN),相对于 O ( N 2 ) O(N^2) O(N2) 的冒泡排序、选择排序等,效率更高。
空间开销小,使用的是原地排序,不需要额外的存储空间。

缺点:

在最坏情况下(如数组已经有序),快速排序的时间复杂度会退化到 O ( N 2 ) O(N^2) O(N2)
为了避免最坏情况,可以采取随机选择基准值的策略,即随机化快速排序(Randomized QuickSort)。

相关文章:

【每日一题】洛谷 - 快速排序模板

今天的每日一题来自洛谷&#xff0c;题目要求对给定的 N N N 个正整数进行从小到大的排序&#xff0c;并输出结果。我们将使用经典的**快速排序算法&#xff08;QuickSort&#xff09;**来解决这一问题。下面我将从问题分析、代码实现、及快速排序的核心思想进行详细说明。 题…...

Django模型优化

1、创建一个Django项目 可参考之前的带你快速体验Django web应用 我使用的是mysql数据库。按照上述教程完成准备工作。 2、创建一个app并完成注册 demo主要来完成创建用户、修改用户、查询用户、删除用户的操作。 python manage.py startapp test0023、app的目录 新建templ…...

Python实现火柴人的设计与实现

1.引言 火柴人&#xff08;Stick Figure&#xff09;是一种极简风格的图形&#xff0c;通常由简单的线段和圆圈组成&#xff0c;却能生动地表达人物的姿态和动作。火柴人不仅广泛应用于动画、漫画和涂鸦中&#xff0c;还可以作为图形学、人工智能等领域的教学和研究工具。本文…...

衡石分析平台系统分析人员手册-应用模版

应用模板​ 应用模板使分析成果能被快速复用&#xff0c;节省应用创作成本&#xff0c;提升应用创作效率。此外应用模板实现了应用在不同环境上快速迁移。 支持应用复制功能 用户可以从现有的分析成果关联到新的分析需求并快速完成修改。 支持应用导出为模板功能 实现多个用户…...

Git和SVN

一. Git和SVN的区别 1.1 Git是分布式的&#xff0c;SVN是集中式的 1.2 Git复杂概念多&#xff0c;SVN简单易上手 Git 的命令实在太多了&#xff0c;日常工作需要掌握 add, commit, status, fetch, push, rebase等&#xff0c;若要熟练掌握&#xff0c;还必须掌握 rebase和 m…...

【C语言教程】【常用类库】(十八)宏与预处理 - <stddef.h> 和 <stdbool.h>

18. 宏与预处理 - <stddef.h> 和 <stdbool.h> C语言的宏和预处理指令在程序编译之前就被执行&#xff0c;用于文件包含、符号定义、条件编译等操作。理解和运用宏和预处理可以提高代码的灵活性和可移植性。 18.1 宏定义与条件编译 18.1.1 #define 与参数化宏 #…...

订单超时过期的实现方案的探讨

在我们的业务开发中&#xff0c;会遇到这样一个场景&#xff0c;用户下了一个单&#xff0c;如果超过20分钟不进行支付&#xff0c;订单就要变成已取消状态。 字段设定 订单中需要设定了三个字段&#xff1a;订单是否取消、是否支付、支付超时时间。 订单是否取消会存在&…...

C++中的CRTP

CRTP&#xff0c;全称为 Curiously Recurring Template Pattern&#xff08;奇异递归模板模式&#xff09;&#xff0c;是一种在C中使用继承和模板技术来实现静态多态和功能复用的惯用法。它使用派生类来模板参数化基类&#xff0c;使得基类能够访问派生类&#xff0c;从而在编…...

go压缩的使用

基础&#xff1a;使用go创建一个zip func base(path string) {// 创建 zip 文件zipFile, err : os.Create("test.zip")if err ! nil {panic(err)}defer zipFile.Close()// 创建一个新的 *Writer 对象zipWriter : zip.NewWriter(zipFile)defer zipWriter.Close()// 创…...

一图解千言,了解常见的流程图类型及其作用

在企业管理、软件研发过程中&#xff0c;经常会需要进行各种业务流程梳理&#xff0c;而流程图就是梳理业务时必要的手段&#xff0c;同时也是梳理的产出。但在不同的情况下适用的流程图又不尽相同。 本文我们就一起来总结一下8 种最常见的流程图类型 数据流程图 数据流程图&…...

【微信小程序_19_自定义组件(1)】

摘要:本文主要介绍了小程序开发中自定义组件的相关知识。包括组件的创建与引用,可在项目根目录创建组件文件夹,生成相应文件,并根据使用频率选择全局或局部引用。还阐述了组件和页面的区别,如组件的.json 文件需声明 “component: true”,.js 文件调用 Component () 函数…...

标准版admin后台页面添加及开发操作流程及注意事项

基础介绍 CRMEB后台管理是基于vue2技术栈进行开发搭建的 Vue Router 使用的是v3版本&#xff0c;mode为history模式 如需修改 mode 请在src/setting.js中修改routerMode 新建页面 新建路由 根据目录结构&#xff0c;需要在src/router/modules中对应模块中&#xff0c;添加对…...

‘perl‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件。

‘perl’ 不是内部或外部命令,也不是可运行的程序 或批处理文件。 明明已经根据教程安装了perl环境,但是在cmd中依赖报该错误,本章教程提供解决办法。 一、激活perl环境 state shell ActiveState-Perl-5.36.0此时输入perl -v 是可以直接输出perl版本号的。 二、找到perl的执…...

如何利用CMMI帮助组织消除低价值流程

CMMI发展到今天&#xff0c;过程中历经了不断的蜕变和升级。从早期的CMM到今天的CMMI3.0&#xff0c;从早期的22个过程域优化组合到今天的20个实践域&#xff0c;从早期隶属的SEI到今天的CMMI研究院&#xff0c;所有的变化都是与时俱进&#xff0c;都是为了提供更好的实践&…...

如何理解线程安全这个概念?

文章目录 为什么需要线程安全&#xff1f;线程安全的实现方式总结推荐阅读文章 线程安全&#xff08;Thread Safety&#xff09;是指在多线程环境中&#xff0c;多个线程同时访问某个对象时&#xff0c;不会导致程序出现错误的状态或不一致的结果。简单来说&#xff0c;线程安全…...

代码随想录算法训练营第48天| 739. 每日温度,496.下一个更大元素 I,503.下一个更大元素II

第十一章&#xff1a;图论part01 图论理论基础 大家可以在看图论理论基础的时候&#xff0c;很多内容 看不懂&#xff0c;例如也不知道 看完之后 还是不知道 邻接矩阵&#xff0c;邻接表怎么用&#xff0c; 别着急。 理论基础大家先对各个概念有个印象就好&#xff0c;后面在…...

Qt 支持打包成安卓

1. 打开维护Qt&#xff0c;双击MaintenanceTool.exe 2.登陆进去,默认是添加或移除组件&#xff0c;点击下一步&#xff0c; 勾选Android, 点击下一步 3.更新安装中 4.进度100%&#xff0c;完成安装&#xff0c;重启。 5.打开 Qt Creator&#xff0c;编辑-》Preferences... 6.进…...

PDF工具类源码

PDF-Guru: PDF Guru Anki是一款以PDF为中心的多功能办公学习工具箱软件&#xff0c;包含四大板块功能&#xff1a;PDF实用工具箱、Anki制卡神器、Anki最强辅助、视频笔记神器&#xff0c;软件功能众多且强大&#xff0c;熟练运用可以大幅提高办公和学习效率&#xff0c;绝对是您…...

NirCmd-Gui-Chinese-Introduction

简介 此程序是我的一个练习作品&#xff0c;单纯是为了提升编程水平&#xff0c;次要是为了做一个NirCmd的Gui&#xff0c;其实主要成分还是Gui&#xff0c;核心代码就两三行。 主要是Gui&#xff0c;功能基于nircmd.exe实现&#xff0c;程序本身不提供一些重要的功能。 关于…...

吴恩达深度学习笔记(7)

误差分析&#xff1a; 你运行一个算法代替人类计算&#xff0c;但是没有达到人类的效果&#xff0c;需要手动检查算法中的错误&#xff0c;对模型的一些部分做相应调整&#xff0c;才能更好地提升分类的精度。如果不加分析去做&#xff0c;可能几个月的努力对于提升精度并没有…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...