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

python 快速排序(Quick Sort)

快速排序(Quick Sort)

快速排序是一种高效的排序算法,采用分治法(Divide and Conquer)策略。它的基本思想是:选择一个基准元素(pivot),将数组分为两部分,使得左边部分的元素都小于基准元素,右边部分的元素都大于基准元素,然后递归地对左右两部分进行排序。

快速排序的步骤:
  1. 选择基准元素:从数组中选择一个元素作为基准(通常选择第一个、最后一个或中间元素)。
  2. 分区操作:将数组分为两部分,左边部分的元素小于基准元素,右边部分的元素大于基准元素。
  3. 递归排序:对左右两部分递归地应用快速排序。
  4. 合并结果:由于分区操作已经保证了左边部分小于右边部分,最终数组自然有序。
时间复杂度:
  • 最坏情况:O(n²) —— 当每次选择的基准元素都是最小或最大元素时。
  • 最好情况:O(n log n) —— 当每次选择的基准元素都能将数组均匀分为两部分时。
  • 平均情况:O(n log n)
空间复杂度:
  • O(log n) —— 递归调用栈的深度。

Python 实现

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]  # 选择中间元素作为基准left = [x for x in arr if x < pivot]  # 小于基准的部分middle = [x for x in arr if x == pivot]  # 等于基准的部分right = [x for x in arr if x > pivot]  # 大于基准的部分return quick_sort(left) + middle + quick_sort(right)  # 递归排序并合并# 示例使用
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)

输出结果

排序后的数组: [1, 1, 2, 3, 6, 8, 10]

快速排序的详细过程

以数组 [3, 6, 8, 10, 1, 2, 1] 为例:

  1. 第一轮

    • 选择基准元素 10(假设选择最后一个元素)。
    • 分区结果:
      • 左边部分:[3, 6, 8, 1, 2, 1]
      • 右边部分:[]
    • 递归排序左边部分。
  2. 第二轮

    • 选择基准元素 1(左边部分的最后一个元素)。
    • 分区结果:
      • 左边部分:[]
      • 右边部分:[3, 6, 8, 2]
    • 递归排序右边部分。
  3. 第三轮

    • 选择基准元素 2(右边部分的最后一个元素)。
    • 分区结果:
      • 左边部分:[]
      • 右边部分:[3, 6, 8]
    • 递归排序右边部分。
  4. 第四轮

    • 选择基准元素 8(右边部分的最后一个元素)。
    • 分区结果:
      • 左边部分:[3, 6]
      • 右边部分:[]
    • 递归排序左边部分。
  5. 第五轮

    • 选择基准元素 6(左边部分的最后一个元素)。
    • 分区结果:
      • 左边部分:[3]
      • 右边部分:[]
    • 递归排序左边部分。
  6. 合并结果

    • 最终排序结果为 [1, 1, 2, 3, 6, 8, 10]

快速排序的优缺点

优点

  • 平均时间复杂度为 O(n log n),性能优异。
  • 是原地排序算法,不需要额外的存储空间。
  • 在实际应用中表现良好,是常用的排序算法之一。

缺点

  • 最坏情况下时间复杂度为 O(n²),但可以通过优化基准选择策略来避免。
  • 不是稳定的排序算法(相同元素的相对位置可能改变)。

优化快速排序

  1. 随机选择基准元素

    • 避免最坏情况的发生,提高算法的稳定性。
  2. 三数取中法

    • 选择第一个、最后一个和中间元素的中位数作为基准。
  3. 小数组使用插入排序

    • 当数组规模较小时,插入排序的效率更高。

优化后的快速排序实现

import randomdef quick_sort_optimized(arr):if len(arr) <= 1:return arrpivot = random.choice(arr)  # 随机选择基准元素left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort_optimized(left) + middle + quick_sort_optimized(right)# 示例使用
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort_optimized(arr)
print("优化后的排序数组:", sorted_arr)

总结

快速排序是一种高效的排序算法,适用于大规模数据的排序。通过优化基准选择策略,可以进一步提高其性能和稳定性。

相关文章:

python 快速排序(Quick Sort)

快速排序&#xff08;Quick Sort&#xff09; 快速排序是一种高效的排序算法&#xff0c;采用分治法&#xff08;Divide and Conquer&#xff09;策略。它的基本思想是&#xff1a;选择一个基准元素&#xff08;pivot&#xff09;&#xff0c;将数组分为两部分&#xff0c;使得…...

MySQL数据库——常见慢查询优化方式

本文详细介绍MySQL的慢查询相关概念&#xff0c;分析步骤及其优化方案等。 文章目录 什么是慢查询日志&#xff1f;慢查询日志的相关参数如何启用慢查询日志&#xff1f;方式一&#xff1a;修改配置文件方式二&#xff1a;通过命令动态启用 分析慢查询日志方式一&#xff1a;直…...

【AIGC篇】AIGC 引擎:点燃创作自动化的未来之火

&#xff1a;羑悻的小杀马特.-CSDN博客 未来都是惊喜。你生来本应为高山。并非草芥。 引言&#xff1a; 在当今数字化的时代&#xff0c;人工智能生成内容&#xff08;AIGC&#xff09;正以一种前所未有的力量改变着我们的创作领域。它就像一个神秘而强大的魔法师&#xff0c;…...

C语言性能优化:从基础到高级的全面指南

引言 C 语言以其高效、灵活和功能强大而著称&#xff0c;被广泛应用于系统编程、嵌入式开发、游戏开发等领域。然而&#xff0c;要写出高性能的 C 语言代码&#xff0c;需要对 C 语言的特性和底层硬件有深入的了解。本文将详细介绍 C 语言性能优化的背后技术&#xff0c;并通过…...

常用的公共 NTP(网络时间协议)服务器

公共 NTP 服务列表 以下是一些常用的公共 NTP&#xff08;网络时间协议&#xff09;服务器&#xff0c;供您参考&#xff1a; 中国地区公共 NTP 服务器 国家授时中心 NTP 服务器&#xff1a;ntp.ntsc.ac.cn中国 NTP 快速授时服务&#xff1a;cn.ntp.org.cn阿里云公共 NTP 服务…...

Kafka中的Topic和Partition有什么关系?

大家好&#xff0c;我是锋哥。今天分享关于【Kafka中的Topic和Partition有什么关系&#xff1f;】面试题。希望对大家有帮助&#xff1b; Kafka中的Topic和Partition有什么关系&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在 Apache Kafka 中&#…...

Unity 使用UGUI制作卷轴开启关闭效果

视频效果 代码 using UnityEngine.UI; using System.Collections; using System.Collections.Generic; using UnityEngine; using DG.Tweening; using DG.Tweening.Core; using DG.Tweening.Plugins.Options;public class JuanZhou : MonoBehaviour {[SerializeField]private …...

MarkDown怎么转pdf;Mark Text怎么使用;

MarkDown怎么转pdf 目录 MarkDown怎么转pdf先用CSDN进行编辑,能双向看版式;标题最后直接导出pdfMark Text怎么使用一、界面介绍二、基本操作三、视图模式四、其他功能先用CSDN进行编辑,能双向看版式; 标题最后直接导出pdf Mark Text怎么使用 Mark Text是一款简洁的开源Mar…...

整合版canal ha搭建--基于1.1.4版本

开启MySql Binlog&#xff08;1&#xff09;修改MySql配置文件&#xff08;2&#xff09;重启MySql服务,查看配置是否生效&#xff08;3&#xff09;配置起效果后&#xff0c;创建canal用户&#xff0c;并赋予权限安装canal-admin&#xff08;1&#xff09;解压 canal.admin-1…...

QGIS移动图元功能

有时需要在QGIS里面移动一些矢量图层&#xff0c;比如图层的地理配准&#xff0c;网上搜了一些资料没有查看&#xff0c;后来仔细找了下&#xff0c;在编辑-编辑几何图形-移动要素里面&#xff0c;可以移动图层。 注意&#xff1a;移动前先要选择上要移动的图层&#xff0c;之…...

【模电刷题复习--填空】

如有错误&#xff0c;欢迎各位大佬在评论区批评指正 模电刷题 一、填空题1.本征半导体中&#xff0c;若掺入微量的__五__价元素&#xff0c;则形成___n___型半导体&#xff0c;其多数载流子是自由电子&#xff0c;若掺入微量的__三__价元素&#xff0c;则形成__p__型半导体。其…...

shardingsphere-jdbc-core-spring-boot-starter的性能问题(理论)

hardingSphere-JDBC-core-spring-boot-starter 是 ShardingSphere 提供的与 Spring Boot 集成的模块&#xff0c;用于实现数据库的分库分表等功能。在性能方面&#xff0c;它既有优势也存在一定的挑战&#xff0c;以下是具体分析&#xff1a; 优势方面 数据分片提升查询性能 通…...

Java Map 集合详解:基础用法、常见实现类与高频面试题解析

在 Java 集合框架中&#xff0c;Map 是用于存储键值对&#xff08;Key-Value&#xff09;的重要接口&#xff0c;广泛应用于开发中的各种场景。本文将详细讲解 Map 的基础概念、常见实现类及其特性&#xff0c;并结合代码示例和高频面试问题&#xff0c;帮助你深入理解 Map 的用…...

一款基于.Net方便、快捷的数据库文档查询、生成工具

项目介绍 SmartSQL 是一款方便、快捷的数据库文档查询、导出工具&#xff01;从最初仅支持SqlServer数据库、CHM文档格式开始&#xff0c;通过不断地探索开发、集思广益和不断改进&#xff0c;又陆续支持Word、Excel、PDF、Html、Xml、Json、MarkDown等文档格式的导出。同时又…...

Linux平台下实现的小程序-进度条

目录 1.换行、回车概念 2.缓冲区 2.1缓冲区 2.2强制刷新 3.进度条程序 Makefile文件 ProgressBar.h ProgressBar.c Main.c 执行结果 1.换行、回车概念 /n&#xff1a;换行回车&#xff08;\r&#xff1a;回车&#xff09; 2.缓冲区 如下图在vim编辑器中的命令模式下…...

Ubuntu 22.04.5 修改IP

Ubuntu22.04.5使用的是netplan管理网络&#xff0c;因此需要在文件夹/etc/netplan下的01-network-manager-all.yaml中修改&#xff0c;需要权限&#xff0c;使用sudo vim或者其他编辑器&#xff0c;修改后的内容如下&#xff1a; # Let NetworkManager manage all devices on …...

解决virtualbox出现开启DHCP之后ubuntu虚拟机之后IP重复的问题

找遍了国内论坛&#xff0c;没一个能解决该问题的&#xff0c;所以我自己写个文章吧&#xff0c;真讨厌那些只会搬运的&#xff0c;污染国内论坛环境&#xff0c;搜一个问题&#xff0c;千篇一律。 问题 操作系统版本为"Ubuntu 24.04 LTS" lennytest1:~$ cat /etc…...

Java开发工具-Jar命令

Java开发工具-Jar 1、jar命令全平台使用 2、jar命令的作用 为类和资源创建存档&#xff0c;并从存档中操作或恢复单个类或资源 3、摘要 jar [OPTION …] [ [–release VERSION] [-C dir] files] … 4、jar命令描述 jar命令通常作为用于压缩与解压的工具&#xff0c;基于ZIP或Z…...

UE5通过蓝图节点控制材质参数

通过蓝图节点控制材质的参数 蓝图节点 在材质上设置标量值 和 在材质上设置向量参数值 Set Scalar Parameter Value on Materials Set Vector Parameter Value on Materials 这两个蓝图节点都可以在蓝图中&#xff0c;控制材质的参数值和向量值...

敖行客年终总结-AT Work 1.0发布

2024年就要过去了&#xff0c;看看敖行客这一年都干了些啥&#xff1f; 敖行客团队通过整整一年的努力&#xff0c;正式推出了AT Work 1.0订阅版&#xff0c;这也标志着AT Work即将正式和C端的小伙伴见面了。 AT Work 是什么&#xff1f; 长期以来&#xff0c;软件研发成本、…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...