【算法系列篇】分冶-快排

在这里插入图片描述

文章目录

  • 前言
  • 什么是分冶
  • 1.颜色分类
    • 1.1 题目要求
    • 1.2 做题思路
    • 1.3 Java代码实现
  • 2. 排序数组
    • 2.1 题目要求
    • 2.2 做题思路
    • 2.3 Java代码实现
  • 3.数组中的第k个最大元素
    • 3.1 题目要求
    • 3.2 做题思路
    • 3.3 Java代码实现
  • 4. 最小的k个数
    • 4.1 题目要求
    • 4.2 做题思路
    • 4.3 Java代码实现
  • 总结

前言

我相信看到这里很多人都学过八大排序了吧,其中快速排序是一种非常高效的排序方式,那么今天我们将会使用快速排序的算法来解决实际生活中的某些问题。

什么是分冶

分治算法是一种算法设计策略,它将大问题分解成更小的子问题,并通过解决子问题来解决原始问题。分治算法的基本思想是将问题分解成若干个规模较小但结构与原问题相似的子问题,然后递归地解决这些子问题,最后再将子问题的解合并得到原问题的解。

一般而言,分治算法可以分为三个步骤:

  1. 分解(Divide):将原问题划分成若干个规模较小且相互独立的子问题,通常通过递归方式实现。

  2. 解决(Conquer):递归地解决子问题。如果子问题的规模足够小,无需继续分解,直接求解并返回结果。

  3. 合并(Merge):将子问题的解合并成原问题的解。这一步骤通常涉及对子问题解的操作,以得到原问题的解。

分治算法的典型应用包括排序算法(如快速排序和归并排序)、查找算法(如二分查找)、图算法(如最大子数组和、最短路径问题)等。

分治算法的优点在于它能够高效地解决某些复杂问题,尤其适用于可以被划分为多个子问题的情况。通过将问题分解为更小的子问题,分治算法可以减少问题的规模,简化问题的解决过程。

然而,需要注意的是,并非所有问题都适合采用分治算法。在使用分治算法时,需要保证子问题相对独立且可以有效地解决。此外,分治算法在涉及大量递归调用时可能会带来额外的开销,因此在设计算法时需要注意递归深度与性能之间的平衡。

我们今天使用的快速排序的算法则是很好的利用了分冶将大事化小的思想来解决问题的,将整个数组分为若干小区间来进行排序,最终得到我们想要的结果。

1.颜色分类

https://leetcode.cn/problems/sort-colors/

1.1 题目要求

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1:

输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]

示例 2:

输入:nums = [2,0,1]
输出:[0,1,2]

提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶:

你能想出一个仅使用常数空间的一趟扫描算法吗?

class Solution {public void sortColors(int[] nums) {}
}

1.2 做题思路

前面学习的快速排序,每一趟排序过程会以一个数为基准,使最终结果这个基准值的左边小于等于这个基准值,右边部分都是大于这个基准值,所以这个题目我们同样可以使用这种快排的思想,以1为基准,然后用 i 来遍历数组,left 指针以及 left 指针左边都是0,right 指针以及 right 指针右边部分都是2。left 一开始的位置指向 -1,right 指针指向 n(数组大小),当 i 所指向的数据小于 1 的时候,就先将 left++ ,然后将left 所指的内容与 i 所指的内容交换位置,交换结束之后,i++;如果 i 所指向的内容等于 1 的之后,直接i++;如果 i 指向的内容大于 1 ,则先需要将 right–,然后交换right 与 i 所指向的内容,但是这里交换完成之后,i 不能++,因为与 right 指向的内容交换位置之后,i 所指向的内容是 i 没有遍历过的,如果 i++,那么这个数字将会被跳过。
在这里插入图片描述

1.3 Java代码实现

class Solution {private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}public void sortColors(int[] nums) {int n = nums.length;int left = -1,right = n,i = 0;while(i < right) {if(nums[i] < 1) swap(nums,++left,i++);else if(nums[i] == 1) i++;else swap(nums,--right,i);}}
}

在这里插入图片描述

2. 排序数组

https://leetcode.cn/problems/sort-an-array/

2.1 题目要求

给你一个整数数组 nums,请你将该数组升序排列。

示例 1:

输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104
class Solution {public int[] sortArray(int[] nums) {}
}

2.2 做题思路

这道题就很简单明了,直接将数组进行升序排序,我们可以使用分冶的思想,讲整个数组分为 n 个部分,然后在这 n 个小部分中使用快排的思想进行排序,需要注意的是,如果数组趋于有序的话,快速排序的时间复杂度会下降到 O(N^2) ,所以我们可以对快速排序进行优化,优化的方式有很多:三数取中等等,这里我们使用的方式是随机取基准值的方法吗,这样能使快排的时间复杂度基本趋于 O(N*logN)。

2.3 Java代码实现

class Solution {public int[] sortArray(int[] nums) {qsort(nums,0,nums.length-1);return nums;}private void qsort(int[] nums, int l, int r) {if(l >= r) return; //递归结束的条件int left = l-1,right = r + 1, i = l;//在[l,r]区间内,随机取一个数作为基准值int key = nums[new Random().nextInt(r - l + 1) + l];while(i < right) {if(nums[i] < key) swap(nums,++left,i++);else if(nums[i] == key) i++;else swap(nums,--right,i);}//当将基准值排序到最终位置之后,还需要将基准位置左右两边部分继续排序qsort(nums,l,left);qsort(nums,right,r);}private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

在这里插入图片描述

3.数组中的第k个最大元素

https://leetcode.cn/problems/kth-largest-element-in-an-array/

3.1 题目要求

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104
class Solution {public int findKthLargest(int[] nums, int k) {}
}

3.2 做题思路

要想找到数组中的第k个最大元素,我们能想到的还是将数组进行排序,然后从大到小找到第k个元素。这道题目可以使用堆排序,创建出大小为 k 的小根堆。但是我们不使用堆排序的方法,而是使用分冶-快排的方法来解决。如何使用快排的方式来解决呢?同样是先找一个元素作为基准值,进行快排,将数组分为 a——小于基准值的部分、b——等于基准值的部分和c——大于基准值的部分,因为要找到第 k 个最大的元素,所以首先我们需要在大于基准的部分中找这个元素是否存在,如果 c 部分的长度大于等于 k ,则说明这个部分中存在第 k 大的元素,然后我们在这个部分中继续寻找;如果 c 的长度小于 k ,并且 b + c 的长度大于等于 k,那么我们可以直接返回 b 部分的元素,因为 c 部分的长度小于 k ,所以这个第 k 大的元素存在于 b 部分,而 b 部分都是等于基准值的部分,可以直接返回;如果前面两种情况都不存在,那么这个第 k 大的元素就在 a 部分,我们需要在 a 部分中找到第 k - b - c 大的元素,这个操作跟前面的递归操作类似。

在这里插入图片描述

3.3 Java代码实现

class Solution {public int findKthLargest(int[] nums, int k) {return qsort(nums,0,nums.length-1,k);}private int qsort(int[] nums, int l, int r, int k) {int key = nums[new Random().nextInt(r - l + 1) + l];int left = l-1, right = r + 1, i = l;while(i < right) {if(nums[i] < key) swap(nums,++left,i++);else if(nums[i] == key) i++;else swap(nums,--right,i);}//c表示大于key的部分,b表示等于key的部分,剩下的部分就是小于key的部分int c = r - right + 1;int 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);}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

在这里插入图片描述

4. 最小的k个数

https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/

4.1 题目要求

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:

输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]

示例 2:

输入:arr = [0,1,2,1], k = 1
输出:[0]

限制:

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000
class Solution {public int[] getLeastNumbers(int[] arr, int k) {}
}

4.2 做题思路

因为这道题目没有要求要按照元素的大小顺序返回,所以我们可以模仿上面的第 k 个最大元素的思路进行分冶-快排的算法,对数组进行简单的排序,并且将数组分为:a——小于基准值的部分,b——等于基准值的部分,c——大于基准值的部分。
如果a > k,则需要在 a 部分中继续递归,找到最小的 k 个数;如果a <= k,但是 a + b >= k ,因为 b 部分都是相等的数据,所以可以直接返回;如果前面两种情况都不符合的话,就还需要在 c 部分中继续进行排序,直到在 c 部分中找到 第k - a -b小的元素,然后该位置之前的部分就是我们需要的最小的 k 个数。

4.3 Java代码实现

class Solution {public int[] getLeastNumbers(int[] nums, int k) {qsort(nums,0,nums.length-1,k);int[] ret = new int[k];for(int i = 0; i < k; i++) ret[i] = nums[i];return ret;}private void qsort(int[] nums, int l, int r, int k) {int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1,i = l;while(i < right) {if(nums[i] < key) swap(nums,++left,i++);else if(nums[i] == key) i++;else swap(nums,--right,i);}int a = left - l + 1,b = right - left - 1;if(a > k) qsort(nums,l,left,k);else if(a + b >= k) return;else qsort(nums,right,r,k - a - b);}private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

在这里插入图片描述

总结

通过本篇博客,我们深入了解了分治算法以及其在快速排序算法中的应用。快速排序是一种高效的排序算法,它利用了分治策略,将大问题逐步分解为规模较小的子问题,并通过递归地解决和合并子问题来完成整个排序过程。

快速排序算法的核心思想是选择一个基准元素,将待排序数组分割成两个子数组,一个小于等于基准的子数组和一个大于基准的子数组。然后,递归地对两个子数组进行排序,最后合并得到最终的有序数组。

快速排序算法具有以下优点:

  1. 高效性:快速排序算法的平均时间复杂度为O(nlogn),在实际应用中表现出良好的性能。它通过不断地将数组划分为较小的子数组进行排序,从而减少了比较和交换的次数。

  2. 原地排序:快速排序算法可以在原数组上进行排序,不需要额外的辅助空间。这对于内存受限的环境来说具有重要意义。

然而,快速排序算法也存在一些注意事项和局限性:

  1. 对于初始数组的选择敏感:快速排序算法的性能高度依赖于选择的基准元素。最理想的情况是选择一个能够将数组划分成大小相似的子数组的基准元素,以避免出现最坏情况的时间复杂度。

  2. 递归深度:在快速排序算法中,递归调用的深度取决于划分操作的方式和基准元素的选择。当数组中存在大量重复元素时,可能会导致递归深度增加,影响算法的性能。

总结而言,快速排序算法是一种高效、原地排序的算法,通过分治策略实现了对待排序数组的快速排序。它在实践中被广泛使用,具有较好的性能。然而,需要根据具体问题选择合适的基准元素,并考虑递归深度对算法性能的影响。

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

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

相关文章

设计模式之代理模式与外观模式

目录 代理模式 简介 优缺点 角色职责 实现 运用场景 外观模式 简介 角色职责 优缺点 实现 使用场景 代理模式 简介 由于某些原因需要给某对象提供一个代理以控制对该对象的访问。这时&#xff0c;访问对象不适合或者不能直接引用目标对象&#xff0c;代理对象作为…

iOS系统下轻松构建自动化数据收集流程

在当今信息爆炸的时代&#xff0c;我们经常需要从各种渠道获取大量的数据。然而&#xff0c;手动收集这些数据不仅耗费时间和精力&#xff0c;还容易出错。幸运的是&#xff0c;在现代科技发展中有两个强大工具可以帮助我们解决这一问题——Python编程语言和iOS设备上预装的Sho…

知识图谱项目实践

目录 步骤 SpaCy Textacy——Text Analysis for Cybersecurity Networkx Dateparser 导入库 写出页面的名称 ​编辑 自然语言处理 词性标注 可能标记的完整列表 依存句法分析&#xff08;Dependency Parsing&#xff0c;DEP&#xff09; 可能的标签完整列表 实例理…

Web自动化 —— Selenium元素定位与防踩坑

1. 基本元素定位一 from selenium import webdriver from selenium.webdriver.chrome.service import Service from selenium.webdriver.common.by import By # selenium Service("../../chromedriver.exe") # driver webdriver.Chrome(serviceService) # driver.…

【Linux】进程概念

文章目录 一.进程1.概念2.描述进程——pcb3.pcb&#xff08;task_struct&#xff09;内容分类4.查看进程&#xff08;1&#xff09;通过系统调用查看&#xff08;2&#xff09;通过ps命令查看 二.通过系统调用获取进程的PID和PPID三.通过系统调用创建子进程fork()1.fork函数创建…

锁( ReentrantLock,Synchronized)

1.lock和synchronized 语法层面 synchronized 是关键字&#xff0c;源码在 jvm 中&#xff0c;用 c 语言实现&#xff1b; Lock 是接口&#xff0c;源码由 jdk 提供&#xff0c;用 java 语言实现&#xff1b; 使用 synchronized 时&#xff0c;退出同步代码块锁会自动释放&…

Axure RP PC电商平台Web端交互原型模板

Axure RP PC电商平台Web端交互原型模板。原型图内容齐全&#xff0c;包含了用户中心、会员中心、优惠券、积分、互动社区、运营推广、内容推荐、商品展示、订单流程、订单管理、售后及服务等完整的电商体系功能架构和业务流程。 在设计尺寸方面&#xff0c;本套模板按照主流的…

MybatisPlus 核心功能 条件构造器 自定义SQL Service接口 静态工具

MybatisPlus 快速入门 常见注解 配置_软工菜鸡的博客-CSDN博客 2.核心功能 刚才的案例中都是以id为条件的简单CRUD&#xff0c;一些复杂条件的SQL语句就要用到一些更高级的功能了。 2.1.条件构造器 除了新增以外&#xff0c;修改、删除、查询的SQL语句都需要指定where条件。因此…

12. 微积分 - 梯度积分

Hi,大家好。我是茶桁。 上一节课,我们讲了方向导数,并且在最后留了个小尾巴,是什么呢?就是梯度。 我们再来回看一下但是的这个式子: [ f x f y

打造西南交通感知新范式,闪马智能携手首讯科技落地创新中心

9月4日&#xff0c;2023年中国国际智能产业博览会&#xff08;以下简称“智博会”&#xff09;在重庆拉开帷幕。大会期间&#xff0c;由上海闪马智能科技有限公司&#xff08;以下简称“闪马智能”&#xff09;与重庆首讯科技股份有限公司&#xff08;以下简称“首讯科技”&…

Logback日志记录只在控制台输出sql,未写入日志文件【解决】

原因&#xff1a;持久层框架对于Log接口实现方式不一样&#xff0c;日记记录的位置及展示方式也也不一样 mybatis-plus:configuration:log-impl: org.apache.ibatis.logging.stdout.StdOutImpl # sql只会打印到控制台不会输出到日志文件种mybatis-plus:configuration:log-impl…

前后端项目部署上线详细笔记

部署 参考文章&#xff1a;如何部署网站&#xff1f;来比比谁的方法多 - 哔哩哔哩大家好&#xff0c;我是鱼皮&#xff0c;不知道朋友们有没有试着部署过自己开发的网站呢&#xff1f;其实部署网站非常简单&#xff0c;而且有非常多的花样。这篇文章就给大家分享几种主流的前端…

DVWA失效的访问控制

失效的访问控制&#xff0c;可以认为是系统对一些功能进行了访问或权限限制&#xff0c;但因为种种原因&#xff0c;限制并没有生效&#xff0c;造成失效的访问控制漏洞,比如越权等 这里以DVWA为例&#xff0c;先访问低难度的命令执行并抓包 删除cookie&#xff0c;并在请求头…

从0到1学会Git(第二部分):Git的本地操作和管理

写在前面:本文介绍了在本地仓库进行文件的处理以及本地的合并等操作。 前置知识:文件可以处在三个区域&#xff0c;分别为工作区&#xff0c;暂存区和本地仓库&#xff0c;我们此文的目标即是将文件存储在本地仓库中。我们可以将文件的区域理解为&#xff0c;cpu中&#xff0c…

UDP和TCP协议报文格式详解

在初识网络原理(初识网络原理_蜡笔小心眼子&#xff01;的博客-CSDN博客)这篇博客中,我们简单的了解了一下TCP/IP五层网络模型,这篇博客将详细的学习一下五层网络模型中传输层的两个著名协议:UDP和TCP 目录 一, 传输层的作用 二, UDP 1,UDP协议的特点 2,UDP报文格式 三, TC…

Python爬取天气数据并进行分析与预测

随着全球气候的不断变化&#xff0c;对于天气数据的获取、分析和预测显得越来越重要。本文将介绍如何使用Python编写一个简单而强大的天气数据爬虫&#xff0c;并结合相关库实现对历史和当前天气数据进行分析以及未来趋势预测。 1 、数据源选择 选择可靠丰富的公开API或网站作…

视频监控/视频汇聚/视频云存储EasyCVR平台接入华为ivs3800平台提示400报错,该如何解决?

开源EasyDarwin视频监控TSINGSEE青犀视频平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;视频云存储/安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多路视频…

垃圾回收 - 复制算法

GC复制算法是Marvin L.Minsky在1963年研究出来的算法。说简单点&#xff0c;就是只把某个空间的活动对象复制到其它空间&#xff0c;把原空间里的所有对象都回收掉。这是一个大胆的想法。在此&#xff0c;我们将复制活动对象的原空间称为From空间&#xff0c;将粘贴活动对象的新…

Flink---1、概述、快速上手

1、Flink概述 1.1 Flink是什么 Flink的官网主页地址&#xff1a;https://flink.apache.org/ Flink的核心目标是“数据流上有状态的计算”(Stateful Computations over Data Streams)。 具体说明&#xff1a;Apache Flink是一个“框架和分布式处理引擎”&#xff0c;用于对无界…

面试总结 - 计算机网络

计算机网络 1 OSI 七层模型 | TCP与UDP | 响应状态码 OSI 模型 应用层: 计算机用户&#xff0c;以及各种应用程序和网络之间的接口&#xff0c;其功能是直接向用户提供服务&#xff0c;完成用户希望在网络上完成的各种工作。 HTTP SMTP FTP DNS 表示层: 负责数据格式的转换&…