排序基础-快排三路快排

三路快排

1. 回忆快排

快排的核心思想是,每次选取一个基准值,然后将数组分成两部分,一部分小于基准值,一部分大于基准值,然后递归处理这两部分。


class Solution:

    # 快速排序
    def paviot(self,nums:List[int],lo:int,hi:int):
		# 随机选取一个值作为pivot,避免退化为O(n^2)         
        i = random.randint(lo,hi) 
        nums[i],nums[hi] = nums[hi],nums[i] 

        pivot = nums[hi]
        less = great = lo
        while(great < hi):
            if nums[great] < pivot:  # 如果当前值小于pivot(pivot为最后一个值)
                nums[less],nums[great] = nums[great],nums[less] # 如果存在大量重复值,这里会导致大量交换,导致超时
                less += 1
            great += 1
        nums[less],nums[hi] = nums[hi],nums[less]
        return less
    
    def quickSort(self,nums:List[int],lo:int,hi:int):
        if lo > hi:return
        index = self.paviot(nums,lo,hi)
        self.quickSort(nums,lo,index-1)
        self.quickSort(nums,index+1,hi)

    def sortArray(self, nums: List[int]) -> List[int]:
        self.quickSort(nums,0,len(nums)-1)
        return nums

  • 快排在处理大量重复值的时候,会导致大量的交换,导致超时。
  • 如果数组本身就是有序的,那么快排的时间复杂度会退化到O(n^2)。

2. 三路快排

三路快排的核心思想是,每次选取一个基准值,然后将数组分成三部分,一部分小于基准值,一部分大于基准值,一部分等于基准值,然后递归处理这三部分。

相比于快排,三路快排在处理大量重复值的时候,不会导致大量的交换,因此不会导致超时。


from cn.Python3.mod.preImport import *
import random
# @test([5,2,3,1])=[1,2,3,5]
# @test([5,1,1,2,0,0])=[0,0,1,1,2,5]
class Solution:

    # 三路快排
    
    def threeway_quick_sort(self,nums:List[int],lo:int,hi:int):
        if lo >= hi:return
        j = random.randint(lo,hi)
        nums[j],nums[hi] = nums[hi],nums[j]
        pivot = nums[hi]
        
        i = lo
        less = lo
        great = hi
        while(i<=great):
            if nums[i] < pivot:
                nums[i],nums[less] = nums[less],nums[i]
                less += 1
                i += 1
            elif nums[i] > pivot:
                nums[i],nums[great] = nums[great],nums[i]
                great -= 1
            else:
                i += 1
        self.threeway_quick_sort(nums,lo,less-1)
        self.threeway_quick_sort(nums,great+1,hi)
    
    def sortArray(self, nums: List[int]) -> List[int]:
        self.threeway_quick_sort(nums,0,len(nums)-1)
        return nums

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Ansys】什么软件模块是DS,它和workbench、mechanical的区别在哪里?

一、DesignSpace和workbench 早期的Workbench称之为DesignSpace&#xff0c;更偏向于建模。 现在DS是license的一种&#xff0c;而分析的模块在11中称之为Simulation&#xff08;Design Simulation&#xff09;&#xff0c;在12中改名为Mechanical。 所以&#xff0c;你可以…

IFPUG功能点度量4:度量事务功能

一、基本概念 1、事务功能 事务功能是处理数据功能的基本过程。 每个事务功能都是一个基本过程。 事务功能由多个逻辑处理来完成。 事务功能包含三种类型&#xff1a;EI、EO、EQ 2、基本过程 一个基本过程是由一个逻辑处理或者多个逻辑处理来完成的。 如何识别&#xf…

【备考技巧】系统集成(案例分析题)并不难

案例分析考题分析&#xff1a; 正常情况下四道题&#xff0c;计算题20分左右&#xff0c;剩余三道分析题每题15-20分左右。 ☆案例分析题&#xff1a; 从整体管理、范围管理、质量管理、人力资源管理、合同管理&采购管理、配置管理、风险管理、进度管理、成本管理中出简答题…

Jvm学习笔记(二)GC

GC 垃圾收集(GC)起源于Lisp&#xff0c;远比Java的历史更久&#xff0c;它主要思考了三件事情&#xff1a; 哪些内存需要回收&#xff1f;什么时候回收&#xff1f;如何回收&#xff1f; 本章就根据这三个点进行分析。 哪些内存需要回收&#xff1f; 在java堆中存放着无数的…

Mac浏览器无法上网但可以用微信等

可以使用微信QQ等&#xff0c;但是浏览器无法上网&#xff0c;Mac浏览器无法上网怎么办&#xff0c;Mac浏览器无法上网但可以用微信等&#xff08;百度了一下&#xff0c;没有找到原因是为什么&#xff0c;只找到了解决方法&#xff0c;记录一下&#xff09; 1.首先我们打开Ma…

Centos安装docker以及通过docker部署Mysql,照做就行!

1.安装docker 1.1给虚拟机联网&#xff08;反斜杠带表该语句没写完&#xff09; yum install -y yum-utils \device-mapper-persistent-data \lvm2 --skip-broken 1.2更新本地文件镜像 # 设置docker镜像源 yum-config-manager \--add-repo \https://mirrors.aliyun.com/doc…

【Python_Selenium学习笔记(四)】基于Selenium模块实现键盘操作

基于Selenium模块实现键盘操作 前言 在 Selenium 模块中&#xff0c;提供了一个 Keys 类&#xff0c;来处理键盘操作&#xff1b; 在 Selenium 模块中&#xff0c;使用 send_keys() 方法&#xff0c;来模拟键盘输入&#xff0c; 此篇文章主要介绍如何使用 Keys 类 和 send_ke…

vue请求本地JSON文件(注意路径 否则会404)

npm i axios // main.jsimport axios from "axios";Vue.prototype.$axios axios; //全局注册&#xff0c;使用方法为:this.$axios...vue/cli 2 json文件存放目录为 根目录下static/json/aaa.json // 使用getVideoData() {this.$axios.create({baseURL: "&quo…

springboot 部署k8s(二)

系列文章目录 目录 系列文章目录 前言 操作步骤 1.springboot.yaml文件 2.查看deployment 3.查看service服务 4.验证服务 总结 前言 springboot 部署到k8s 上。里面涉及了deployment, Service, NodePort. 操作步骤 1.springboot.yaml文件 apiVersion: apps/v1 kind: …

codeblocks20.3配置wxWidget3.2.2.1

codeblocks20.3 # 英文版自带gcc810&#xff0c;不汉化 wxWidget3.2.2.1 github下载源码 win11专业版 1.下载wxWidget3.2.2.1 源码 2.下载后解压到一个目录中&#xff0c;不要含中文和空格。我放在&#xff1a;d:\wxWidget3.2.2.1 3.打开终端cd build/msw 4.编译wxWidgets 为 …

本行卡转账基本流程说明

1、业务大致流程 2、基本业务描述 大概流程说明&#xff1a;&#xff08;牵涉到调用硬件、不便多说&#xff09; 用户插卡后、选择转账交易、依次输入转入账户卡号和转账金额后&#xff0c;用户确定转账信息&#xff1b;转账交易发送前&#xff1a;需要根据插卡账户信息和转账…

Java基础(四)数组

1. 数组的概述 1.1 为什么需要数组 需求分析1&#xff1a; 需要统计某公司50个员工的工资情况&#xff0c;例如计算平均工资、找到最高工资等。用之前知识&#xff0c;首先需要声明50个变量来分别记录每位员工的工资&#xff0c;这样会很麻烦。因此我们可以将所有的数据全部存…

TCP报文 Flood攻击原理与防御方式

TCP交互过程中包含SYN、SYN-ACK、ACK、FIN和RST报文&#xff0c;这几类报文也可能会被攻击者利用&#xff0c;海量的攻击报文会导致被攻击目标系统资源耗尽、网络拥塞&#xff0c;无法正常提供服务。接下来我们介绍几种常见的Flood攻击的原理和防御方式。 SYN Flood攻击与防御…

【Qt】项目开发遇到问题及解决总结

1.控件的触发&#xff1a;toggle()、triggered()、clicked() 区别&#xff1a; 都是按钮点击后发射的信号 clicked()&#xff1a;用于Button发射的信号triggered()&#xff1a;用于QAction发射的信号&#xff0c; trigger是一次性的。 点击后&#xff0c;无法改变状态。 要么…

【案例教程】基于RWEQ模型的土壤风蚀模数估算及其变化归因分析实践技术

土壤风蚀是一个全球性的环境问题。中国是世界上受土壤风蚀危害最严重的国家之一&#xff0c;土壤风蚀是中国干旱、半干旱及部分湿润地区土地荒漠化的首要过程。中国风蚀荒漠化面积达160.74104km2&#xff0c;占国土总面积的16.7%&#xff0c;严重影响这些地区的资源开发和社会经…

论文笔记|ECCV2022:Self-Promoted Supervision for Few-Shot Transformer

论文地址&#xff1a;https://arxiv.org/abs/2203.07057 代码链接&#xff1a;https://github.com/DongSky/few-shot-vit 这篇论文在2022年发表在ECCV上&#xff0c;论文的题目是用于小样本Transformer的self-promoted supervision&#xff08;自我推荐监督&#xff09; 1 Mot…

求给定集合中好数对的个数

已知一个集合A&#xff0c;对A中任意两个不同的元素求和&#xff0c;若求得的和仍在A内&#xff0c;则称其为好数对。例如&#xff0c;集合A{1 2 3 4}&#xff0c;123&#xff0c;134&#xff0c;则1,2和1,3 是两个好数对。 编写程序求给定集合中好数对的个数。 注&#xff1a;…

java设计模式(1) 适配器模式、装饰器模式

适配器模式 适配器就是一种适配中间件&#xff0c;它存在于不匹配的了两者之间&#xff0c;用于连接两者&#xff0c;使不匹配变得匹配。 手机充电需要将220V的交流电转化为手机锂电池需要的5V直流电 知识补充&#xff1a;手机充电器输入的电流是交流&#xff0c;通过变压整流…

XML复习

目录什么是XMLXML中的内容可以干什么XML文件的创建以及其格式XML的文档约束-DTD约数XML的文档约束-schema约束Dom4J 解析XML 文档什么是XML XML 全称(extensible Markup Lanage) 可扩展标记语言它是一种数据的表示形式, 可以存储复杂的数据格式以及我们自己定义的格式.XML经常…

windows安装ubuntu时错误WslRegisterDistribution failed with error: 0x8007023e的解决方法

cmd或者powershell安装&#xff0c;或者打开linux时 莫名的出现了如下错误&#xff1a; Installing, this may take a few minutes... WslRegisterDistribution failed with error: 0x8007023e Error: 0x8007023e {Application Error} The exception s (0x尝试了很多的方法都不…
最新文章