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

利用分治策略优化快速排序

1. 基本思想

    分治快速排序(Quick Sort)是一种基于分治法的排序算法,采用递归的方式将一个数组分割成小的子数组,并通过交换元素来使得每个子数组元素按照特定顺序排列,最终将整个数组排序。

快速排序的基本步骤:

  1. 选择基准元素:从数组中选择一个元素作为基准(pivot)。
  2. 分区操作:将数组分成两个部分,左边的部分所有元素都小于基准元素,右边的部分所有元素都大于基准元素。此时基准元素已经排好序。
  3. 递归排序:对基准元素左侧和右侧的子数组递归进行快速排序。

快速排序的核心思想:

  • 分治法:通过每次选择一个基准元素,将数组分割成两个子数组,然后递归地对两个子数组进行排序。
  • 每次选择基准元素后,通过分区将数组划分为两个部分,左侧部分的元素都小于基准,右侧部分的元素都大于基准。
  • 递归对子数组进行排序,直到每个子数组的长度为 1 或 0,排序完成。
// 分区函数,返回基准元素的正确位置
int Partition(vector<int>& arr, int low, int high) {int pivot = arr[high];  // 选择最后一个元素作为基准int i = low - 1;  // i 是小于基准元素的子数组的最后一个元素的索引// 遍历数组,将小于基准的元素移动到数组的前面for (int j = low; j < high; ++j) {if (arr[j] < pivot) {++i;swap(arr[i], arr[j]);}}// 将基准元素放到正确的位置swap(arr[i + 1], arr[high]);return i + 1;  // 返回基准元素的索引
}// 快速排序函数
void QuickSort(vector<int>& arr, int low, int high) {if (low < high) {// 找到基准元素的索引int pi = Partition(arr, low, high);// 递归排序基准元素左边和右边的子数组QuickSort(arr, low, pi - 1);  // 排序左边子数组QuickSort(arr, pi + 1, high); // 排序右边子数组}
}

 2. 快速选择算法

    快速选择算法(Quickselect) 是一种基于快速排序(Quick Sort)的算法,用于在未排序的数组中找到第 k 小(大)的元素。与快速排序不同,快速选择只对包含第 k 小(大)元素的部分进行排序,而不需要对整个数组进行排序,因此它的时间复杂度通常较低。

快速选择的核心思想是:

  1. 与快速排序一样,通过选择一个“基准”元素并进行分区(Partition)操作,将数组分成左右两个部分。
  2. 如果基准元素的位置正好是 k,则基准元素即为第 k 小的元素。
  3. 如果基准元素的位置小于 k,则继续在右侧子数组中查找第 k 小元素。
  4. 如果基准元素的位置大于 k,则继续在左侧子数组中查找第 k 小元素。

通过将数组分成三个部分:小于基准、等于基准、大于基准,从而更有效地找到第 k 小的元素。相较于传统的快速选择算法,使用三个部分分区可以加速查找过程,特别是在处理重复元素时。

下面是一个示例,这类问题可以以此为模板,通过适当修改来实现不同的目标。 

int qsort(vector<int>& nums, int l, int r, int k){if(l == r) return nums[l];//1.随机选择基准数int key = getRandom(nums, l, r);//2.根据基准数将数组分成三组int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]); }//3.分情况讨论int c = r - right + 1, b = right - left - 1;if(c >= k)return qsort(nums, right, r, k);else if(b + c >= k) return key;else  return qsort(nums, l, left, k - b - c);}int getRandom(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left) + left];}

3. 颜色分类

解法:三指针

排序时数组被分成四个部分,[0, left] 区间都是0,(left, i)区间都是1,[i, right]区间是未排序的部分,[right , n - 1]区间都是2.

排序完成后,i与right相等,数组被分成三个部分[0, left]都是1,(left, i)都是0,[right , n - 1]都是2

class Solution {
public:void sortColors(vector<int>& nums) {int i = 0, n = nums.size();int left = -1, right = n;while(i < right){if(nums[i] == 0) swap(nums[i++], nums[++left]);else if(nums[i] == 1) i++;else if(nums[i] == 2) swap(nums[i], nums[--right]);}}
};

75. 颜色分类 - 力扣(LeetCode)

4.  排序数组

使用将数组分成三部分的思想实现快排,效率会更高

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vector<int>& nums, int l, int r){if(l >= r) return;int key = getRanNum(nums, l, r);//获取随机基准值int i = l, left = l - 1, right = r + 1;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}qsort(nums, l, left);qsort(nums, right, r);}int getRanNum(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left) + left];}
};

912. 排序数组 - 力扣(LeetCode)

5. 数组中第k个最大元素

快速选择算法

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vector<int>& nums, int l, int r, int k){if(l == r) return nums[l];//返回条件//1.随机选择基准数int key = getRandom(nums, l, r);//2.根据基准数将数组分成三组int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]); }//3.分情况讨论int c = r - right + 1, b = right - left - 1;if(c >= k)return qsort(nums, right, r, k);else if(b + c >= k) return key;else  return qsort(nums, l, left, k - b - c);}int getRandom(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left) + left];}
};

215. 数组中的第K个最大元素 - 力扣(LeetCode)

6. 库存管理

法一:排序 O(nlogn)

法二:堆排序 O(nlogk)

法三:快速选择算法 O(n)

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};}void qsort(vector<int>& stock,int l, int r, int cnt){if(l == r) return;//1.随机选择基准数int key = getRandom(stock, l, r);//2.根据基准数将数组分成三组int left = l - 1, right = r + 1, i = l;while(i < right){if(stock[i] < key) swap(stock[++left], stock[i++]);else if(stock[i] == key) i++;else swap(stock[--right], stock[i]); }//3.分情况讨论int a = left - l + 1, b = right - left - 1;if(cnt < a) qsort(stock, l, left, cnt);else if(cnt <= a + b) return;else qsort(stock, right, r, cnt - a - b);}int getRandom(vector<int>& stock, int left, int right){int r = rand();return stock[r % (right - left) + left];}
};

相关文章:

利用分治策略优化快速排序

1. 基本思想 分治快速排序&#xff08;Quick Sort&#xff09;是一种基于分治法的排序算法&#xff0c;采用递归的方式将一个数组分割成小的子数组&#xff0c;并通过交换元素来使得每个子数组元素按照特定顺序排列&#xff0c;最终将整个数组排序。 快速排序的基本步骤&#…...

前端工程化的具体实现细节

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…...

数据分析--数据清洗

一、数据清洗的重要性&#xff1a;数据质量决定分析成败 1.1 真实案例警示 电商平台事故&#xff1a;2019年某电商大促期间&#xff0c;因价格数据未清洗导致错误标价&#xff0c;产生3000万元损失医疗数据分析&#xff1a;未清洗的异常血压值&#xff08;如300mmHg&#xff…...

✨1.HTML、CSS 和 JavaScript 是什么?

✨✨ HTML、CSS 和 JavaScript 是构建网页的三大核心技术&#xff0c;它们相互协作&#xff0c;让网页呈现出丰富的内容、精美的样式和交互功能。以下为你详细介绍&#xff1a; &#x1f98b;1. HTML&#xff08;超文本标记语言&#xff09; 定义&#xff1a;HTML 是一种用于描…...

QT--常用对话框

文章目录 前言一、颜色对话框颜色对话框代码解析 二、文本对话框文本对话框代码解析 三、输入对话框1.整型输入对话框2.浮点数输入对话框3.条目对话框 四、提示对话框1.提问对话框2.消息对话框3.警告对话框4.关键对话框 五、进度对话框六、向导对话框总结 前言 今天介绍几种标…...

基于 Ollama 工具的 LLM 大语言模型如何部署,以 DeepSeek 14B 本地部署为例

简简单单 Online zuozuo :本心、输入输出、结果 文章目录 基于 Ollama 工具的 LLM 大语言模型如何部署,以 DeepSeek 14B 本地部署为例前言下载 Ollama实际部署所需的硬件要求设置 LLM 使用 GPU ,发挥 100% GPU 性能Ollama 大模型管理命令大模型的实际运行资源消耗基于 Ollam…...

图的最小生成树算法: Prim算法和Kruskal算法(C++)

上一节我们学习了最短路径算法, 这一节来学习最小生成树. 最小生成树(Minimum Spanning Tree, MST)算法是图论中的一种重要算法, 主要用于在加权无向图中找到一棵生成树, 使得这棵树包含图中的所有顶点, 并且所有边的权重之和最小. 这样的树被称为最小生成树. 最小生成树广泛应…...

WPS的AI助手进化跟踪(灵犀+插件)

Ver V0.0 250216: 如何给WPS安装插件用以支持其他大模型LLM V0.1 250217: WPS的灵犀AI现在是DeepSeek R1(可能是全参数671B) 前言 WPS也有内置的AI&#xff0c;叫灵犀&#xff0c;之前应是自已的LLM模型&#xff0c;只能说是属于“能用&#xff0c;有好过无”&#xff0c;所…...

我用AI做数据分析之数据清洗

我用AI做数据分析之数据清洗 AI与数据分析的融合效果怎样&#xff1f; 这里描述自己在使用AI进行数据分析&#xff08;数据清洗&#xff09;过程中的几个小故事&#xff1a; 1. 变量名的翻译 有一个项目是某医生自己收集的数据&#xff0c;变量名使用的是中文&#xff0c;分…...

一周学会Flask3 Python Web开发-request请求对象与url传参

锋哥原创的Flask3 Python Web开发 Flask3视频教程&#xff1a; 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili request请求对象封装了从客户端发来的请求报文信息&#xff0c;我们可以从中获取所有数据。 request对象包含的常用属性&…...

【ISO 14229-1:2023 UDS诊断(ECU复位0x11服务)测试用例CAPL代码全解析④】

ISO 14229-1:2023 UDS诊断【ECU复位0x11服务】_TestCase04 作者&#xff1a;车端域控测试工程师 更新日期&#xff1a;2025年02月17日 关键词&#xff1a;UDS诊断协议、ECU复位服务、0x11服务、ISO 14229-1:2023 TC11-004测试用例 用例ID测试场景验证要点参考条款预期结果TC…...

网络技术变迁:从IPv4走向IPv6

目录 前言 旧时代产物&#xff1a;IPv4 什么是IPv4&#xff1f; IPv4的工作方式 IPv4的缺点 为什么要从IPv4过渡到IPv6&#xff1f; 走向IPv6&#xff1a;新一代互联网协议 IPv6的技术特性 我们需要过渡技术 双栈&#xff08;Dual Stack&#xff09; 隧道技术&#…...

DeepSeek教unity------事件管理

1. 定义事件类型 定义一个枚举来表示不同类型的事件。组织和识别不同的事件。 2. 创建事件参数类 为了让事件携带数据&#xff0c;创建一个通用的事件参数类或者为每个事件类型创建特定的参数类。 3. 实现事件管理器 创建一个EventManager类&#xff0c;用于管理事件的注册…...

确保设备始终处于最佳运行状态,延长设备的使用寿命,保障系统的稳定运行的智慧地产开源了

智慧地产视觉监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;从而大大减少企业级应用约95%的开发成本。通过计算机视觉和…...

RedisTemplate存储含有特殊字符解决

ERROR信息: 案发时间: 2025-02-18 01:01 案发现场: UserServiceImpl.java 嫌疑人: stringRedisTemplate.opsForValue().set(SystemConstants.LOGIN_CODE_PREFIX phone, code, Duration.ofMinutes(3L)); // 3分钟过期作案动机: stringRedisTemplate继承了Redistemplate 使用的…...

28、深度学习-自学之路-NLP自然语言处理-做一个完形填空,让机器学习更多的内容程序展示

import sys,random,math from collections import Counter import numpy as npnp.random.seed(1) random.seed(1) f open(reviews.txt) raw_reviews f.readlines() f.close()tokens list(map(lambda x:(x.split(" ")),raw_reviews))#wordcnt Counter() 这行代码的…...

【NLP 22、语言模型 language model】

有时候我也想听听&#xff0c;我在你心里&#xff0c;是什么样子 —— 25.1.12 一、什么是语言模型 语言是灵活的&#xff0c;也是有规律的 了解一门语言的人可以判断一句话是否“合理” 通俗来讲&#xff0c;语言模型用来评价一句话(句子可以看作是字的组合)是否“合理”或…...

刚性平衡机建模

这两个公式是动平衡机中用于描述旋转部件振动行为的动力学方程。它们分别描述了旋转部件在平移振动和扭转振动中的运动规律&#xff0c;用于分析不平衡量对系统的影响。以下是详细解释&#xff1a; 1. 第一个公式&#xff1a;平移振动的动力学方程 M d 2 y d t 2 2 K y 0 m 1…...

【算法】双指针(上)

目录 双指针 左右指针(对撞指针) 快慢指针 移动零 双指针解题 复写零 暴力解题 双指针解题(快慢指针) 快乐数 双指针解题(快慢指针) 盛最多水的容器 暴力解题(会超时) 双指针解题(左右指针) 有效三角形的个数 暴力解题 双指针解题(左右指针) 双指针 常见的双指…...

【Linux Redis】关于用docker拉取Redis后,让虚拟机运行起来redis,并使得其可以连接到虚拟机外的navicat。

步骤一&#xff1a;拉取Redis镜像 docker pull redis 这个命令会下载最新版本的Redis镜像到你的本地Docker仓库中。你也可以指定一个具体的版本号&#xff0c;例如docker pull redis:6.2.6&#xff0c;来拉取特定版本的Redis镜像。 如果拉取遇到问题请参考【Linux AnolisOS】关…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...