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

快速排序基本原理

快速排序基本原理

  • 1.快速排序
    • 1.1 基本原理
    • 1.2 快速排序执行步骤
      • 1.2.1 分区包含步骤
      • 1.2.1 分区步骤
    • 1.3 快速排序大O记法表示
  • 2. 将[0,5,2,1,6,3]进行快速排序 【实战】
    • 2.1 第一次分区步骤
    • 2.2 第二次分区步骤
    • 2.3 第三次分区步骤
    • 2.4 第四次分区步骤
  • 3.快速排序代码实现

1.快速排序

1.1 基本原理

  • 快速排序依赖于一个名为分区的概念
  • 分区:从数组随机选取一个值,以此值轴,将比它小的值放到它左边,比它大的值放到它右边

1.2 快速排序执行步骤

1.2.1 分区包含步骤

  • 比较:每个值都要与轴做比较。
  • 交换:在适当时候将左右指针所指的两个值交换位置。

1.2.1 分区步骤

  • 第一次分区步骤

    1. 左指针逐个格子向右移动,当遇到大于或等于轴的值时,停止移动。
    2. 右指针逐个格子向左移动,当遇到小于或等于轴的值时,停止移动。
    3. 将两指针所指的值交换位置。
    4. 重复步骤,直至两指针重合或左指针移到右指针的右边。
    5. 将轴与左指针所指的值交换位置【左指针>轴时交换】。
  • 子数组分区
    6. 对其轴左右两侧的元素进行排序。
    7. 对轴左右的两个子数组递归重复第 1、2 步,两个子数组各自分区,并形成各自的轴以及由轴分隔的更小的子数组。然后对这些子数组分区。
    8. 当分出的子数组长度为 0 或 1 时,排序结束。

  • 每次分区完成时,在轴左侧的那些值肯定比轴要小,在轴右侧的那些值肯定比轴要大

  • 轴数据的值放在了正确的位置。

1.3 快速排序大O记法表示

  • 快速排序大O记法表示: O(NNN)

2. 将[0,5,2,1,6,3]进行快速排序 【实战】

2.1 第一次分区步骤

在这里插入图片描述

2.2 第二次分区步骤

在这里插入图片描述

2.3 第三次分区步骤

在这里插入图片描述

2.4 第四次分区步骤

在这里插入图片描述

3.快速排序代码实现

# 方式一【有排序步骤输出】,根据最大索引排序
alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
def sort(alist, left, right, flag=True):if not flag:print('-' * 30 + '\tstart list\t' + '-' * 30)print(f"当前列表为:{alist},left:{left},right:{right}")axis_index = rightaxis = alist[axis_index]  # 轴值left_pointer = left  # 左指针right_pointer = right - 1  # 右指针if left_pointer > right_pointer:  # 判断左指针是否在右指针的右边,如果是:停止移动returnwhile True:while alist[left_pointer] < axis:left_pointer = left_pointer + 1while alist[right_pointer] > axis:  # 右指针向左移动right_pointer = right_pointer - 1if left_pointer < right_pointer:  # 指针未重合alist[left_pointer], alist[right_pointer] = alist[right_pointer], alist[left_pointer]print(f'左指针索引为:{left_pointer},右指针索引为:{right_pointer};左右指针交换后数组作为:{alist}')elif alist[left_pointer] > alist[axis_index]:alist[left_pointer], alist[axis_index] = alist[axis_index], alist[left_pointer]  # 轴值交换print(f'左指针索引为:{left_pointer},轴索引为:{axis_index};左指针与轴交换后数组作为:{alist}')breakelif left_pointer > right_pointer:print(f"左指针索引为:{left_pointer},右指针索引为:{right_pointer};左指针在右指针的右边,指针移动结束")breakprint(f'分区结束,数组为:{alist}')if left_pointer - left not in [0, 1]:print('-' * 30 + '\tleft list\t' + '-' * 30)sort(alist, left, left_pointer - 1)  # 排序左子数组if right - left_pointer not in [0, 1]:print('-' * 30 + '\tright list\t' + '-' * 30)sort(alist, left_pointer + 1, right)  # 排序右子数组return alistend=sort(alist, 0, len(alist) - 1, False)
print('-' * 30 + '\tend list\t' + '-' * 30)
print(f"最终排序结果为:{end}")# 方式二【无排序步骤输出】
alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
def sort(alist, left, right):axis_index = right        # 轴索引axis = alist[axis_index]  # 轴值left_pointer = left  # 左指针right_pointer = right - 1  # 右指针if left_pointer > right_pointer:  # 判断左指针是否在右指针的右边,如果是:停止移动returnwhile True:while alist[left_pointer] < axis:  # 左指针向右移动left_pointer = left_pointer + 1while alist[right_pointer] > axis:  # 右指针向左移动right_pointer = right_pointer - 1if left_pointer < right_pointer:  # 指针未重合,左右指针调换alist[left_pointer], alist[right_pointer] = alist[right_pointer], alist[left_pointer]elif alist[left_pointer] > alist[axis_index]: # 左指针>轴alist[left_pointer], alist[axis_index] = alist[axis_index], alist[left_pointer]  # 轴值交换breakelif left_pointer > right_pointer:  # 左指针在右指针的右边breakif left_pointer - left not in [0, 1]:sort(alist, left, left_pointer - 1)  # 排序左子数组if right - left_pointer not in [0, 1]:sort(alist, left_pointer + 1, right)  # 排序右子数组return alist
end=sort(alist, 0, len(alist) - 1)
print(f"最终排序结果为:{end}")# 方式三 :根据索引0开始排序
alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
def sort(alist, left, right):low = lefthigh = rightif low > high:returnmiddle = alist[low]while low != high:while low < high:if alist[high] > middle:high = high - 1else:alist[low] = alist[high]breakwhile low < high:if alist[low] < middle:low = low+1else:alist[high] = alist[low]breakalist[low] = middlesort(alist, left, low - 1)sort(alist, high + 1, right)return alistprint(sort(alist, 0, len(alist) - 1))

在这里插入图片描述

相关文章:

快速排序基本原理

快速排序基本原理1.快速排序1.1 基本原理1.2 快速排序执行步骤1.2.1 分区包含步骤1.2.1 分区步骤1.3 快速排序大O记法表示2. 将[0,5,2,1,6,3]进行快速排序 【实战】2.1 第一次分区步骤2.2 第二次分区步骤2.3 第三次分区步骤2.4 第四次分区步骤3.快速排序代码实现1.快速排序 1.…...

Android开发笔记-提纲(连载中....)

文章目录Android概述Android开发学习笔记提纲1. 认识AS开发Android的基础入门知识2. 认识Activity的生命周期和基础使用3. 认识Activity之间的跳转和传值4. 认识Intent以及全局Activity的属性的共享5. 认识Service6. 学习跨应用服务【AIDL通信】Android概述 Android系统框架的四…...

React Native(一)

移动端触摸事件example1:<ButtononPress{() > {Alert.alert(你点击了按钮&#xff01;);}}title"点我&#xff01;" />Touchable 系列组件TouchableHighlight 此组件的背景会在用户手指按下时变暗TouchableNativeFeedback 会在用户手指按下时形成类似墨水涟…...

Kotlin 26. Kotlin 如何播放音频文件

Kotlin 如何播放音频文件 文章目录Kotlin 如何播放音频文件1 下载并放置音频文件2 activity_main.xml3 MainActivity.kt1 下载并放置音频文件 我们可以随便下载一个音频文件&#xff0c;比如 alarm.mp3&#xff0c;需要将其放置在 /res/raw/ 路径下。 2 activity_main.xml 这…...

recv和明文收包分析

我们CTRLg 跳到recv 分析收包函数 发现函数会断并且收包函数返回值(收包包长)也会不断变化 那么证明recv是真正的收包函数&#xff0c;游戏没有重新实现该函数 我们只要分析该函数即可 在recv函数执行完毕以后下断 eax是包长,esi28是包指针 我们上2个号&#xff0c;让另外…...

【IVIF的超分重建】

Multimodal super-resolution reconstruction of infrared and visible images via deep learning &#xff08;基于深度学习的红外和可见光图像多模态超分辨率重建&#xff09; 提出了一种基于编解码器结构的红外-可见光图像融合方法。图像融合任务被重新表述为保持红外-可见…...

“深度学习”学习日记。--加深网络

2023.2.13 深度学习 是加深了层的深度神经网络的学习过程。基于之前介绍的网络&#xff0c;只需要通过 叠加层&#xff0c; 就可以创建深度网络 之前的学习&#xff0c;已经学习到了很多东西&#xff0c;比如构成神经网络的各种层、参数优化方法、误差反向传播法&#xff0c;…...

2023前端面试总结含参考答案

文章目录1. 父子组件生命周期的执行顺序:2. 原型链&#xff1a;3. promise的理解&#xff1a;4. 数组循环&#xff0c;foreach&#xff0c;filter&#xff0c;map&#xff0c;reduce5. 数组去重&#xff0c;set6. 组件通信方式7. 路由钩子8. 首页首屏加载优化&#xff1a;9. th…...

总览 Java 容器--集合框架的体系结构

前言 我们在讲 Java 的数据类型的时候&#xff0c;单独介绍过数组&#xff0c;数组也确实是开发程序中常用的内存类型之一&#xff0c;不过 Java 内置的数组限制颇多&#xff0c;所以此后扩展出了List这种结构&#xff0c;与之类似的Set、Queue 这些内存中的容器都被放在了 Co…...

即便考分很好也不予录取的研究生复试红线,都是原则性问题

在浙大研究生招生录取政策文件中有这么一句话&#xff1a;坚持“按需招生、全面衡量、择优录取、宁缺毋滥”的原则&#xff0c;以提高人才选拔质量为核心&#xff0c;在确保安全性、公平性和科学性的基础上&#xff0c;做到统筹兼顾、精准施策、严格管理。字字体现出研究生招生…...

Android java创建子线程的几种方法

1.新建一个类继承自Thread&#xff0c;并重写run()方法&#xff0c;并在里面编写耗时逻辑。 1 2 3 4 5 6 7 class ThreadTest extends Thread { Override public void run() { //具体的耗时逻辑代码 } } new ThreadTest().st…...

UVa 11212 Editing a Book 编辑书稿 IDA* Iterative Deepening A Star 迭代加深搜剪枝

题目链接&#xff1a;Editing a Book 题目描述&#xff1a; 给定nnn个(1<n<10)1<n<10)1<n<10)数字&#xff0c;数字分别是1,2,3,...,n1, 2, 3, ...,n1,2,3,...,n&#xff0c;但是顺序是打乱的&#xff0c;你可以选择一个索引区间的数字进行剪切操作。问最少进…...

第一章:unity性能优化之内存优化

目录 前言 unity性能优化之内存的优化 一、unity Analysis工具的使用。 二、内存优化方法 1、设置和压缩图片 2、图片格式 3、动画文件 4、模型 5、RenderTexture&#xff08;RT&#xff09; 6、分辨率 7、资源的重复利用 8、shader优化 9、对bundle进行良好的管…...

2023年家族办公室研究报告

第一章 概况 家族办公室最早起源于古罗马时期的大“Domus”&#xff08;家族主管&#xff09;以及中世纪时期的大“Domo”&#xff08;总管家&#xff09;。现代意义上的家族办公室出现于19世纪中叶&#xff0c;一些抓住产业革命机会的大亨将金融专家、法律专家和财务专家集合…...

Typescript快速入门

Typescript快速入门第一章 快速入门0、TypeScript简介1、TypeScript 开发环境搭建2、基本类型3、编译选项4、webpack5、Babel第二章&#xff1a;面向对象0、面向对象简介1、类&#xff08;class&#xff09;2、面向对象的特点3、接口&#xff08;Interface&#xff09;4、泛型&…...

如何激励你的内容团队产出更好的创意

对于一个品牌而言&#xff0c;如何创造吸引受众并对受众有价值内容是十分关键的。随着市场数字化的推进&#xff0c;优质的创意和内容输出对一个品牌在市场中有着深远的影响。对于很多内容策划和创作者来说&#xff0c;不断地产出高质量有创意的内容是一件非常有挑战性的事情。…...

机械设备管理软件如何选择?机械设备管理软件哪家好?

随着信息化技术的进步与智能制造的发展趋势&#xff0c;很多机械设备制造企业也在一直探寻适合自己的数字化管理转型之路&#xff0c;而企业上ERP管理软件又是实现数字化管理的前提&#xff0c;机械设备管理软件对于企业来说就是关键一环。机械设备管理软件如何选择&#xff1f…...

深入浅出带你学习shiro-550漏洞

//发点去年存货 前言 apache shiro是一个java安全框架&#xff0c;作用是提供身份验证&#xff0c;Apache Shiro框架提供了一个Rememberme的功能,存储在cookie里面的Key里面&#xff0c;攻击者可以使用Shiro的默认密钥构造恶意序列化对象进行编码来伪造用户的 Cookie&#xf…...

项目(今日指数之环境搭建)

一 项目架构1.1 今日指数技术选型【1】前端技术【2】后端技术栈【3】整体概览1.2 核心业务介绍【1】业务结构预览【2】业务结构预览1.定时任务调度服务XXL-JOB通过RestTemplate多线程动态拉去股票接口数据&#xff0c;刷入数据库&#xff1b; 2.国内指数服务 3.板块指数服务 4.…...

PCL 基于投影点密度的建筑物立面提取

目录 一、算法原理1、投影密度理论及方法2、参考文献二、代码实现三、结果展示一、算法原理 1、投影密度理论及方法 将3维坐标点直接垂直投影到水平面上或者将 Z Z Z 值取任意常数,统计和计算水平面任意位置处所含投影点的个数记为...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

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

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