快速排序---算法

1、算法概念

快速排序:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的数据均比另一部分的数据小,则可分别对这两部分记录继续进行排序,以达到震哥哥序列有序。

        快速排序的最坏运行情况是O(n^{2}),比如说顺序数列的快排。但它的平摊期望时间是O(n\log{n}),且(n\log{n})记号中隐含的常数因子很小,比复杂度稳定等于O(n\log{n})的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是由于归并排序。

2、算法步骤

  • 从数列中挑出一个元素,称为“基准”。
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的书可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区操作
  • 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
public static int[] quicksort(int[] arr,int left,int right){
        if (left < right){
            int p = partition(arr,left,right);
            quicksort(arr,left,p-1);
            quicksort(arr,p+1,right);
        }
        return arr;
    }
public static int partition(int[] arr, int left, int right) {
        //色号顶基准值pivot
        int pivot = left;
        int index = pivot+1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr,i,index);
                index++;
            }
        }
        swap(arr,pivot,index-1);
        return index-1;
    }
public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
}

例题

https://www.lanqiao.cn/problems/3225/learning/

public class _04快速排序 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        arr = quicksort(arr,0,n-1);
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    public static int[] quicksort(int[] arr,int left,int right){
        if (left < right){
            int p = partition(arr,left,right);
            quicksort(arr,left,p-1);
            quicksort(arr,p+1,right);
        }
        return arr;
    }
    public static int partition(int[] arr, int left, int right) {
        //色号顶基准值pivot
        int pivot = left;
        int index = pivot+1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr,i,index);
                index++;
            }
        }
        swap(arr,pivot,index-1);
        return index-1;
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

整数删除,蓝桥杯训练题

题目描述: 给定一个长度为 N 的整数数列&#xff1a;A1,A2,…,AN。 你要重复以下操作 K 次&#xff1a; 每次选择数列中最小的整数&#xff08;如果最小值不止一个&#xff0c;选择最靠前的&#xff09;&#xff0c;将其删除&#xff0c;并把与它相邻的整数加上被删除的数值。 …

【前端面试3+1】06继承方式及优缺点、缓存策略、url输入到渲染全过程、【二叉树中序遍历】

一、继承有哪些方式&#xff1f;以及优缺点 继承的方式包括原型链继承、构造函数继承、组合继承、原型式继承、寄生式继承和组合式继承。 1.原型链继承&#xff1a; 实现方式&#xff1a;将子类的原型指向父类的实例来实现继承。优点&#xff1a;简单易懂&#xff0c;代码量少。…

linux 一些命令

文章目录 linux 一些命令fdisk 磁盘分区parted 分区文件系统mkfs 格式化文件系统fsck 修复文件系统 mount 挂载swap 交换分区清除linux缓存df du 命令raid 命令基本原理硬raid 和 软raid案例raid 10 故障修复&#xff0c;重启与卸载 lvm逻辑卷技术LVM的使用方式LVM 常见名词解析…

wavedec2函数及使用

在MATLAB中&#xff0c;进行小波分解及其逆运算是处理图像的一种常见方法&#xff0c;尤其适用于图像分析、压缩和去噪等场景。wavedec2函数可以对二维信号&#xff08;例如图像&#xff09;进行多级小波分解&#xff0c;而waverec2函数则用于进行相应的逆运算。以下是如何使用…

【树状数组专题】【蓝桥杯备考训练】:数星星、动态求连续区间和、一个简单的整数问题、一个简单的整数问题2【已更新完成】

目录 1、数星星&#xff08;《信息学奥赛一本通》 & ural 1028&#xff09; 思路&#xff1a; 基本思路&#xff1a; 树状数组经典三函数&#xff1a; 1、lowbit()函数 2、query()函数 3、add()函数 最终代码&#xff1a; 2、动态求连续区间和&#xff08;《信息学奥赛一本…

笔记本三屏异显方案——更新中,是否能够在FPGA上实现,淘宝购物的价格太贵

三屏是&#xff08;笔记本电脑屏幕&#xff0c;两个显示器屏幕&#xff09;&#xff0c;异显是采用屏幕的扩展功能&#xff0c;这样能够左边看视频文章&#xff0c;右边control cv代码。 一、 电脑有一个HDMI口的时候&#xff0c;只需要买一个TypeC&#xff08;雷电接口&#x…

ruoyi-nbcio-plus基于vue3的flowable任务监听器的升级修改

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 http://122.227.135.243:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a…

基于Springboot点餐平台网站

采用技术 基于Springboot点餐平台网站的设计与实现~ 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBootMyBatis 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 页面展示效果 菜品评价管理 订单管理 前台首页 管理员登录 用户管理 菜品分…

MATLAB小波包分解及逆向操作

MATLAB代码 % 载入图像 grayImg imread(lena256.bmp); % 替换为你的图像路径% 选择小波函数和分解级别 waveletFunction db1; level 2;% 执行WPT正向分解 wp wpdec2(double(grayImg), level, waveletFunction);% 从小波包分解中重建图像&#xff08;逆向运算&#xff09; r…

【数字IC/FPGA】手撕代码:模3检测器(判断输入序列能否被3整除)

今天我们来手撕一个常见的笔试题&#xff0c;使用的方法是三段式Moore状态机。 题目描述&#xff1a; 输入端口是串行的1bit数据&#xff0c;每个时钟周期进来一位新数据后&#xff0c;实时检查当前序列是否能整除3&#xff0c;若能则输出1&#xff0c;否则输出0。 例如&#…

webpack搭建开发环境

webpack搭建开发环境 一.webpack开发模式二.webpack打包模式三.webpack打包模式应用四.Webpack 前端注入环境变量五.Webpack 开发环境调错 source map六. Webpack 设置解析别名路径七.优化-CDN的使用八.多页面打包九.优化-分割公共代码一.webpack开发模式 作用:启动 Web 服务…

亮数据,可视化数据采集强大利器

前言 随着信息技术的飞速发展&#xff0c;我们已经进入了一个以数据为中心的世纪。在这个时代&#xff0c;数据不仅仅是信息的载体&#xff0c;它已经成为了推动社会进步、创新科技、增强决策和驱动经济增长的关键资源。 在这个数据世纪中&#xff0c;掌握数据的能力等同于掌…

[计算机效率] 文件对比工具:Beyond Compare 4

3.10 文件对比工具&#xff1a;Beyond Compare 4 Beyond Compare 4是一款功能强大的文件和文件夹比较工具&#xff0c;它能够帮助用户在不同系统或版本之间快速比较和同步文件和文件夹。以下是Beyond Compare 4软件的一些主要特点&#xff1a; 文件和文件夹比较&#xff1a;Be…

普发Pfeiffer 真空TCP120-TCP380-TCP035-TCP600 使用手侧

普发Pfeiffer 真空TCP120-TCP380-TCP035-TCP600 使用手侧

MultiPath HTTP:北大与华为合作部署FLEETY

当前的终端基本都能支持蜂窝网络和wifi网络&#xff0c;然而&#xff0c;不同的网络通路都不可避免的会出现信号不好或者其他因素引起的通路性能(吞吐量、时延等)下降。为了能够提升终端业务体验&#xff0c;很多不同的MultiPath方案被提出&#xff0c;其中&#xff0c;包括应用…

程序运行要求,三角形三边的值来自于本地一个文本文件input.txt,三角形类型的值最终存储于本地文本文件out.txt中。

本周完成如下2个实验&#xff1a; 面向对象数据持久化编程&#xff0c;使用java编写程序&#xff0c;完成三角形的类型判断&#xff0c;程序模块要求如下&#xff1a; 创建三角形对象triangle&#xff0c;该对象属性有三边a,b,c&#xff0c;该对象有&#xff1a; 方法1&#xf…

linux 软中断入门

在 linux 中&#xff0c;任务执行的载体有很多&#xff0c;包括线程&#xff0c;中断&#xff0c;软中断&#xff0c;tasklet&#xff0c;定时器等。但是从本质上来划分的话&#xff0c;任务执行的载体只有两个&#xff1a;线程和中断。软中断和 tasklet 的执行可能在中断中&am…

【无限列车1】SpringCloudAlibaba 与 SpringBoot后端架构的搭建

【无限列车1】SpringCloudAlibaba 与 SpringBoot后端架构的搭建 1、版本说明二、日志相关配置3、AOP 打印日志 1、版本说明 【SpringCloud 版本说明】https://sca.aliyun.com/zh-cn/docs/2022.0.0.0-RC1/overview/version-explain &#x1f58a; RC&#xff08;Release Candi…

离散数学--谓词逻辑之复习与前束范式与谓词演算的推理理论

引子&#xff1a;在命题演算中&#xff0c;常常要化成规范形式&#xff0c;对于谓词的演算&#xff0c;可以化成与他等价的范式&#xff01; 前束范式定义&#xff1a; 一个公式&#xff0c;如果量词均非否定地在全式的开头&#xff0c;它们的作用域延伸到整个公式的末尾&…

绘制空心环形

1.通过几个div拼接绘制空心环形进度条。 通过 -webkit-mask: radial-gradient(transparent 150px, #fff 150px);绘制空心圆 html:<body><div class"circle"><div class"circle-left"></div><div class"circle-left-mask&…