【算法】快速排序的基本思想、优化 | 挖坑填补法和区间分割法
创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步!
更多算法分析与设计知识专栏:算法分析🔥
给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

目录
- 一、挖坑填补法
- 二、区间分割法
- 三、快排的优化:
快排的基本思想:先确定一个标准值,将比标准值小的元素放在标准值的左侧,比标准值大的元素放在右侧,左右部分分别重复以上的操作,直到整个数组有序。
快速排序是基于分治策略的排序算法
一、挖坑填补法
- 选择一个基准元素
- 将基准元素挖出,形成一个坑
- 从右向左遍历数组,找到第一个比基准元素小的元素,将其填入空坑中,并将此位置视为新的坑
- 从左向右遍历数组,找到第一个比基准元素大的元素,将其填入新的空坑中,并将此位置视为新的坑
- 重复过程,直到左右指针相遇
- 最后将基准元素填入坑中,此时基准元素左边的所有元素都比它小,右边的所有元素都比它大。
- 对基准元素左边和右边的子数组递归地进行上述操作,直到整个数组有序

C++代码:
#include <iostream>
#include <cmath>
using namespace std;int partition(int arr[], int left, int right)
{// 确定标准值,保存起来int standard = arr[left];//使用双指针从两端开始,将比标准值大的数放到标准值右侧,小于标准值的放到左侧while (left < right){//从右到左(right到left)找到比标准值小的//如果遇到的值大于等于标准值,则跳过 right--while (left < right && arr[right] >= standard){right--;}//找到了比标准值小的值arr[right],放到左边的left坑中arr[left] = arr[right];//从左到右(left到right)找到比标准值大的//如果遇到的值小于等于标准值,则跳过 left++while (left < right && arr[left] <= standard){left++;}//找到了比标准值大的值arr[left],放到左边的right坑中arr[right] = arr[left];}//中间的坑放入标准值arr[left] = standard;//返回标准值的下标return left;
}void quicksort(int arr[], int left, int right)
{if (arr == NULL || left >= right) return;int standard = partition(arr, left, right);quicksort(arr, left, standard - 1);quicksort(arr, standard + 1, right);
}void print(int arr[], int len)
{if (arr == NULL || len <= 0) return;for (int i = 0; i < len; i++){std::cout << arr[i] << " ";}std::cout << endl;
}int main()
{int arr[] = { 5, 1, 7, 0, 4, 3, 4, 9, 6 };int len = sizeof(arr) / sizeof(arr[0]);cout << "------------------------------" << endl << "原始序列:";print(arr, len);quicksort(arr, 0, len - 1);cout << "------------------------------" << endl << "排序后序列:";print(arr, len);return 0;
}

二、区间分割法
#include <iostream>
#include <cmath>
using namespace std;int partition(int arr[], int left, int right)
{int nSmall = left - 1;for (left; left < right; left++){if (arr[left] < arr[right]){//小区间扩张if (++nSmall != left){arr[nSmall] = arr[nSmall] ^ arr[left];arr[left] = arr[nSmall] ^ arr[left];arr[nSmall] = arr[nSmall] ^ arr[left];}}}//将标准值放入if (++nSmall != right){arr[nSmall] = arr[nSmall] ^ arr[right];arr[right] = arr[nSmall] ^ arr[right];arr[nSmall] = arr[nSmall] ^ arr[right];}return nSmall;
}
void print(int arr[], int len)
{if (arr == NULL || len <= 0) return;for (int i = 0; i < len; i++){std::cout << arr[i] << " ";}std::cout << endl;
}int main()
{int arr[] = { 5, 1, 7, 0, 4, 3, 4, 9, 6 };int len = sizeof(arr) / sizeof(arr[0]);cout << "------------------------------" << endl << "原始序列:";print(arr, len);quicksort(arr, 0, len - 1);cout << "------------------------------" << endl << "排序后序列:";print(arr, len);return 0;
}
三、快排的优化:
- 1.标准值的选取:选取三个数字(头、尾、中间),选择大小为中间值的
- 2.分割到数据较少时,不再使用快排,使用插入排序
- 3.使用栈取代递归
- 4.尾递归
以下为使用了标准值三选一、按情况使用插入排序的优化后代码:
class Solution {
public:void swap (vector<int>& nums, int i, int j) { int temp = nums[i];nums[i] = nums[j];nums[j] = temp;} void insertSort (vector<int>& nums, int left, int right) {for (int i = left+1; i <= right; i++) {int temp = nums[i];int j = i-1;for (j = i-1; j >= 0; j--) {if (temp < nums[j]) {nums[j+1] = nums[j];continue;} break;}nums[j+1] = temp;}} int place(vector<int>& nums,int left,int right){//标准值三选一int mid = left + (right-left)/2;if (nums[left] > nums[right]) swap(nums,left,right);if (nums[mid] > nums[right]) swap(nums,mid,right);if (nums[mid] > nums[left]) swap(nums,mid,left); int standard = nums[left];while(left < right){while(left<right&&nums[right]>standard){right--;}nums[left] = nums[right];while(left<right&&nums[left]<standard){left++;}nums[right] = nums[left];}nums[left] = standard;return left;}void quickSort(vector<int>& nums,int left,int right){//分割到数据较少时,不再使用快排,使用插入排序if (right - left <= 5) {insertSort(nums,left,right);return;} if(nums.size() == 0 || left >= right) return;int standard = place(nums,left,right);quickSort(nums,left,standard-1);quickSort(nums,standard+1,right);}vector<int> sortArray(vector<int>& nums) {quickSort(nums,0,nums.size()-1);return nums;}
};

| 大家的点赞、收藏、关注将是我更新的最大动力! 欢迎留言或私信建议或问题。 |
| 大家的支持和反馈对我来说意义重大,我会继续不断努力提供有价值的内容!如果本文哪里有错误的地方还请大家多多指出(●'◡'●) |
相关文章:
【算法】快速排序的基本思想、优化 | 挖坑填补法和区间分割法
创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡>𖥦<)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 更多算法分析与设计知识专栏:算法分析🔥 给大家跳…...
OSPF动态路由实验(华为)
思科设备参考:OSPF动态路由实验(思科) 一,技术简介 OSPF(Open Shortest Path First)是一种内部网关协议,主要用于在单一自治系统内决策路由。它是一种基于链路状态的路由协议,通过…...
EasyRecovery2024专业免费的电脑数据恢复软件
EasyRecovery数据恢复软件是一款功能强大的数据恢复工具,广泛应用于各种数据丢失场景,帮助用户从不同类型的存储介质中恢复丢失或删除的文件。 该软件支持恢复的数据类型非常广泛,包括但不限于办公文档、图片、音频、视频、电子邮件以及各种…...
Vue集成PageOffice实现在线编辑word、excel(前端配置)
一、什么是PageOffice PageOffice是一款在线的office编辑软件,帮助Web应用系统或Web网站实现用户在线编辑Word、Excel、PowerPoint文档。可以完美实现在线公文流转,领导批阅,盖章。可以给文件添加水印,在线安全预览防止用户下载…...
IBM SPSS Statistics for Mac:数据分析的卓越工具
IBM SPSS Statistics for Mac是一款功能强大的数据分析软件,专为Mac用户设计,提供了一系列专业的统计分析和数据管理功能。无论是科研人员、数据分析师还是学生,都能从中获得高效、准确的数据分析支持。 IBM SPSS Statistics for Mac v27.0.1…...
python爬虫------- Selenium下篇(二十三天)
🎈🎈作者主页: 喔的嘛呀🎈🎈 🎈🎈所属专栏:python爬虫学习🎈🎈 ✨✨谢谢大家捧场,祝屏幕前的小伙伴们每天都有好运相伴左右,一定要天天…...
获取字符串的全排列(去除字符串中2个字符相同时造成的重复)
一、概念 现有一个字符串,要打印出该字符串中字符的全排列。 以字符串abc为例,输出的结果为:abc、acb、bac、bca、cab、cba。 以字符串aab为例,输出的结果为:aab、aba、baa。 二、代码 public class Permutation {pub…...
HTML5新增的多媒体标签
在网页中加入音乐 <audio></audio> src 设置音乐文件名以及路径,<audio>标记支持MP3、WAV及OGG 3种音乐格式 autoplay:是否自动播放,加入autopaly属性表示自动播放 controls: 是否显示播放面板,加入controls属性表示显示播放面板 …...
温湿度传感器(DHT11)以及光照强度传感器(BH1750)的使用
前言 对于一些单片机类的环境检测或者智能家居小项目中,温湿度传感器(DHT11)以及光照强度传感器(BH1750)往往是必不可少的两个外设,下面我们来剖析这两个外设的原理,以及使用。 1. 温湿度传感…...
ActiveMQ 04 Linux下安装
Active MQ 04 Linux下安装 下载 解压 在init.d下建立软连接 ln -s /usr/local/activemq/bin/activemq ./设置开启启动 chkconfig activemq on 服务管理 service activemq start service activemq status service activemq stopNIO配置 默认配置为tcp,使用的…...
.pyc 文件是什么?是否有必要同步到 GitHub 远程仓库?
git status 时发现有很多 .pyc 的没有被 add (env) username:~/path/to/project$ git status On branch main Your branch is up to date with origin/main.Changes to be committed:(use "git restore --staged <file>..." to unstage)new file: xxx.pyCha…...
Zookeeper的集群搭建和ZAB协议详解
Zookeeper的集群搭建 1)zk集群中的角色 Zookeeper集群中的节点有三个角色: Leader:处理集群的所有事务请求,集群中只有一个LeaderFollwoer:只能处理读请求,参与Leader选举Observer:只能处理读…...
STM32 MPU配置参数
TXE LEVEL一般只用MPU_TEX_LEVEL0 1 - 1 - 1 -0性能最强(TEX - C - B- S). #define MPU_TEX_LEVEL0 ((uint8_t)0x00) #define MPU_TEX_LEVEL1 ((uint8_t)0x01) #define MPU_TEX_LEVEL2 ((uint8_t)0x02) 基于上表进行常用配置 ÿ…...
Kafka概述
目录 1、为什么需要消息队列(MQ) 2、使用消息队列的好处 3、消息队列的两种模式 4、Kafka 定义 5、Kafka 简介 6、Kafka 的特性 7、Kafka 系统架构 8、Partation 数据路由规则 9、分区的原因 1、为什么需要消息队列(MQ) …...
OpenHarmony编译构建系统
这篇来聊聊OpenHarmony的编译构建,经过前面的实践,再来看编译构建。 编译构建概述 在官网中提到了,OpenHarmony编译子系统是以GN和Ninja构建为基座,对构建和配置粒度进行部件化抽象、对内建模块进行功能增强、对业务模块进行功能…...
Qt5 编译oracle数据库驱动
库文件 1、Qt源码目录:D:\Qt5\5.15.2\Src\qtbase\src\plugins\sqldrivers\oci 2、oracle客户端SDK: https://www.oracle.com/database/technologies/instant-client/winx64-64-downloads.html 下载各版本中的如下压缩包,一定要版本相同的 将两个压缩包…...
UE5学习日记——实现自定义输入及监听输入,组合出不同的按键输入~
UE5的自定义按键和UE4有所不同,在这里记录一下。 本文主要是记录如何设置UE5的自定义按键,重点是学会原理,实际开发时结合实际情况操作。 输入映射 1. 创建输入操作 输入操作并不是具体的按键映射,而是按键的激活方式࿰…...
为什么把script标签放在div下面?
放在底部可以优先加载页面的内容结构,提升页面渲染速度。只有等到HTML解析完成后,才会开始执行main.js,避免JS阻塞页面解析, 同时main.js里可能会操作DOM,如果放头部,可能会找不到节点而报错 <body><div id"root"><App></App>&l…...
Git 自定义命令
前言 在使用 hexo 搭建个人博客时,共两种部署的方法。分别为: 本地利用 hexo 的插件 hexo-deployer-git 来实现部署,缺点是需要多敲几个命令行且不方便对源码进行云端备份使用 Github Action 的 workflow 自动化部署,优势就是可…...
SpringBoot多数据源配置及使用
1.application.properties数据配置 首先现在配置文件中定义三个数据库相关信息 # 数据库1 targetLibraryMain.datasource.url jdbc:kingbase8://127.0.0.1:54321/DATA_ONE?useUnicodetrue&characterEncodingutf8&serverTimezoneGMT%2B8&allowMultiQueriestrue …...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
