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

三天精通一算法之快速排序

力扣链接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. 排序数组 - 力扣&#xff08;LeetCode&#xff09;注意这题快排不能用递归&#xff0c;否则堆会爆 快速排序&#xff08;Quicksort&#xff09;是一种高效的排序算法&#xff0c;通常使用分治法来将一个列表分成较小的子列表&#xff0c;然后递归地排序这些子列表…...

互联网、物联网的相关标准

互联网的相关标准 网络通信协议&#xff1a; HTTP&#xff08;Hypertext Transfer Protocol&#xff09;&#xff1a;用于在网络中传输文本、图像、音频和视频等数据的协议。它基于请求-响应模型&#xff0c;客户端发送请求给服务器&#xff0c;服务器返回响应。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 引言回顾&#xff1a;DistilBERT模型TinyBERT模型结构TinyBERT模型策略Transformer层蒸馏嵌入层蒸馏预测层蒸馏 TinyBERT模型的训练效果展示 引言 上一节介绍了 DistilBERT \text{DistilBERT} DistilBERT模型&#xff0c;本节将继续介绍优化性更强的知…...

【时间序列预测】基于PyTorch实现CNN_BiLSTM算法

文章目录 1. CNN与BiLSTM2. 完整代码实现3. 代码结构解读3.1 CNN Layer3.2 BiLSTM Layer3.3 Output Layer3.4 forward Layer 4. 应用场景5. 总结 本文将详细介绍如何使用Pytorch实现一个结合卷积神经网络&#xff08;CNN&#xff09;和双向长短期记忆网络&#xff08;BiLSTM&am…...

联想Y7000 2024版本笔记本 RTX4060安装ubuntu22.04双系统及深度学习环境配置

目录 1..制作启动盘 2.Windows 磁盘分区,删除原来ubuntu的启动项 3.四个设置 4.安装ubuntu 5.ubuntu系统配置 1..制作启动盘 先下载镜像文件,注意版本对应。Rufus - 轻松创建 USB 启动盘 用rufus制作时,需要注意选择正确的分区类型和系统类型。不然安装的系统会有问题…...

VuePress学习

1.介绍 VuePress 由两部分组成&#xff1a;第一部分是一个极简静态网站生成器 (opens new window)&#xff0c;它包含由 Vue 驱动的主题系统和插件 API&#xff0c;另一个部分是为书写技术文档而优化的默认主题&#xff0c;它的诞生初衷是为了支持 Vue 及其子项目的文档需求。…...

一次“okhttp访问间隔60秒,提示unexpected end of stream“的问题排查过程

一、现象 okhttp调用某个服务&#xff0c;如果第二次访问间隔上一次访问时间超过60s&#xff0c;返回错误&#xff1a;"unexpected end of stream"。 二、最终定位原因&#xff1a; 空闲连接如果超过60秒&#xff0c;服务端会主动关闭连接。此时客户端恰巧访问了这…...

SQL最佳实践:避免使用COUNT=0

如果你遇到类似下面的 SQL 查询&#xff1a; SELECT * FROM customer c WHERE 0 (SELECT COUNT(*)FROM orders oWHERE o.customer_id c.customer_id);意味着有人没有遵循 SQL 最佳实践。该语句的作用是查找没有下过订单的客户&#xff0c;其中子查询使用了 COUNT 函数统计客…...

PG与ORACLE的差距

首先必须是XID 64&#xff0c;一个在极端环境下会FREEZE的数据库无论如何都无法承担关键业务系统的重任的&#xff0c;我们可以通过各种配置&#xff0c;提升硬件的性能&#xff0c;通过各种IT管控措施来尽可能避免在核心系统上面临FREEZE的风险&#xff0c;不过并不是每个企业…...

树莓派3B+驱动开发(2)- LED驱动(传统模式)

github主页&#xff1a;https://github.com/snqx-lqh 本项目github地址&#xff1a;https://github.com/snqx-lqh/RaspberryPiDriver 本项目硬件地址&#xff1a;https://oshwhub.com/from_zero/shu-mei-pai-kuo-zhan-ban 欢迎交流 笔记说明 如我在驱动开发总览中说的那样&…...

超详细搭建PhpStorm+PhpStudy开发环境

刚开始接触PHP开发&#xff0c;搭建开发环境是第一步&#xff0c;网上下载PhpStorm和PhpStudy软件&#xff0c;怎样安装和激活就不详细说了&#xff0c;我们重点来看一看怎样搭配这两个开发环境。 前提&#xff1a;现在假设你已经安装完PhpStorm和PhpStudy软件。 我的PhpStor…...

分析比对vuex和store模式

在 Vue 中&#xff0c;Vuex 和 store 模式 是两个不同的概念&#xff0c;它们紧密相关&#xff0c;主要用于管理应用的状态。下面我会详细介绍这两个概念&#xff0c;并通过例子帮助你更好地理解。 1. Vuex 是什么&#xff1f; Vuex 是 Vue.js 的一个状态管理库&#xff0c;用…...

C# 网络编程--基础核心内容

在现今软件开发中&#xff0c;网络编程是非常重要的一部分&#xff0c;本文简要介绍下网络编程的概念和实践。 C#网络编程的主要内容包括以下几个方面‌&#xff1a; : 上图引用大佬的图&#xff0c;大家也关注一下&#xff0c;有技术有品质&#xff0c;有国有家&#xff0c;情…...

【C++游戏程序】easyX图形库还原游戏《贪吃蛇大作战》(三)

承接上一篇文章&#xff1a;【C游戏程序】easyX图形库还原游戏《贪吃蛇大作战》&#xff08;二&#xff09;&#xff0c;我们这次来补充一些游戏细节&#xff0c;以及增加吃食物加长角色长度等设定玩法&#xff0c;也是本游戏的最后一篇文章。 一.玩家边界检测 首先是用来检测…...

uni-app H5端使用注意事项 【跨端开发系列】

&#x1f517; uniapp 跨端开发系列文章&#xff1a;&#x1f380;&#x1f380;&#x1f380; uni-app 组成和跨端原理 【跨端开发系列】 uni-app 各端差异注意事项 【跨端开发系列】uni-app 离线本地存储方案 【跨端开发系列】uni-app UI库、框架、组件选型指南 【跨端开…...

SpringBoot中的@Configuration注解

在Spring Boot中&#xff0c;Configuration注解扮演着非常重要的角色&#xff0c;它是Spring框架中用于定义配置类的一个核心注解。以下是Configuration注解的主要作用&#xff1a; 定义配置类&#xff1a; 使用Configuration注解的类表示这是一个配置类&#xff0c;Spring容器…...

十二、路由、生命周期函数

router路由 页面路由指的是在应用程序中实现不同页面之间的跳转,以及数据传递。通过 Router 模块就可以实现这个功能 2.1创建页面 之前是创建的文件,使用路由的时候需要创建页面,步骤略有不同 方法 1:直接右键新建Page(常用)方法 2:单独添加页面并配置2.1.1直接右键新建…...

【蓝桥杯每日一题】X 进制减法

X 进制减法 2024-12-6 蓝桥杯每日一题 X 进制减法 贪心 进制转换 题目大意 进制规定了数字在数位上逢几进一。 XX 进制是一种很神奇的进制, 因为其每一数位的进制并不固定&#xff01;例如说某 种 XX 进制数, 最低数位为二进制, 第二数位为十进制, 第三数位为八进制, 则 XX 进制…...

2026电商客服外包TOP5实力品牌详细解读

进入2026年&#xff0c;电商行业已从粗放式扩张转向精细化运营时代&#xff0c;客户服务不再局限于简单的问答回复&#xff0c;而是成为驱动店铺销售增长、积累品牌声誉的关键要素。根据最新行业研究报告&#xff0c;专业的外包客服团队能够帮助店铺将询单转化率提高20%-30%&am…...

Qt新手必看:MinGW和MSVC构建套件到底怎么选?保姆级对比指南

Qt构建套件选择指南&#xff1a;MinGW与MSVC深度对比与实战决策 刚接触Qt开发的初学者&#xff0c;往往在配置开发环境的第一步就陷入选择困难——面对MinGW和MSVC这两个构建套件选项&#xff0c;究竟该如何抉择&#xff1f;这个看似简单的选择背后&#xff0c;实则关系到后续开…...

同花顺期货通指标编写指南:从零开始构建趋势波段共振系统(含避坑技巧)

同花顺期货通指标编写指南&#xff1a;从零开始构建趋势波段共振系统&#xff08;含避坑技巧&#xff09; 在期货交易中&#xff0c;技术指标是交易者不可或缺的分析工具。同花顺期货通作为国内主流的期货交易软件&#xff0c;其内置的指标编写功能为交易者提供了强大的自定义能…...

游戏资源解密工具:RPG Maker Decrypter零基础使用指南

游戏资源解密工具&#xff1a;RPG Maker Decrypter零基础使用指南 【免费下载链接】RPGMakerDecrypter Tool for extracting RPG Maker XP, VX and VX Ace encrypted archives. 项目地址: https://gitcode.com/gh_mirrors/rp/RPGMakerDecrypter RPG Maker Decrypter 是一…...

手把手教你用Python+AI大模型,把Yapi接口文档变成自动化测试脚本(附避坑指南)

用Python与大模型实现Yapi接口自动化测试的工程化实践 在中小型技术团队中&#xff0c;接口测试往往是质量保障的薄弱环节。传统手工编写测试用例的方式不仅耗时耗力&#xff0c;更难以应对快速迭代的开发节奏。本文将分享如何利用Python生态与AI大模型能力&#xff0c;将Yapi平…...

告别代码恐惧!用KRobot图形化编程,10分钟搞定Arduino巡线小车(附完整接线图)

零代码玩转Arduino巡线小车&#xff1a;KRobot图形化编程全攻略 第一次接触Arduino时&#xff0c;看到满屏的C代码是不是头皮发麻&#xff1f;作为教育工作者或创客爱好者&#xff0c;你可能更希望把时间花在创意实现上&#xff0c;而不是纠结于语法错误。现在&#xff0c;通过…...

UNet全维度改进模型库重磅发布

突破边界&#xff0c;赋能工业质检&#xff1a;UNet全维度改进模型库重磅发布 在工业缺陷检测领域&#xff0c;分割精度与效率的平衡始终是技术落地的核心命题。我们倾力打造**「UNet全维度改进模型库」&#xff0c;以37项原创性结构创新为引擎&#xff0c;深度融合注意力机制…...

消费级GPU福音:OpenClaw+百川2-13B量化版显存占用实测

消费级GPU福音&#xff1a;OpenClaw百川2-13B量化版显存占用实测 1. 为什么关注显存占用&#xff1f; 去年折腾大模型本地部署时&#xff0c;最头疼的就是显存问题。我的RTX3060显卡只有12GB显存&#xff0c;跑Llama2-13B原版模型时&#xff0c;加载阶段就直接爆显存。直到发…...

别再死磕EKF了!用ESKF搞定无人机姿态估计,避开‘大数吃小数’的坑

无人机姿态估计实战&#xff1a;用ESKF避开EKF的数值陷阱 四轴飞行器在高速翻滚时&#xff0c;IMU数据突然出现剧烈抖动——这是去年调试自主无人机时遇到的真实场景。当时使用传统EKF算法&#xff0c;姿态解算在极端机动下频繁发散&#xff0c;直到切换到误差状态卡尔曼滤波&a…...

为什么每次招人,企业HR和管理者心里都没底?招错人会带来哪些严重后果?

这是众多企业面临的招聘痛点。根据行业数据&#xff0c;企业招错一名员工的平均成本高达该员工年薪的30%-150%&#xff0c;不仅造成直接经济损失&#xff0c;更会导致团队效率下降、管理成本增加、项目延期等一系列连锁反应。许多企业陷入"招聘-试用-不合适-再招聘"的…...