【JavaScript 算法】快速排序:高效的排序算法


文章目录
- 一、算法原理
- 二、算法实现
- 三、应用场景
- 四、优化与扩展
- 五、总结

快速排序(Quick Sort)是一种高效的排序算法,通过分治法将数组分为较小的子数组,递归地排序子数组。快速排序通常比其他 O(n log n) 算法表现更好,因为它的内部循环可以在大多数架构上被有效地实现。本文将详细介绍快速排序算法的原理、实现及其应用。
一、算法原理
快速排序通过以下步骤实现:
- 选择基准:从数组中选择一个元素作为基准(pivot)。
- 划分数组:将数组分为两部分,一部分的元素都小于基准,另一部分的元素都大于基准。
- 递归排序:对划分后的两部分分别进行快速排序。
- 合并结果:将排序好的两部分合并,得到最终的排序结果。

二、算法实现
以下是快速排序的JavaScript实现:
/*** 快速排序算法* @param {number[]} arr - 需要排序的数组* @return {number[]} - 排序后的数组*/
function quickSort(arr) {if (arr.length <= 1) {return arr; // 基础情况:数组为空或只有一个元素}const pivot = arr[Math.floor(arr.length / 2)]; // 选择基准元素const left = [];const right = [];// 将数组分为小于基准和大于基准的两部分for (let i = 0; i < arr.length; i++) {if (i === Math.floor(arr.length / 2)) continue; // 跳过基准元素if (arr[i] < pivot) {left.push(arr[i]);} else {right.push(arr[i]);}}// 递归排序并合并结果return quickSort(left).concat([pivot], quickSort(right));
}// 示例
const arr = [3, 6, 8, 10, 1, 2, 1];
const sortedArr = quickSort(arr);
console.log(sortedArr); // 输出: [1, 1, 2, 3, 6, 8, 10]
三、应用场景
- 大规模数据排序:快速排序在处理大规模数据时表现优秀。
- 需要高效排序的场景:快速排序通常比其他排序算法更快,适用于需要高效排序的场景。
- 多种数据类型排序:快速排序可以排序各种数据类型,如数字、字符串等。
四、优化与扩展
- 选择基准优化:选择基准的方式可以影响排序效率。常见的优化方法包括三数取中法和随机选择法。
/*** 三数取中法选择基准* 该方法通过选择数组中的三个元素(第一个元素、中间元素和最后一个元素),* 并将它们进行比较,选择其中的中位数作为基准索引,以减少快速排序的最坏情况发生。* @param {number[]} arr - 数组* @return {number} - 基准索引*/
function medianOfThree(arr) {const mid = Math.floor(arr.length / 2); // 计算中间索引const a = arr[0]; // 数组第一个元素const b = arr[mid]; // 数组中间元素const c = arr[arr.length - 1]; // 数组最后一个元素// 比较三个元素,返回中位数对应的索引if ((a > b) !== (a > c)) return 0; // 如果 a 既不是最大也不是最小,返回 0if ((b > a) !== (b > c)) return mid; // 如果 b 既不是最大也不是最小,返回 midreturn arr.length - 1; // 否则返回最后一个元素的索引
}
- 尾递归优化:通过尾递归优化减少栈的深度,提高效率。
/*** 快速排序算法(尾递归优化)* 该算法通过分治法将数组分为较小的子数组,递归地排序子数组。尾递归优化可以减少栈的深度,提高效率。* @param {number[]} arr - 需要排序的数组* @return {number[]} - 排序后的数组*/
function quickSortTailRecursive(arr) {/*** 分区函数* 该函数选择一个基准元素,并将数组分为两部分,一部分小于基准,另一部分大于基准* @param {number[]} arr - 需要排序的数组* @param {number} left - 左边界索引* @param {number} right - 右边界索引* @return {number} - 分区索引*/function partition(arr, left, right) {const pivot = arr[Math.floor((left + right) / 2)]; // 选择中间元素作为基准let i = left; // 初始化左指针let j = right; // 初始化右指针// 左右指针向中间移动,进行分区操作while (i <= j) {while (arr[i] < pivot) i++; // 左指针右移,直到找到大于等于基准的元素while (arr[j] > pivot) j--; // 右指针左移,直到找到小于等于基准的元素if (i <= j) {// 交换左右指针所指向的元素[arr[i], arr[j]] = [arr[j], arr[i]];i++; // 左指针右移j--; // 右指针左移}}return i; // 返回分区索引}/*** 排序函数* 递归地对数组进行排序* @param {number[]} arr - 需要排序的数组* @param {number} left - 左边界索引* @param {number} right - 右边界索引*/function sort(arr, left, right) {if (left >= right) return; // 基础情况:子数组长度为0或1时,停止递归const index = partition(arr, left, right); // 获取分区索引sort(arr, left, index - 1); // 递归排序左子数组sort(arr, index, right); // 递归排序右子数组}sort(arr, 0, arr.length - 1); // 初始调用排序函数,排序整个数组return arr; // 返回排序后的数组
}// 示例
const arr = [3, 6, 8, 10, 1, 2, 1];
const sortedArrTailRecursive = quickSortTailRecursive(arr);
console.log(sortedArrTailRecursive); // 输出: [1, 1, 2, 3, 6, 8, 10]
五、总结
快速排序是一种高效的排序算法,通过分治法将数组分为较小的子数组,递归地排序子数组。理解和掌握快速排序算法对于处理大规模数据和优化程序性能都具有重要意义。希望本文对你理解和应用快速排序有所帮助。
相关文章:
【JavaScript 算法】快速排序:高效的排序算法
🔥 个人主页:空白诗 文章目录 一、算法原理二、算法实现三、应用场景四、优化与扩展五、总结 快速排序(Quick Sort)是一种高效的排序算法,通过分治法将数组分为较小的子数组,递归地排序子数组。快速排序通常…...
Excel如何才能忽略隐藏行进行复制粘贴?
你有没有遇到这样的情况:数据很多,将一些数据隐藏后,进行复制粘贴,结果发现粘贴后的内容仍然将整个数据都显示出来了!那么,Excel如何才能忽略隐藏行进行复制粘贴? 打开你的Excel表格 Excel如何…...
行人越界检测 越线 越界区域 多边形IOU越界判断
行人越界判断 越界判断方式:(1)bbox中心点越界(或自定义)(2)交并比IoU判断 越界类型:(1)越线 (2)越界区域 1.越线判断 bbox中心点xc、…...
「UCD」浅谈蓝湖Figma交互设计对齐
在现代数字产品的设计和开发过程中,选择合适的工具对于提高团队效率和保证产品质量至关重要。本文将从开发和设计两个不同的角度,探讨蓝湖和Figma两款流行工具的优势与不足,并提出结论和建议。 开发研发视角:蓝湖 优点: 清晰的设计规范:蓝湖为开发工程师提供了清晰的设计…...
VUE3 播放RTSP实时、回放(NVR录像机)视频流(使用WebRTC)
1、下载webrtc-streamer,下载的最新window版本 Releases mpromonet/webrtc-streamer GitHub 2、解压下载包 3、webrtc-streamer.exe启动服务 (注意:这里可以通过当前文件夹下用cmd命令webrtc-streamer.exe -o这样占用cpu会很少,…...
[PaddlePaddle飞桨] PaddleOCR-光学字符识别-小模型部署
PaddleOCR的GitHub项目地址 推荐环境: PaddlePaddle > 2.1.2 Python > 3.7 CUDA > 10.1 CUDNN > 7.6pip下载指令: python -m pip install paddlepaddle-gpu2.5.1 -i https://pypi.tuna.tsinghua.edu.cn/simple pip install paddleocr2.7…...
Python应用开发——30天学习Streamlit Python包进行APP的构建(15):优化性能并为应用程序添加状态
Caching and state 优化性能并为应用程序添加状态! Caching 缓存 Streamlit 为数据和全局资源提供了强大的缓存原语。即使从网络加载数据、处理大型数据集或执行昂贵的计算,它们也能让您的应用程序保持高性能。 本页仅包含有关 st.cache_data API 的信息。如需深入了解缓…...
python实现openssl的EVP_BytesToKey及AES_256_CBC加解密算法
python实现openssl EVP_BytesToKey(EVP_aes_256_cbc(), EVP_md5(), NULL, pass, passlen, 1, key, iv); 并实现AES 256 CBC加解密. # encoding:utf-8import base64 from Crypto.Cipher import AES from Crypto import Random from hashlib import md5def EVP_BytesToKey(passw…...
基于SpringBoot+VueJS+微信小程序技术的图书森林共享小程序设计与实现
注:每个学校每个老师对论文的格式要求不一样,故本论文只供参考,本论文页数达到60页以上,字数在6000及以上。 基于SpringBootVueJS微信小程序技术的图书森林共享小程序设计与实现 目录 基于SpringBootVueJS微信小程序技术的图书森…...
【css】image 使用 transform:scale 放大后显示不全的问题
css 可以用 transform: scale(1.2) 实现图片放大 1.2 倍显示的功能,在此基础上可以修改 transform-origin 为用户点击的坐标值优化体验。问题在于 origin 位于图片下方时,图片放大后出现滚动条,而滚动条的高度会忽略放大显示的图片的上半部分…...
损失函数简介
损失函数(Loss Function)是机器学习中用来衡量模型预测值与真实值之间差异的函数。在训练过程中,通过最小化损失函数来优化模型的参数,以提高模型的预测准确性。 以下是损失函数的主要用途和一些常用的损失函数类型: 损失函数的用途: 评估模型性能:损失函数提供了一个…...
2023睿抗CAIP-编程技能赛-本科组省赛(c++)
RC-u1 亚运奖牌榜 模拟 AC: #include<iostream> using namespace std; struct nation{int j,y,t; }a[2]; int main(){int n;cin>>n;for(int i1;i<n;i){int x,y;cin>>x>>y;if(y1) a[x].j;if(y2) a[x].y;if(y3) a[x].t;}cout<<a[0].j<<&…...
现在国内的ddos攻击趋势怎么样?想了解现在ddos的情况该去哪看?
目前,国内的DDoS攻击趋势显示出以下几个特征: 攻击频次显著增加:根据《快快网络2024年DDoS攻击趋势白皮书》,2023年DDoS攻击活动有显著攀升,总攻击次数达到1246.61万次,比前一年增长了18.1%。 攻击强度和规…...
微服务到底是个什么东东?
微服务架构是一种架构模式,它提倡将单一应用程序划分成一组小的服务,服务之间互相协调、互相配合,为用户提供最终价值。 每个服务运行在其独立的进程中,服务和服务间采用轻量级的通信机制互相沟通(通常是基于 HTTP 的…...
C++笔试强训5
文章目录 一、选择题1-5题6-10题 二、编程题题目一题目二 一、选择题 1-5题 x1,先x,再x–,while判断永远为真,故死循环 选D。 sizeof会计算\0,strlen不包括\0,并且strlen只计算\0之前的。 所以sizeof是10,strken是4 …...
初学51单片机之UART串口通信
CSDN其他博主的博文(自用)嵌入式学习笔记9-51单片机UART串口通信_51uart串口通讯-CSDN博客 CSDN其他博主的博文写的蛮好,如果你想了解51单片机UART串口可以点进去看看: UART全称Universal Asynchronous Receiver/Transmitter即通…...
数据结构——查找(线性表的查找与树表的查找)
目录 1.查找 1.查找的基本概念 1.在哪里找? 2.什么查找? 3.查找成功与否? 4.查找的目的是什么? 5.查找表怎么分类? 6.如何评价查找算法? 7.查找的过程中我们要研究什么? 2.线性表…...
MySQL入门学习-深入索引.组合索引
在 MySQL 中,组合索引(也称为复合索引)是在多个列上创建的索引。以下是关于组合索引的详细信息: 一、组合索引的概念: - 组合索引是基于多个列创建的索引结构。它可以提高在这些列上进行查询的效率。 二、深入理解组…...
RABBITMQ的本地测试证书生成脚本
由于小程序要求必须访问wss的接口,因此需要将测试环境也切换到https,看了下官方的文档 RabbitMQ Web STOMP Plugin | RabbitMQ里面有这个信息 然后敲打GPT一阵子,把要求输入几个来回,得到这样一个脚本: generate_cer…...
记录些Redis题集(4)
Redis 通讯协议(RESP) Redis 通讯协议(Redis Serialization Protocol,RESP)是 Redis 服务端与客户端之间进行通信的协议。它是一种二进制安全的文本协议,设计简洁且易于实现。RESP 主要用于支持客户端和服务器之间的请求响应交互…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
