排序系列 之 快速排序

  • !!!排序仅针对于数组哦
  • 本次排序是按照升序来的哦
  • 代码后边有图解哦

介绍

  • 快速排序英文名为Quick Sort

基本思路

  • 快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素base,利用base将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列

代码

<!----java----->
import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] arr = {7,2,3,6,1,5,4};  // 待排序数组sort(arr,0, arr.length-1); // 方法调用,left和right为带排序数组的起始位置和最终位置,所以right=arr.length-1System.out.println(Arrays.toString(arr));}public static void sort(int[] arr,int left,int right){if(left>=right){return;}    // 判断带排序数组的长度,严格的左边游标要不大于右边游标int base = arr[left];    // 定义基准数int i = left;       // 定义左边的游标。这里不用left,是因为left位置为基准数,基准数不能变int j = right;      // 定义右边的游标。这里不用right,是因为后续递归的时候需要一个参数while(i!=j){    // 循环走起,当i和j相遇时,跟基准数交换。不相遇时,i位置大于基准数,j位置小于基准数时,i位置和j位置的数交换/**   思考下,为啥这里先是j在i前边???    */while(arr[j]>=base && i<j){j--;}    // 循环停止,说明j指向的数值要比基准数小。降序为<= while(arr[i]<=base && i<j){i++;}    // 循环停止,说明i指向的数值要比基准数大。降序为>= /** 【公布问题答案啦】* 因为j停下的时候代表当前数比基准数小,i停下是当前数比基准数大。我们此次排序是升序,相遇数要和基准数交换,所以需要保证相遇数一定要小于基准数*/// 本次排序为升序,即需要找到一个位置,这个位置的左边都是比基准数小的,右边都是比基准数大的int temp = arr[i];  // i比基准数大,j比基准数小,交换。交换完成后,i和j不等,两个游标继续前走或后走arr[i] = arr[j];arr[j] = temp;}// i和j相遇,i也行j也行,因为都指向一个嘛,跟基准数交换。然后对基准数左右两遍递归arr[left] = arr[i];arr[i] = base;sort(arr,left,i-1);sort(arr,i+1,right);}
}<!------------------------>
运行结果;
[1, 2, 3, 4, 5, 6, 7]
<!----python----->
def quickSort(arr, left, right):if left >= right:return arr;base = arr[left];i, j = left, right;while i != j:while arr[j] >= base and i < j:j -= 1while arr[i] <= base and i < j:i += 1arr[j], arr[i] = arr[i], arr[j];arr[i], arr[left] = arr[left], arr[i];quickSort(arr,left,i-1);quickSort(arr,i+1,right);return arrarr = [7,2,3,6,1,5,4]
print(quickSort(arr, 0, len(arr) - 1))
<!------------------------>
运行结果;
[1, 2, 3, 4, 5, 6, 7]

代码思路及流程图(直接上图,不清楚可以对照代码看哦)

在这里插入图片描述

复杂度

  • 时间复杂度:最好和平均情况下为O(n log n),最坏情况下为O(n^2)。
  • 空间复杂度:最好情况下为O(log n),最坏情况下为O(n),额外空间为O(1)。
    (复杂度先记住吧,等后续研究彻底了,会再写篇文章的)
  • 它是非稳定排序

扩展一下

Python的一个更简单的方法
# 该方法不适用java哦
def quickSort(arr):if len(arr)<2:return arr;base=arr[0];left = [x for x in arr if x<base];middle = [x for x in arr if x==base];right = [x for x in arr if x>base];return quickSort(left)+middle+quickSort(right);arr=[7,2,3,6,1,5,4];
print(quickSort(arr))  # [1, 2, 3, 4, 5, 6, 7]

巩固一下

给定一个数组,用上述方法进行排序,流程是不是跟下图一样呢?
int[] arr = {3,7,1,6,2,5,4}
在这里插入图片描述

文章推荐

  • 实在是不会做动画,如果还看不懂,可以移步这里:
    十大经典排序算法
    【漫画】不要再问我快速排序了
  • 有错误请指正,谢谢各位~

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(01)Unity使用在线AI大模型(使用百度千帆服务)

目录 一、概要 二、环境说明 三、申请百度千帆Key 四、使用千帆大模型 四、给大模型套壳 一、概要 在Unity中使用在线大模型分为两篇发布&#xff0c;此篇文档为在Python中使用千帆大模型&#xff0c;整体实现逻辑是&#xff1a;在Python中接入大模型—>发布为可传参的…

算法日记day 12(栈实现队列|队列实现栈|有效的括号)

队列是先进先出的&#xff0c;就像排队一样&#xff0c;谁在前谁先获得服务 栈是一种先进后出的数据结构 一、用栈实现队列 题目&#xff1a; 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09;&#xf…

uniapp上传功能用uni-file-picker实现

文章目录 html代码功能实现css样式代码 html代码 <uni-file-pickerselect"onFileSelected"cancel"onFilePickerCancel"limit"1"class"weightPage-upload-but"file-mediatype"image"></uni-file-picker><imag…

飞睿智能UWB Tag蓝牙防丢器标签,宠物安全新升级,5cm精准定位测距不迷路

宠物早已成为许多家庭不可或缺的一员&#xff0c;它们用无条件的爱温暖着我们的心房&#xff0c;陪伴我们度过每一个平凡而温馨的日子。然而&#xff0c;随着宠物活动范围的扩大和外界环境的复杂多变&#xff0c;宠物走失的风险也随之增加。每一次出门遛弯&#xff0c;都像是心…

视频压缩文件太大了怎么缩小?怎么压缩视频大小?视频压缩方法:10个!(宝藏)

视频压缩文件太大了怎么缩小&#xff1f;让我看看是谁下班之后不是一手刷手机短视频&#xff0c;顺便葛优躺在沙发上的&#xff1f;互联网发展到现在&#xff0c;视频已成为我们生活中不可或缺的一部分。不管是视频录制还是视频缓存&#xff0c;视频文件体积越来越庞大&#xf…

微信小程序canvas 使用案例(一)

一、cavans 对象获取、上线文创建 1.wxml <!-- canvas.wxml --><canvas type"2d" id"myCanvas"></canvas> 2.js /*** 生命周期函数--监听页面加载*/onLoad(options) {const query wx.createSelectorQuery()query.select(#myCanvas).f…

DICOM CT\MR片子免费在线查看工具;python pydicom包加载查看;mayavi 3d查看

DICOM CT\MR片子免费在线查看工具 参考&#xff1a; https://zhuanlan.zhihu.com/p/668804209 dicom格式&#xff1a; DICOM&#xff08;Digital Imaging and Communications in Medicine&#xff09;是医学数字成像和通信的标准。它定义了医学图像&#xff08;如CT、MRI、X…

.net6 core Worker Service项目,使用Exchange Web Services (EWS) 分页获取电子邮件收件箱列表,邮件信息字段

Program.cs 安装包&#xff1a;Microsoft.AspNetCore.Hosting.WindowsServices、Microsoft.Extensions.Hosting、Microsoft.Extensions.Hosting.WindowsServices、Microsoft.Extensions.Logging.Log4Net.AspNetCore 新建Configs/log4net.config using Com.Chinahorn.Exchange.W…

【人工智能】机器学习 -- 决策树(乳腺肿瘤数)

目录 一、使用Python开发工具&#xff0c;运行对iris数据进行分类的例子程序dtree.py&#xff0c;熟悉sklearn机器实习开源库。 二、登录https://archive-beta.ics.uci.edu/ 三、使用sklearn机器学习开源库&#xff0c;使用决策树对breast-cancer-wisconsin.data进行分类。 …

docker自建rustdesk-server远程桌面

rustdesk简介 RustDesk 是一款可以平替 TeamViewer 的开源软件&#xff0c;旨在提供安全便捷的自建方案。 RustDesk 是一款功能齐全的远程桌面应用&#xff0c;具有以下特性&#xff1a; 支持 Windows、macOS、Linux、iOS、Android、Web 等多个平台。支持 VP8 / VP9 / AV1 …

JMeter使用手册

安装 下载地址 https://jmeter.apache.org/download_jmeter.cgi 下载后解压到win的文件夹中 打开JMeter的bin文件夹&#xff0c;双击这个jar就启动了JMeter 启动 出现这样的界面 基本使用 添加变量 这个变量在使用的时候可以被引用 创建线程组 所有的请求都得基于…

Harbor系列之1:介绍、架构及工作流程说明

Harbor介绍、架构及工作流程说明 Harbor 是一个用于存储、签名和扫描内容的企业级容器镜像注册表项目。由 VMware 开发并于 2016 年开源。Harbor 提供了一些关键特性&#xff0c;使其成为企业使用的理想选择。 1. Harbor 介绍 1.1 什么是 Harbor Harbor 是一个开源的云原生…

Spring-Boot基础--yaml

目录 Spring-Boot配置文件 注意&#xff1a; YAML简介 YAML基础语法 YAML:数据格式 YAML文件读取配置内容 逐个注入 批量注入 ConfigurationProperties 和value的区别 Spring-Boot配置文件 Spring-Boot中不用编写.xml文件&#xff0c;但是spring-Boot中还是存在.prope…

基于GTX的64B66B编码的自定义接收模块(高速收发器二十二)

点击进入高速收发器系列文章导航界面 1、自定义PHY顶层模块 前文设计了64B66B自定义PHY的发送模块&#xff0c;本文完成自定义PHY剩余的模块的设计&#xff0c;整体设计框图如下所示。 其中phy_tx是自定义PHY的发送数据模块&#xff0c;scrambler是加扰模块&#xff0c;rx_slip…

多口适配器,给您的生活增添便利

随着科技的快速发展&#xff0c;我们的生活已离不开各种各样的电子设备&#xff0c;智能手机、平板电脑、智能手表、无线耳机……它们共同构建了我们丰富多彩的数字生活。然而&#xff0c;面对众多设备的充电需求&#xff0c;传统的单一充电口已难以满足现代人的使用习惯。在这…

使用JWT双令牌机制进行接口请求鉴权

在前后端分离的开发过程中&#xff0c;前端发起请求&#xff0c;调用后端接口&#xff0c;后端在接收请求时&#xff0c;首先需要对收到的请求鉴权&#xff0c;在这种情况先我们可以采用JWT机制来鉴权。 JWT有两种机制&#xff0c;单令牌机制和双令牌机制。 单令牌机制服务端…

IDEA的详细设置

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …

《绝区零》是一款什么类型的游戏,Mac电脑怎么玩《绝区零》苹果电脑玩游戏怎么样

米哈游的《绝区零》最近在网上爆火呀&#xff0c;不过很多人都想知道mac电脑能不能玩《绝区零》&#xff0c;今天麦麦就给大家介绍一下《绝区零》是一款什么样的游戏&#xff0c;Mac电脑怎么玩《绝区零》。 一、《绝区零》是一款什么样的游戏 《绝区零》是由上海米哈游自主研发…

常见排序算法总结

文章目录 比较排序冒泡排序选择排序插入排序归并排序快速排序堆排序希尔排序 非比较排序&#xff08;桶排序&#xff09;计数排序基数排序 比较排序 冒泡排序 嵌套循环&#xff0c;每次内层循环执行时&#xff0c;数组的每两个元素交换&#xff0c;将一个最大/小的数排到数组…

技术成神之路:设计模式(八)责任链模式

介绍 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为设计模式&#xff0c;它允许多个对象依次处理请求&#xff0c;避免请求的发送者和接收者之间的显式耦合。该模式通过将多个可能处理请求的对象连接成一条链&#xff0c;并沿着这条链传递请求…