【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 主要用于支持客户端和服务器之间的请求响应交互…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
