快速排序

快速排序

      • 概况
      • 步骤
      • 代码示例
      • 输出结果

要想学习快速排序,前提必须了解 递归算法

概况

快速排序是一种高效的排序算法,它采用了分治的策略。

基本思想是选择一个基准数,通过一趟排序将待排序序列划分成两个子序列,其中一个子序列的所有元素小于基准数,另一个子序列的所有元素大于基准数。然后对这两个子序列递归地应用快速排序算法,直到子序列的长度为1或0,即达到最终的排序结果。

快速排序是一种原地排序算法,它的平均时间复杂度为O(nlogn),其中n是待排序序列的长度。但在最坏情况下,即待排序序列已经有序或近乎有序时,快速排序的时间复杂度为O(n^2),这是因为每次划分都只能减少一个元素的位置。

步骤

其基本步骤如下:

  1. 选择一个基准数(通常是序列的第一个元素)。

  2. 定义两个指针,一个指向序列的起始位置,另一个指向序列的末尾位置。

  3. 从右向左移动右指针,直到找到一个小于基准数的元素。

  4. 从左向右移动左指针,直到找到一个大于基准数的元素。

  5. 交换左右指针所指向的元素。

  6. 重复步骤3、4、5,直到左指针和右指针相遇。

  7. 将基准数和左指针所指向的元素进行交换,使得基准数归位。

  8. 对基准数左边的子序列和右边的子序列递归应用以上步骤,直到子序列的长度为1或0。

  9. 完成排序后,序列就被分成了若干个以基准数为中心的子序列,子序列的元素都已经有序。

黑马程序员阿伟老师制作

代码示例

需求:采用快速排序将下列数据进行排序,数据如下{6, 2, 6, 3, 9, 4, 7, 8, 5, 1, 10}

例如:

package text.text02;/*
快速排序:以0索引的数字为基准数,确定基准数在数组中正确的位置。比基准数小的全部在左边,比基准数大的全部在右边。后面以此类推。
步骤:1. 从数列中挑出一个元素,一般都是左边第一个数字,称为 "基准数";2. 创建两个指针,一个从前往后走,一个从后往前走。3. 先执行后面的指针,找出第一个比基准数小的数字4. 再执行前面的指针,找出第一个比基准数大的数字5. 交换两个指针指向的数字6. 直到两个指针相遇7. 将基准数跟指针指向位置的数字交换位置,称之为:基准数归位。8. 第一轮结束之后,基准数左边的数字都是比基准数小的,基准数右边的数字都是比基准数大的。9. 把基准数左边看做一个序列,把基准数右边看做一个序列,按照刚刚的规则递归排序*/
public class text15A {public static void main(String[] args) {int[] arr = {6, 2, 6, 3, 9, 4, 7, 8, 5, 1, 10};//调用quickSort方法quickSort(arr, 0, arr.length - 1);//遍历数组输出数组数据for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + "  ");      //1  2  3  4  5  6  6  7  8  9  10}}//创建快速排序方法quickSortpublic static void quickSort(int[] arr, int startIndex, int endIndex) {//定义变量接受startIndex和endIndex,方便以后递归int i = startIndex;int j = endIndex;//起始索引大于结束索引,说明遍历完成,结束方法(出口)if (startIndex > endIndex) {return;}//定义个变量记录基准数int number = arr[startIndex];//当起始索引小于结束索引时while (startIndex < endIndex) {//当起始索引小于结束索引并且从右向左遍历时的某个数大于基准数时while (startIndex < endIndex && arr[endIndex] >= number) {endIndex--;}//当起始索引小于结束索引并且从左向右遍历时的某个数小于基准数时while (startIndex < endIndex && arr[startIndex] <= number) {startIndex++;}//将从右向左遍历时大于基准数的某个数与从左向右遍历时小于基准数的某个数进行交换int temp = arr[endIndex];arr[endIndex] = arr[startIndex];arr[startIndex] = temp;}//当起始索引与结束索引相等时,将其对应的数与基准数进行交换int num = arr[startIndex];arr[startIndex] = number;arr[i] = num;//在基准数左边的数接着递归调用该方法quickSort(arr, i, startIndex - 1);//在基准数右边的数接着递归调用该方法quickSort(arr, startIndex + 1, j);}
}

输出结果

在这里插入图片描述
流程图:

开始
├─ 定义快速排序方法 quickSort
│    ├─ 如果起始索引大于结束索引,返回
│    ├─ 选择数组中的一个元素作为基准数
│    ├─ 定义指针 i 指向起始索引
│    ├─ 定义指针 j 指向结束索引
│    ├─ 循环直到指针 i 和 j 相遇
│    │    ├─ 从右向左移动指针 j,找到一个比基准数小的数字
│    │    ├─ 从左向右移动指针 i,找到一个比基准数大的数字
│    │    ├─ 如果指针 i 和 j 没有相遇
│    │    │    ├─ 交换指针 i 和指针 j 指向的数字
│    ├─ 交换基准数与指针 i 指向的数字,基准数归位
│    ├─ 递归调用 quickSort 方法,对基准数左边的序列进行排序
│    ├─ 递归调用 quickSort 方法,对基准数右边的序列进行排序
├─ 创建数组 arr
├─ 调用 quickSort 方法,对数组 arr 进行排序
├─ 遍历数组 arr,输出排序后的数据
结束

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

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

相关文章

乔迁新居发言

亲爱的家人们&#xff0c;大家好&#xff01; 非常感谢大家在百忙之中抽出宝贵的时间来到这里为我们的新居增添福气。我代表我和田小帆对大家的到来表示热烈的欢迎和衷心的感谢。 在这个特殊的时刻&#xff0c;我对我们小家庭建设过程中帮助我们的所有亲人、朋友和同学们表示由…

大模型实战营Day6 笔记

本期主题为&#xff1a; 为何测评&#xff0c;因场景众多&#xff0c;需要统一的标准&#xff1a; 评测的意义&#xff1a; 传统NLP的一些评测需要&#xff1a; 到了大模型时代&#xff0c;需要评测的就更多了&#xff1a; 客观评测&#xff1a; 有些主观题可以用模型评价…

Shell脚本的条件语句-------if语句与case语句

目录 一、if语句 1、bash的配置文件 2、单分支结构 3、双分支结构 4、多分支结构 ①单分支应用举例&#xff1a;写一个脚本检查80端口是否开启&#xff0c;如果开启则反馈http正在运行&#xff0c;否则启动httpd服务 ②多分支应用例子&#xff1a;90-100 是优秀 70-89…

FlinkAPI开发之状态管理

案例用到的测试数据请参考文章&#xff1a; Flink自定义Source模拟数据流 原文链接&#xff1a;https://blog.csdn.net/m0_52606060/article/details/135436048 Flink中的状态 概述 有状态的算子 状态的分类 托管状态&#xff08;Managed State&#xff09;和原始状态&…

springboot123基于springboot框架的网上商城系统的设计与实现

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的基于springboot框架的网上商城系统的设计与实现 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看…

centos7.9安装redmine5.1.1

前提&#xff1a; 安装mysql并新建数据库--教程太多了此步骤省略&#xff1b; 用sqlyog连上mysql创建数据库redmine&#xff1b; 1.下载redmine-5.1.1.tar.gz&#xff0c;上传到/usr/local/software目录下&#xff1b; 2.解压 cd /usr/local/software tar -zxvf redmine-5.…

架构师的36项修炼-06高性能系统架构设计

本课时讲解大家常听到的高性能系统架构。 高性能系统架构&#xff0c;主要包括两部分内容&#xff0c;性能测试与性能优化。性能优化又可以细分为硬件优化、中间件优化、架构优化及代码优化&#xff0c;知识架构图如下。 性能测试 先看系统的性能测试。性能测试是性能优化的…

Mybatis 动态SQL条件查询(注释和XML方式都有)

需求 : 根据用户的输入情况进行条件查询 新建了一个 userInfo2Mapper 接口,然后写下如下代码,声明 selectByCondition 这个方法 package com.example.mybatisdemo.mapper; import com.example.mybatisdemo.model.UserInfo; import org.apache.ibatis.annotations.*; import j…

GetShell的姿势

0x00 什么是WebShell 渗透测试工作的一个阶段性目标就是获取目标服务器的操作控制权限&#xff0c;于是WebShell便应运而生。Webshell中的WEB就是web服务&#xff0c;shell就是管理攻击者与操作系统之间的交互。Webshell被称为攻击者通过Web服务器端口对Web服务器有一定的操作权…

AnimatedDrawings:让绘图动起来

老样子&#xff0c;先上图片和官网。这个项目是让绘制的动画图片动起来&#xff0c;还能绑定人体的运动进行行为定制。 快速开始 1. 下载代码并进入文件夹&#xff0c;启动一键安装 git clone https://github.com/facebookresearch/AnimatedDrawings.gitcd AnimatedDrawingspip…

python批量处理修改pdf内容

将PDF转换为Word&#xff1a; 使用pdf2docx库中的Converter类来进行PDF转换。convert_pdf_to_docx函数接受PDF文件路径和输出的Word文档路径作为参数。通过调用Converter对象的convert方法将PDF转换为Docx格式。最后调用close方法关闭Converter对象并保存转换后的文档。 将Word…

一文读懂RabbitMQ核心概念及架构

1. RabbitMQ简介 RabbitMQ是一个开源的消息代理软件&#xff0c;实现了高级消息队列协议&#xff08;AMQP&#xff09;。它是一个应用程序对应用程序的通信方法&#xff0c;基于消费-生产者模型。在RabbitMQ中&#xff0c;消息的生产者将消息发布到队列中&#xff0c;而消息的…

【zlm】针对单个设备的码率的设置

目录 代码修改 实验数据一 实验数据二 同时拉一路视频后 修改记录 使用方法 各库实操 代码修改 要被子类引用 &#xff0c;所以放在protected 不能放private 下面的结论&#xff0c;可以在下面的实验数据里引用。“同时拉一路视频后” 实验数据一 https://10.60.3.45:1…

共话 AI for Science | 北京大学王超名:BrainPy,迈向数字化大脑的计算基础设施

导读&#xff1a; 2023 和鲸社区年度科研闭门会以“对话 AI for Science 先行者&#xff0c;如何抓住科研范式新机遇”为主题&#xff0c;邀请了多个领域的专家学者共同探讨人工智能在各自领域的发展现状与未来趋势。 在脑科学领域&#xff0c;数字化大脑通过数学模型和计算机…

Matplotlib Mastery: 从基础到高级的数据可视化指南【第30篇—python:数据可视化】

文章目录 Matplotlib: 强大的数据可视化工具1. 基础1.1 安装Matplotlib1.2 创建第一个简单的图表1.3 图表的基本组件&#xff1a;标题、轴标签、图例 2. 常见图表类型2.1 折线图2.2 散点图2.3 条形图2.4 直方图 3. 图表样式与定制3.1 颜色、线型、标记的定制3.2 背景样式与颜色…

【JavaEE进阶】 MyBatis使用XML实现增删改查

文章目录 &#x1f38d;前言&#x1f340;配置连接字符串和MyBatis&#x1f343;写持久层代码&#x1f6a9;添加mapper接⼝&#x1f6a9;添加UserInfoXMLMapper.xml&#x1f6a9;单元测试 &#x1f334;增(Insert&#xff09;&#x1f6a9;返回⾃增id &#x1f38b;删(Delete)&…

JAVA_LinkedList添加元素源码分析(jdk17)

目录 先看一些重要的源码&#xff1a; 开始分析&#xff1a; 底层数据结构是双链表&#xff0c;查询慢&#xff0c;首尾操作是极快的&#xff0c;所以多了很多首尾操作的特有 Api&#xff1a; addlast 和 add 一样元素默认添加到末尾&#xff0c;了解即可。 先看一些重要的源…

vue3源码(二)reactiveeffect

一.reactive与effect功能 reactive方法会将对象变成proxy对象&#xff0c; effect中使用reactive对象时会进行依赖收集&#xff0c;稍后属性变化时会重新执行effect函数。 <div id"app"></div><script type"module">import {reactive,…

web开发学习笔记(14.mybatis基于xml配置)

1.基本介绍 2.基本使用 在mapper中定义 在xml中定义&#xff0c;id为方法名&#xff0c;resultType为实体类的路径 在测试类中写 3. 动态sql&#xff0c;if和where关键字 动态sql添加<where>关键字可以自动产生where和过滤and或者or关键字 where关键字可以动态生成whe…

C++面试:跳表

目录 跳表介绍 跳表的特点&#xff1a; 跳表的应用场景&#xff1a; C 代码示例&#xff1a; 跳表的特性 跳表示例 总结 跳表&#xff08;Skip List&#xff09;是一种支持快速搜索、插入和删除的数据结构&#xff0c;具有相对简单的实现和较高的查询性能。下面是跳表…