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

数据结构—快速排序(续)

引言:在上一篇中我们详细介绍了快速排序和改进,并给出了其中的一种实现方式-挖坑法

但其实快速排序有多种实现方式,这篇文章再来介绍其中的另外两种-左右指针法和前后指针法。有了上一篇挖坑法的启示,下面的两种实现会容易许多。

 一、左右指针法

 首先进行“三数取中”

 

 

这样就完成了比4小的在左边,比4大的在右边。

就继续递归就好了。

下面是代码:

int mid_quick_number(int* arry, int left, int right) {int mid = left + (right - left >> 1);//去中间数防止普通求中间数溢出问题,//同时注意优先级,+ -的优先级高于》《if (arry[mid] > arry[left]) {if (arry[right] > arry[mid]) {mid = mid;}else if(arry[right]>arry[left]){mid = right;}else {mid = left;}}else {if (arry[right] < arry[mid]) {mid = mid;}else if (arry[right] > arry[left]) {mid = left;}else {mid = right;}}return mid;
}
//左右指针法
void dfs_quick_sort2(int* arry, int left, int right) {if ((right - left) <= 0)return;int mid = mid_quick_number(arry, left, right);swap(arry + mid, arry + left);int key = arry[left];int start = left;int end = right;while (start < end) {while (start < end && key <= arry[end]) {end--;}//右指针去找比key小的,停下while (start < end && key >= arry[start]) {start++;}//左指针去找大的,停下swap(arry + start, arry + end);//交换大的和小的}swap(arry + end, arry+left);//最后两个指针重合,将key与right或左的值交换dfs_quick_sort2(arry, left, start - 1);dfs_quick_sort2(arry, start + 1, right);
}

二、前后指针法

 

 

这样就可以把它拆分成两段,在对这两段进行递归即可。

 下面来看代码:

//前后指针法
void dfs_quick_sort3(int* arry, int left, int right) {if ((right - left) <= 0)return;int mid = mid_quick_number(arry, left, right);swap(arry + mid, arry + left);int key = arry[left];int cur = left;int pre = left - 1;while (cur <= right) {while (cur <= right && arry[cur] >= key) {cur++;}if (cur <= right) {pre++;swap(arry + cur, arry + pre);}}if (pre == left-1)pre++;dfs_quick_sort3(arry, left, pre);dfs_quick_sort3(arry, pre + 1, cur - 1);
}

好了,这是本篇文章的所有内容了,希望对你有所帮助!

相关文章:

数据结构—快速排序(续)

引言&#xff1a;在上一篇中我们详细介绍了快速排序和改进&#xff0c;并给出了其中的一种实现方式-挖坑法 但其实快速排序有多种实现方式&#xff0c;这篇文章再来介绍其中的另外两种-左右指针法和前后指针法。有了上一篇挖坑法的启示&#xff0c;下面的两种实现会容易许多。 …...

Snapdragon Profiler分析Android GPU

Snapdragon Profiler&#xff08;骁龙分析器&#xff09;是一款性能分析软件&#xff0c;在Windows、 Mac、和 Linux平台上都可以运行&#xff0c;主要是用来分析使用了高通骁龙处理器的Android设备。 Snapdragon Profiler通过USB连接这些Android设备&#xff0c;开发者可以用…...

Cannot download sources:IDEA源码无法下载

问题 Swagger的相关包&#xff0c;无法看到注释&#xff1b; 在class文件的页面&#xff0c;点击下载源码&#xff0c;源码下载不了&#xff0c;IDEA报下面的错误。 报错 Cannot download sources Sources not found for: io.swagger.core.v3:swagger-annotations:2.2.9 解决…...

从零开始学习 Java:简单易懂的入门指南之IO字符流(三十一)

IO流之字符流 1. 字符流1.1 字符输入流【Reader】1.2 FileReader类构造方法读取字符数据 1.3 字符输出流【Writer】1.4 FileWriter类构造方法基本写出数据关闭和刷新写出其他数据 2. IO异常的处理JDK7前处理JDK7的处理JDK9的改进 3. 综合练习练习1&#xff1a;拷贝文件夹练习2&…...

监狱工具管理系统-监狱劳动工具管理系统

监狱劳动工具管理系统(智工具DW-S308)是依托互3D技术、云计算、大数据、RFID技术、数据库技术、AI、视频分析技术对工具进行统一管理、分析的信息化、智能化、规范化的系统。 当前各级监狱工器具管理更多的是借助于传统的人工管理方法和手段&#xff0c;数据的采集和录入一直以…...

蓄水池算法

题目&#xff1a; 假设有一组数据流元素有 N 个&#xff08;事先不知道 N 具体值&#xff09;&#xff0c;我们希望选择 n 个样本&#xff08;N > n&#xff09;&#xff0c;使用怎样的策略进行抽样可以使得数据流中每个元素被选择的概率恰为 n / N 结论&#xff1a; 创建大…...

作业 day4

完成父子进程通信...

erlang练习题(四)

题目一 传入列表 L1[K|]、L2[V|]、L3[{K,V}|_]&#xff0c;L1和L2一一对应&#xff0c;L1为键列表&#xff0c;L2为值列表&#xff0c;L3为随机kv列表&#xff0c; 将L1和L2对应位合并成KV列表L4&#xff0c;再将L3和L4相加&#xff0c;相同key的value相加 如&#xff1a;L…...

YoloV5实时推理最短的代码

YoloV5实时推理最简单代码 import cv2 import torch# 加载YOLOv5模型 model torch.hub.load(ultralytics/yolov5, yolov5s)# 使用CPU或GPU进行推理 device cuda if torch.cuda.is_available() else cpu model.to(device)# 打开摄像头&#xff08;默认摄像头&#xff09; cap…...

Tensorflow、Pytorch和Ray(张量,计算图)

1.深度学习框架&#xff08;Tensorflow、Pytorch&#xff09; 1.1由来 可以追溯到2016年&#xff0c;当年最著名的事件是alphago战胜人类围棋巅峰柯洁&#xff0c;在那之后&#xff0c;学界普遍认为人工智能已经可以在一些领域超过人类&#xff0c;未来也必将可以在更多领域超过…...

TinyWebServer学习笔记-让程序跑起来

目标&#xff1a;通过这个HTTP项目熟悉网络编程 系统&#xff1a;Ubuntu20.04 首先&#xff0c;学习的第一步就是先让程序跑起来&#xff0c;使用git将项目下载到虚拟机内&#xff1a; git clone https://github.com/qinguoyi/TinyWebServer.git 提前把MySQL数据库安装好&am…...

_tkinter.TclError: no display name and no $DISPLAY environment variable 解决

启动kohya_ss时可能会发生错误&#xff1a; _tkinter.TclError: no display name and no $DISPLAY environment variable 解决办法&#xff1a; 1、apt-get install xvfb //安装xvfb // 启动虚拟显示器 2、Xvfb :99 -screen 0 1024x768x16 & export DISPLAY:99 ps aux…...

我出手了!

时光飞逝&#xff0c;程序员小灰这个微信公众号&#xff0c;已经运营整整7年时间了。 在这7年里&#xff0c;小灰输出过各种各样的文章和视频&#xff0c;有讲编程技术的&#xff0c;有讲职业规划的&#xff0c;有讲互联网行业新闻的&#xff0c;也有讲自己个人生活的。 不过&a…...

springboot的配置文件(properties和yml/yaml)

springboot的配置文件有两种格式分别是properties和yml/yaml 创建配置文件 在创建springboot项目时候&#xff0c;会默认生成application.properties这种格式 书写风格 端口 application.propertis server.port8080 application.yml server:port: 8080 连接数据库 applica…...

SLAM面试笔记(7) — Linux面试题

目录 问题1&#xff1a;Linux系统基本组件&#xff1f; 问题2&#xff1a;Linux和Unix有什么区别&#xff1f; 问题3&#xff1a;Linux下编译程序 问题4&#xff1a;gcc基本格式和常用指令 问题5&#xff1a;用什么命令查找内存和交换使用情况&#xff1f; 问题6&#xf…...

QUIC不是TCP的替代品

QUIC取代了TCP成为HTTP3的基础传输协议&#xff0c;不是因为QUIC能够取代TCP的所有应用场景&#xff0c;而是因为QUIC更适合HTTP的请求/响应业务模型。原文: QUIC Is Not a TCP Replacement TCP新规范(RFC 9293)的发布是网络界的一件大事&#xff0c;值得围绕这一主题发表第二篇…...

计算机竞赛 目标检测-行人车辆检测流量计数

文章目录 前言1\. 目标检测概况1.1 什么是目标检测&#xff1f;1.2 发展阶段 2\. 行人检测2.1 行人检测简介2.2 行人检测技术难点2.3 行人检测实现效果2.4 关键代码-训练过程 最后 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 行人车辆目标检测计数系统 …...

GPT系列模型解读:GPT-1

GPT系列 GPT&#xff08;Generative Pre-trained Transformer&#xff09;是一系列基于Transformer架构的预训练语言模型&#xff0c;由OpenAI开发。以下是GPT系列的主要模型&#xff1a; GPT&#xff1a;GPT-1是于2018年发布的第一个版本&#xff0c;它使用了12个Transformer…...

王杰国庆作业day3

父子进程对话 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <my_head.h> int main(int argc, const char *argv[]) {mkfifo("./fifo1",0664);mkfifo("./fifo2",0664);pid_t cpid fork();if(0 < cp…...

量子计算基础知识—Part1

1.什么是量子计算机&#xff1f; 量子计算机是基于量子力学原理构建的机器&#xff0c;采用了一种新的方法来处理信息&#xff0c;从而使其具有超强的功能。量子计算机使用Qubits处理信息。 2. 什么是量子系统&#xff1f; 一个量子系统指的是由量子力学规则描述和控制的物理…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

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

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

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...