三天精通一算法之快速排序
力扣链接912. 排序数组 - 力扣(LeetCode)注意这题快排不能用递归,否则堆会爆
快速排序(Quicksort)是一种高效的排序算法,通常使用分治法来将一个列表分成较小的子列表,然后递归地排序这些子列表。以下是用 JavaScript 实现快速排序的几种方式:
### 方法一:标准递归实现
```javascript
function quickSort(arr) {
// 如果数组长度小于等于1,则直接返回(已排序)
if (arr.length <= 1) {
return arr;
}
// 选择基准元素(这里选择中间元素)
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
// 定义左右两个数组
const left = [];
const right = [];
// 遍历数组(跳过基准元素),根据与基准元素的比较结果放入left或right
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) continue; // 跳过基准元素
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 递归调用quickSort并合并结果
return [...quickSort(left), pivot, ...quickSort(right)];
}
// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```
### 方法二:原地排序(in-place)
这种方法不需要额外的空间来存储 `left` 和 `right` 数组,而是通过交换元素在原数组上进行排序。
```javascript
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) {
return arr;
}
// 分区函数,返回分区点索引
function partition(arr, left, right) {
const pivot = arr[right]; // 选择最右边的元素作为基准
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]]; // 交换
i++;
}
}
// 将基准元素放到正确的位置
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
// 获取分区点
const pivotIndex = partition(arr, left, right);
// 递归对左右两部分进行排序
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
return arr;
}
// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSortInPlace(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```
### 方法三:随机化快速排序
为了减少最坏情况的发生概率(例如当输入已经是排序好的数组时),可以选择一个随机的基准元素来进行分区。
```javascript
function quickSortRandomized(arr, left = 0, right = arr.length - 1) {
if (left >= right) {
return arr;
}
function partition(arr, left, right) {
const randomPivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
[arr[randomPivotIndex], arr[right]] = [arr[right], arr[randomPivotIndex]]; // 交换随机基准到末尾
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]]; // 交换
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]]; // 将基准元素放到正确的位置
return i;
}
const pivotIndex = partition(arr, left, right);
quickSortRandomized(arr, left, pivotIndex - 1);
quickSortRandomized(arr, pivotIndex + 1, right);
return arr;
}
// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSortRandomized(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```
这三种方法展示了不同的快速排序实现方式。第一种是最简单的递归实现,第二种是更高效的原地排序,而第三种则是引入了随机化以提高性能稳定性。你可以根据具体需求选择最适合的方法。
相关文章:
三天精通一算法之快速排序
力扣链接912. 排序数组 - 力扣(LeetCode)注意这题快排不能用递归,否则堆会爆 快速排序(Quicksort)是一种高效的排序算法,通常使用分治法来将一个列表分成较小的子列表,然后递归地排序这些子列表…...
互联网、物联网的相关标准
互联网的相关标准 网络通信协议: HTTP(Hypertext Transfer Protocol):用于在网络中传输文本、图像、音频和视频等数据的协议。它基于请求-响应模型,客户端发送请求给服务器,服务器返回响应。HTTPS&a…...
Linux题库及答案
填空题 1. 建立用户账号的命令是__useradd________。 2. 修改账号密码的命令是__passwd________。 3. 更改用户密码过期信息的命令是__chage________。 4. 创建一个新组的命令是___groupadd_______。 5. 用于在不注销的情况下切换到系统中的另一个用户的命令是___su_…...
Android 镜像模式和扩展模式区别探讨-Android14
Android 镜像模式和扩展模式区别探讨 1、区分镜像模式和扩展模式1.1 扩展屏是否有显示内容1.2 镜像模式显示条件 2、镜像模式界面 同屏显示和异屏显示探讨DisplayManagerService启动及主屏添加-Android13 Android主副屏显示-Android14 1、区分镜像模式和扩展模式 LogicalDispla…...
深度学习笔记之BERT(五)TinyBERT
深度学习笔记之TinyBERT 引言回顾:DistilBERT模型TinyBERT模型结构TinyBERT模型策略Transformer层蒸馏嵌入层蒸馏预测层蒸馏 TinyBERT模型的训练效果展示 引言 上一节介绍了 DistilBERT \text{DistilBERT} DistilBERT模型,本节将继续介绍优化性更强的知…...
【时间序列预测】基于PyTorch实现CNN_BiLSTM算法
文章目录 1. CNN与BiLSTM2. 完整代码实现3. 代码结构解读3.1 CNN Layer3.2 BiLSTM Layer3.3 Output Layer3.4 forward Layer 4. 应用场景5. 总结 本文将详细介绍如何使用Pytorch实现一个结合卷积神经网络(CNN)和双向长短期记忆网络(BiLSTM&am…...
联想Y7000 2024版本笔记本 RTX4060安装ubuntu22.04双系统及深度学习环境配置
目录 1..制作启动盘 2.Windows 磁盘分区,删除原来ubuntu的启动项 3.四个设置 4.安装ubuntu 5.ubuntu系统配置 1..制作启动盘 先下载镜像文件,注意版本对应。Rufus - 轻松创建 USB 启动盘 用rufus制作时,需要注意选择正确的分区类型和系统类型。不然安装的系统会有问题…...
VuePress学习
1.介绍 VuePress 由两部分组成:第一部分是一个极简静态网站生成器 (opens new window),它包含由 Vue 驱动的主题系统和插件 API,另一个部分是为书写技术文档而优化的默认主题,它的诞生初衷是为了支持 Vue 及其子项目的文档需求。…...
一次“okhttp访问间隔60秒,提示unexpected end of stream“的问题排查过程
一、现象 okhttp调用某个服务,如果第二次访问间隔上一次访问时间超过60s,返回错误:"unexpected end of stream"。 二、最终定位原因: 空闲连接如果超过60秒,服务端会主动关闭连接。此时客户端恰巧访问了这…...
SQL最佳实践:避免使用COUNT=0
如果你遇到类似下面的 SQL 查询: SELECT * FROM customer c WHERE 0 (SELECT COUNT(*)FROM orders oWHERE o.customer_id c.customer_id);意味着有人没有遵循 SQL 最佳实践。该语句的作用是查找没有下过订单的客户,其中子查询使用了 COUNT 函数统计客…...
PG与ORACLE的差距
首先必须是XID 64,一个在极端环境下会FREEZE的数据库无论如何都无法承担关键业务系统的重任的,我们可以通过各种配置,提升硬件的性能,通过各种IT管控措施来尽可能避免在核心系统上面临FREEZE的风险,不过并不是每个企业…...
树莓派3B+驱动开发(2)- LED驱动(传统模式)
github主页:https://github.com/snqx-lqh 本项目github地址:https://github.com/snqx-lqh/RaspberryPiDriver 本项目硬件地址:https://oshwhub.com/from_zero/shu-mei-pai-kuo-zhan-ban 欢迎交流 笔记说明 如我在驱动开发总览中说的那样&…...
超详细搭建PhpStorm+PhpStudy开发环境
刚开始接触PHP开发,搭建开发环境是第一步,网上下载PhpStorm和PhpStudy软件,怎样安装和激活就不详细说了,我们重点来看一看怎样搭配这两个开发环境。 前提:现在假设你已经安装完PhpStorm和PhpStudy软件。 我的PhpStor…...
分析比对vuex和store模式
在 Vue 中,Vuex 和 store 模式 是两个不同的概念,它们紧密相关,主要用于管理应用的状态。下面我会详细介绍这两个概念,并通过例子帮助你更好地理解。 1. Vuex 是什么? Vuex 是 Vue.js 的一个状态管理库,用…...
C# 网络编程--基础核心内容
在现今软件开发中,网络编程是非常重要的一部分,本文简要介绍下网络编程的概念和实践。 C#网络编程的主要内容包括以下几个方面: : 上图引用大佬的图,大家也关注一下,有技术有品质,有国有家,情…...
【C++游戏程序】easyX图形库还原游戏《贪吃蛇大作战》(三)
承接上一篇文章:【C游戏程序】easyX图形库还原游戏《贪吃蛇大作战》(二),我们这次来补充一些游戏细节,以及增加吃食物加长角色长度等设定玩法,也是本游戏的最后一篇文章。 一.玩家边界检测 首先是用来检测…...
uni-app H5端使用注意事项 【跨端开发系列】
🔗 uniapp 跨端开发系列文章:🎀🎀🎀 uni-app 组成和跨端原理 【跨端开发系列】 uni-app 各端差异注意事项 【跨端开发系列】uni-app 离线本地存储方案 【跨端开发系列】uni-app UI库、框架、组件选型指南 【跨端开…...
SpringBoot中的@Configuration注解
在Spring Boot中,Configuration注解扮演着非常重要的角色,它是Spring框架中用于定义配置类的一个核心注解。以下是Configuration注解的主要作用: 定义配置类: 使用Configuration注解的类表示这是一个配置类,Spring容器…...
十二、路由、生命周期函数
router路由 页面路由指的是在应用程序中实现不同页面之间的跳转,以及数据传递。通过 Router 模块就可以实现这个功能 2.1创建页面 之前是创建的文件,使用路由的时候需要创建页面,步骤略有不同 方法 1:直接右键新建Page(常用)方法 2:单独添加页面并配置2.1.1直接右键新建…...
【蓝桥杯每日一题】X 进制减法
X 进制减法 2024-12-6 蓝桥杯每日一题 X 进制减法 贪心 进制转换 题目大意 进制规定了数字在数位上逢几进一。 XX 进制是一种很神奇的进制, 因为其每一数位的进制并不固定!例如说某 种 XX 进制数, 最低数位为二进制, 第二数位为十进制, 第三数位为八进制, 则 XX 进制…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
