排序算法(6):快速排序

ops/2024/12/14 16:02:54/

问题

排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]

快速排序

快速排序采用分治策略,首先从数组中选择一个元素作为基准元素。以基准元素为标准,将问题分解为两个子序列,使小于等于基准元素的子序列在左侧,大于基准元素的子序列在右侧。然后将两个子序列分别进行快速排序,将排序好的两个子序列合并在一起,完成排序。

图解

快速排序算法的重点是选择基准元素,并将其移动到正确的位置。

  1. 初始化第一个元素为基准元素,pivot = 30,i = low,j = high
  2. 从数组的右边位置向左找,一直找到小于 pivot 的元素 12,与基准元素交换位置,i += 1
    在这里插入图片描述
  3. 从数组的左边位置向右找,一直找到大于 pivot 的元素 58,与基准元素交换位置,j -= 1
    在这里插入图片描述
  4. 从数组的右边位置向左找,一直找到小于 pivot 的元素 18,交换位置,i += 1。此时 i = j,第一轮排序结束,返回 i 的位置,mid = i

在这里插入图片描述
5. 完成第一轮排序之后,以 mid 为界,将原数据分为两个子序列,左侧子序列都比 pivot 小,右侧子序列都比 pivot 大,然后分别对两个子序列进行快速排序。

在这里插入图片描述

代码

# 获取基准元素的正确位置
def partition(nums, low, high):pivot = nums[low]i, j = low, highwhile i < j:while i < j and nums[j] >= pivot:   # 从右向左找小于pivot的数,并交换位置j -= 1if i < j: nums[i], nums[j] = nums[j], nums[i]i += 1while i < j and nums[i] <= pivot:   # 从左向右找大于pivot的数,并交换位置i += 1if i < j: nums[i], nums[j] = nums[j], nums[i]j -= 1return idef quick_sort(nums, low=0, high= len(nums)-1):if low < high:mid = partition(nums, low, high)quick_sort(nums, low, mid-1)quick_sort(nums, mid+1, high)return nums

时间复杂度

  • 快速排序最好的时间复杂度是 O(nlogn)

    最理想的情况下,每次划分将问题分解为两个规模都是 n/2 的子问题,递归求解

    在这里插入图片描述
    递归最终规模为 1,令 2x = n,x = logn,那么

    在这里插入图片描述

  • 快速排序最块的时间复杂度为 O(n2)

    在最坏的情况下,每次划分将问题分解后,基准元素的左侧或右侧没有元素,基准元素的另一侧为 1 个规模为 n-1 的子问题,递归求解

    在这里插入图片描述

算法优化

在上述算法中,每次交换都是在和基准元素交换,但实际没必要这样做。只需要从右往左找到小于等于基准元素的数,再从左往右找到大于基准元素的数,将这两个数交换,一直交替进行,直到 i 和 j 碰头,这时将其和基准元素交换,这样就完成了一次划分过程。

  1. 首先取数组第一个元素为基准元素 pivot = 30
    在这里插入图片描述

  2. 从数组的右边往左找,一直找到小于 pivot 的元素 12,从数组的左边往右找,一直找到大于 pivot 的元素 58,然后将它们交换位置
    在这里插入图片描述

  3. 继续从数组的右边往左找,找到小于 pivot 的元素 18,从左往右找大于 pivot 直到 i = j 时停止
    在这里插入图片描述

  4. 将基准元素和 i 位置的元素交换,返回 i 的位置 mid = i,第一轮排序结束

代码

def partition(nums, low, high):pivot = nums[low]i, j = low, highwhile i < j:while i < j and nums[j] > pivot:j -= 1while i < j and nums[i] <= pivot:i += 1if i < j:nums[i], nums[j] = nums[j], nums[i]i += 1j -= 1if nums[i] > pivot:nums[i-1], nums[low] = nums[low], nums[i-1]return i-1nums[low], nums[i] = nums[i], nums[low]return i

http://www.ppmy.cn/ops/141851.html

相关文章

数据库表的CRUD

SQL语句&#xff08;Structured Query Language&#xff09;是用于与关系型数据库进行交互的语言。下面是几个常用的SQL语句&#xff1a; 创建表&#xff1a; CREATE TABLE table_name ( column1 datatype, column2 datatype, column3 datatype, ... ); 插入数据&#xff1a; …

【Go基础】Go算法常用函数整理

Go算法常用函数整理 使用 Go 语言编写算法题时&#xff0c;掌握一些常用的函数和用法可以大大提高效率。 1. 排序 (slices 包)&#xff1a; slices.Sort(x []T)&#xff1a; 对切片 x 进行升序排序。需要 Go 1.18 版本。T 需要实现 constraints.Ordered 接口&#xff0c;例如…

JVM--JVM内存模型

JVM&#xff08;Java虚拟机&#xff09;内存模型是理解Java应用程序运行时行为的关键&#xff0c;它定义了Java程序在执行期间如何管理内存。根据Java虚拟机规范&#xff0c;JVM的内存主要分为五个部分&#xff1a;程序计数器、Java虚拟机栈、本地方法栈、堆以及方法区。随着JD…

代理IP在产品运营中的重要作用

在数字化时代&#xff0c;产品运营的成功与否往往取决于企业对市场动态的敏锐洞察、高效的数据处理能力和强大的网络技术支持。代理IP作为一种重要的网络工具&#xff0c;在产品运营中发挥着不可或缺的作用。本文将详细介绍代理IP如何在产品运营中提供助力&#xff0c;帮助企业…

RFDiffusion 计算二面角函数get_dih解读

get_dih 函数计算任意四个连续原子之间的二面角(dihedral angle),它描述了主链和侧链原子的三维空间排布。 源代码: def get_dih(a, b, c, d):"""calculate dihedral angles for all consecutive quadruples (a[i],b[i],c[i],d[i])given Cartesian coordi…

Spring Boot 应用 “Connection is closed” 及 MySQL 空闲超时断开连接解决方案

在使用 Spring Boot MySQL HikariCP 的组合时&#xff0c;可能会在生产或测试环境中遭遇类似如下异常信息&#xff1a; org.springframework.jdbc.UncategorizedSQLException: PreparedStatementCallback; uncategorized SQLException for SQL [SELECT ...]; SQL state [nu…

区块链技术的应用场景和优势。

区块链技术的应用场景和优势主要包括以下几个方面&#xff1a; 金融领域&#xff1a;区块链技术可以实现去中心化的数字货币&#xff0c;例如比特币&#xff0c;以及智能合约&#xff0c;可以简化金融交易&#xff0c;并提高交易的可追溯性和安全性。 物联网领域&#xff1a;在…

状态管理实战:一次 Redux 到 React Query 的重构之旅

"老师,我们的后台管理系统状态管理好混乱啊&#xff01;"上周二的代码评审会上,小王一脸苦恼地说道。我打开代码仓库看了看,确实问题不小 - Redux store 里堆满了各种数据,有本地状态,有服务器数据,还有一些缓存,导致代码难以维护,性能也受到影响。 说实话,这个问题…