快速排序详讲(两种方法)

目录

原理

实现方式

正常实现

理由

先从右到左,在从左到右

先从左到右,先从右到左

挖坑法

效率

优化

测试

代码


原理

快速排序是将最左侧的数字当作关键数字,将关键数字放在对应位置,且关键数字左侧均大于它,右侧均小于它,采用递归的形式左右执行递归

实现方式

正常实现

升序排序:

先从右往左

如果开始位置小于结束位置并且当前位置大于关键数字则继续往左查找

再从左往右

如果开始位置小于结束位置并且当前位置小于关键数字则继续往左查找

两个结束后,此时begin位置大于关键数字,end位置小于,交换begin与end即可实现将关键数字左右两侧满足条件

当begin<end时继续执行如上操作

注意:先从右往左再从左往右不能进行交换

理由

先从右到左,在从左到右

右侧先停,左碰到右,则右侧此时位置小于关键数字,左碰到右,可保证相遇位置数字小于关键数字

左侧先停,右碰到左此时左侧位置为上一轮交换后的位置,即左侧此时小于关键数字,右碰到左,可保证相遇位置数字小于关键数字

先从左到右,先从右到左

与上相反

挖坑法

取出最左侧的数据

进入循环

同样从右往左查找,但是比较的是当前位置和关键数字的值

效率

和堆排序,希尔排序为同一级别

排序100000个数,快排和希尔均只用了10几ms,而冒泡则用了30s

优化

1.

我们可以将第一个数的位置和最后一个数的位置取出,创建mid=(left+right)/2,关键数字则为第一个数,最后一个数和mid三者之间的中间值,将中间值和首元素进行交换即可

2.

当元素个数小于10时,插入排序效率比快排更高,我们可以在此时使用插入排序代替快排

测试

一百万个数据

通过比较后我们可以发现

挖坑法比普通快排快一些,但是差距不大

优化后确实会比没优化要稍微快上一些

代码

void swap(int* p1, int* p2) {int a = *p1;*p1 = *p2;*p2 = a;
}
void insertsort(int* a, int sum) {//插排int begin, end, tmp;for (begin = 0; begin < sum - 1; begin++) {tmp = a[begin + 1];end = begin;while (end >= 0) {if (a[end] > tmp) {a[end + 1] = a[end];end--;}elsebreak;}a[end + 1] = tmp;}
}
int findmid(int* a, int left, int right) {。。中间值int mid = (left + right) / 2;if (a[left] > a[mid]) {if (a[mid] > a[right])return mid;else {if (a[left] > a[right])return right;return left;}}else {if (a[left] > a[right])return left;else {if (a[mid] > a[right])return right;return mid;}}
}
void normalquick(int* a, int left, int right) {//普通if (left >= right)return;int begin = left, end = right, key = left;while (begin < end) {while (begin < end && a[end] >= a[key])end--;while (begin < end && a[begin] <= a[key])begin++;swap(&a[begin], &a[end]);}swap(&a[begin], &a[key]);key = begin;normalquick(a, left, key - 1);normalquick(a, key + 1, right);
}
void quicksort(int* a, int left, int right) {//优化快排if (left >= right)return;if (right - left + 1 < 10) {insertsort(a + left, right - left + 1);return;}int begin = left, end = right, key = findmid(a, left, right);swap(&a[begin], &a[key]);key = left;while (begin < end) {while (begin < end && a[end] >= a[key])end--;while (begin < end && a[begin] <= a[key])begin++;swap(&a[begin], &a[end]);}swap(&a[begin], &a[key]);key = begin;quicksort(a, left, key - 1);quicksort(a, key + 1, right);
}
void quicksorthoare(int* arr, int left, int right) {//挖坑法if (left >= right)return;int begin=left, end=right, key=arr[left];while (begin < end) {while (begin < end && arr[end] >= key)end--;arr[begin] = arr[end];while (begin < end && arr[begin] <= key)begin++;arr[end] = arr[begin];}arr[begin] = key;quicksorthoare(arr, left, begin - 1);quicksorthoare(arr, begin + 1,right);
}
void shellsort(int* arr, int sum) {//希尔排序int i, j, gap=sum, tmp,a;while (gap > 1) {gap = gap / 3 + 1;for (i = 0; i < gap; i++) {for (j = i; j < sum - gap; j+=gap) {tmp = arr[j + gap];a = j;while (a >= 0) {if (arr[a] > tmp) {arr[a + gap] = arr[a];a -= gap;}elsebreak;}arr[a + gap] = tmp;}}}
}
void hoarequick(int* a, int left, int right) {//优化挖坑if (left >= right)return;if (right - left + 1 < 10) {insertsort(a + left, right - left + 1);return;}int begin = left, end = right, key = findmid(a, left, right);swap(&a[begin], &a[key]);key = a[left];while (begin < end) {while (begin < end && a[end] >= key)end--;a[begin] = a[end];while (begin < end && a[begin] <= key)begin++;a[end] = a[begin];}a[begin] = key;hoarequick(a, left, begin - 1);hoarequick(a, begin + 1, right);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/337930.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Spring Boot 开发 -- 过滤器与拦截器详解

引言 在Web开发中&#xff0c;经常需要对请求进行预处理或在响应后进行后处理&#xff0c;Spring Boot提供了过滤器和拦截器两种机制来实现这一需求。虽然它们都可以用来处理HTTP请求和响应&#xff0c;但在使用场景、执行顺序和配置方式上存在明显的差异。本文将详细讲解Spri…

江苏大信环境科技有限公司:环保领域的开拓者与引领者

2009 年&#xff0c;江苏大信环境科技有限公司在宜兴环保科技工业园成立。自创立之始&#xff0c;该公司便笃定坚守“诚信为本、以质量求生存、以创新谋发展”这一经营理念&#xff0c;全力以赴为客户构建专业的工业有机废气治理整体解决方案&#xff0c;进而成为国家高新技术企…

安全风险 - 组件导出风险

在安全审查中关于组件导出风险是一种常见问题&#xff0c;不同组件都有可能遇到这种问题&#xff0c;而且从一定角度来看的话&#xff0c;如果涉及到三方业务&#xff0c;基本处于无法解决的场景&#xff0c;所以我们需要说明为何无法避免这种风险 组件导出风险能不能规避&…

海康 面阵相机命名规则

海康 面阵相机命名规则 https://www.v-club.com/vCollage/vCollageDetail/516?subjectIdRMse6nPiyo

能不能接受这些坑?买电车前一定要看

图片来源&#xff1a;汽车之家 文 | Auto芯球 作者 | 雷慢 刚有个朋友告诉我&#xff0c;买了电车后感觉被骗了&#xff0c; 很多“坑”都是他买车后才知道的。 不提前研究&#xff0c;不做功课&#xff0c;放着我这个老司机不请教&#xff0c; 这个大冤种他不当谁当&…

Linux系统编程——动静态库

目录 一&#xff0c;关于动静态库 1.1 什么是库&#xff1f; 1.2 认识动静态库 1.3 动静态库特征 二&#xff0c;静态库 2.1 制作静态库 2.2 使用静态库 三&#xff0c;动态库 3.1 制作动态库 3.2 使用动态库一些问题 3.3 正确使用动态库三种方法 3.3.1 方法一&…

ADC数模转换器

一、ADC&#xff08;Analog-Digital Converter&#xff09;模拟-数字转换器 1、ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁 2、12位逐次逼近型ADC&#xff0c;1us转换时间 3、输入电压范围&#xff1a;0~3.3V&a…

Oracle dblink 发现Network 等待事件的分析 enq: KO - fast object checkpoint

所有的sql 通过dblink 查询全部等待中&#xff0c; 同一个SQL 20多个session 在跑&#xff0c;等待事件network&#xff0c;可能怀疑是不是网络断开了&#xff0c;导致没有返回 执行sql 如下&#xff1a; BEGIN Xdblink ; END; 去到dblink 所在的db&#xff0c;发现20多个sql在…

远程继电器模块实现(nodemcu D1 + 继电器)

前言 接下来将实现一个远程继电器&#xff0c;实时远程控制和查询的开关状态。用 5v 直流电控制 220v 交流电。 硬件上&#xff1a; 使用 nodemcu D1 和 JQC-3FF-S-Z 继电器。 软件上&#xff1a; 使用 nodejs 作为服务端&#xff0c;和 html 作为客户端。 在开始之前在电脑…

基于Qt GraphicView 解析 CIM/G 电力接线图文件

本文讲述了如何使用Qt的框架来渲染展示标准的CIM/G格式的图形文件&#xff0c;也就是公用信息模型&#xff08;common information model&#xff0c;CIM&#xff09;中的G文件部分的内容。这是一种电力系统图形的交换规则&#xff0c;用于电网图形交换。 [by amjieker] CIM/G …

⌈ 传知代码 ⌋ 命名实体识别

&#x1f49b;前情提要&#x1f49b; 本文是传知代码平台中的相关前沿知识与技术的分享~ 接下来我们即将进入一个全新的空间&#xff0c;对技术有一个全新的视角~ 本文所涉及所有资源均在传知代码平台可获取 以下的内容一定会让你对AI 赋能时代有一个颠覆性的认识哦&#x…

vue3组件传值---vue组件通过属性,事件和provide,inject进行传值

通过属性传值&#xff08;父传子&#xff09; vue的组件具有props自建属性&#xff08;自定义名称&#xff0c;类似于class&#xff0c;id的属性&#xff09;&#xff0c;通过这个属性&#xff0c;父组件可以向子组件传递参数&#xff0c;从而实现组件之间的信息传递&#xff0…

深入探讨npm、Yarn、pnpm和npx之间的区别

前端生态系统是一个快速发展的领域&#xff0c;充满了各种工具和技术。对于开发人员来说&#xff0c;跟上这些创新可能是一项艰巨的挑战。 在本文中&#xff0c;我们将深入探讨npm、Yarn、pnpm和npx之间的区别&#xff0c;帮助你理解每个工具的不同之处。 包管理器比较 npm …

原码一位乘法(计算机组成原理)

算法原理 每次将1位乘数所对应的部分积与原部分积的“累积和”相加&#xff0c;并移位 设置寄存器 存放部分积累积和、乘积高位存放被乘数存放乘数、乘积低位 法则 乘积的数值位俩数绝对值之积&#xff1b;符号位 位 俩数符号位进行异或&#xff0c;即 p x ⊕ y 步骤 设…

你认识nginx吗,nginx是做什么的,nginx可以做什么 --1)nginx介绍

一.Nginx 介绍 Nginx&#xff08;发音同engine x&#xff09;是一个异步框架的 Web 服务器&#xff0c;也可以用作反向代理&#xff0c;负载平衡器 和 HTTP 缓存。该软件由 Igor Sysoev 创建&#xff0c;并于2004年首次公开发布。同名公司成立于2011年&#xff0c;以提供支持。…

【原型模式】详解

一.概念 原型模式是一种创建型设计模式&#xff0c;它的主要思想是通过复制现有对象来创建新对象&#xff0c;而不是通过实例化一个类来创建。在原型模式中&#xff0c;我们称被复制的对象为原型&#xff08;Prototype&#xff09;&#xff0c;新创建的对象为克隆体&#xff0…

Redis缓存(笔记一:缓存介绍和数据库启动)

目录 1、NoSQL数据库简介 2、Redis介绍 3、Redis(win系统、linux系统中操作) 3.1 win版本Redis启动 3.2 linux版本Redis启动 1、NoSQL数据库简介 技术的分类&#xff1a;&#xff08;发展史&#xff09; 1、解决功能性的问题&#xff1a;Java、Jsp、RDBMS、Tomcat、HTML、…

IC开发——VCS基本用法

1. 简介 VCS是编译型verilog仿真器&#xff0c;处理verilog的源码过程如下&#xff1a; VCS先将verilog/systemverilog文件转化为C文件&#xff0c;在linux下编译链接生成可执行文件&#xff0c;在linux下运行simv即可得到仿真结果。 VCS使用步骤&#xff0c;先编译verilog源…

【计算机毕业设计】388微信小程序足球赛事及队伍管理系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

开发一个comfyui的自定义节点-支持输入中文prompt

文章目录 目标功能开发环境实现过程翻译中文CLIP编码拓展仓库地址完整代码目标功能 目前comfyui的prompt提示词输入节点 CLIP Text Encode 只支持输入英文的prompt,而有时候我们需要自己制定一些prompt,所以就得将我们想要的提示词翻译为英文后再复制粘贴到该节点的输入框中…