当前位置: 首页 > 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;可能几个月的努力对于提升精度并没有…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

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

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

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...