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

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

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

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

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...