快速排序(数据结构)

1. 前言:

这两种排序经常使用,且在算法题中经常遇见。
这里我们简单分析讨论一下。

1. 快速排序

平均时间复杂度:O(nlogn)
最坏时间复杂度: O(n^2)

在这里插入图片描述

1.1. 左右向中遍历:

  1. 取最右侧4为基础元素,取出后,4的位置为null。
  2. 从有空的另一侧开始遍历比较,如果左侧3的元素小于基准元素4,则不变化,反之则把左侧元素交换到右侧,左侧为null。
  3. 然后从右侧开始遍历。
  4. 反复,直到low,high指针相遇。

这种方式易于理解却不便于书写,需要反复判断是向左遍历还是向右遍历。

public class QuickSortVariant {

    public static void main(String[] args) {
        int[] arr = {1, 3, 6, 2, 4};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最右侧元素作为基准
        int left = low;
        int right = high - 1;

        while (left < right) {
            // 从左侧寻找大于基准的元素
            while (arr[left] <= pivot && left < right) {
                left++;
            }
            // 从右侧寻找小于基准的元素
            while (arr[right] >= pivot && left < right) {
                right--;
            }
            // 交换左右找到的元素
            swap(arr, left, right);
        }

        // 如果最后左指针指向的元素大于基准,与基准交换
        if (arr[left] >= pivot) {
            swap(arr, left, high);
        } else {
            left++;
        }

        return left; // 返回基准元素的最终位置
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

1.1. 单侧遍历:

在这里插入图片描述
这种遍历理解麻烦点,书写却简单点。

  1. i 指针指向小于base元素的结尾。这里我指向了数组前的一个元素,这不是错误,而是一个巧妙的设计。
  2. 如果 j 指针指向的元素小于base,则 i 指针扩充一个元素,即i++,然后swap(i,j)一般情况下二者是重合的。
  3. 如果遇见大于base的指针,则j++,i 不变,等效与记录了这个大元素指针的位置,再遇到小的元素可以通过swap(i,j)交换,这时,则真正起作用。
public class Solution {
    public static void main(String[] args) {
        int []arr = new int[]{1,3,6,2,4};
        sort(arr,0,4);
        System.out.println(Arrays.toString(arr));
    }

    public  static void sort(int[]arr,int low, int high){
        int baseIndex = quickSort(arr,low,high);
        quickSort(arr,low,baseIndex-1);
        quickSort(arr,baseIndex + 1,high);
    }
    public static int quickSort(int[]arr,int low, int high){
        int base = arr[high];
        int i = low - 1;
        for(int j = low; j < arr.length - 1; j++){
            if(arr[j] < base){
                i++;
                swap(arr,i,j);
            }
        }
        swap(arr,high,i + 1);
        return i + 1;



    }
    public static void swap(int[]arr,int index0, int index1){
        int tem = arr[index0];
        arr[index0] = arr[index1];
        arr[index1] = tem;
    }

}

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

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

相关文章

Multiplicity - 用一个键盘和鼠标控制多台电脑

Multiplicity 是一款用于多台电脑间控制的软件。通过这个工具&#xff0c;用户可以轻松地在多个计算机之间共享剪贴板、鼠标、键盘和显示屏幕。这样&#xff0c;无需每台电脑之间频繁切换&#xff0c;工作效率也会大大提高。 特征 远程PC访问 无缝控制过渡 兼容所有显示类型…

【Linux杂货铺】进程的基本概念

目录 &#x1f308;前言&#x1f308; &#x1f4c1;进程的概念 &#x1f4c2;描述进程-PCB &#x1f4c2; 查看进程 &#x1f4c2; 查看正在运行的程序 &#x1f4c2;杀死进程 &#x1f4c2;通过系统调用获取进程标识符 &#x1f4c2;通过系统调用创建进程 &#x1f…

万界星空科技商业开源MES,技术支持+项目合作

商业开源的一套超有价值的JAVA制造执行MES系统源码 亲测 带本地部署搭建教程 教你如何在本地运行运行起来。 开发环境&#xff1a;jdk11tomcatmysql8springbootmaven 可以免费使用&#xff0c;需要源码价格便宜&#xff0c;私信我获取。 一、系统概述&#xff1a; MES制造执…

机器学习(26)回顾gan+文献阅读

文章目录 摘要Abstract一、李宏毅机器学习——GAN1. Introduce1.1 Network as Generator1.2 Why distribution 2. Generative Adversarial Network2.1 Unconditional generation2.2 Basic idea of GAN 二、文献阅读1. 题目2. abstract3. 网络架构3.1 Theoretical Results 4. 文…

学习数据结构和算法的第16天

单链表的实现 链表的基本结构 #pragma once #include<stdio.h> #include<stlib.h> typedf int SLTDataType; typedy struct SListNode {SLTDataType data;struct SListNode*next; }SLTNode;void Slisprint(SLTNode*phead); void SListPushBack(SLTNode**pphead,S…

使用 VS Code + Github 搭建个人博客

搭建个人博客的方案 现在&#xff0c;搭建个人博客的方式有很多&#xff0c;门槛也很低。 可以选择已有平台&#xff1a; 掘金语雀知乎简书博客园SegmentFault… 也可以选择一些主流的博客框架&#xff0c;自行搭建。 HexoGitBookVuePressdumi… 如何选择&#xff1f; 我…

每日五道java面试题之mybatis篇(三)

目录&#xff1a; 第一题. MyBatis的框架架构设计是怎么样的?第二题. 为什么需要预编译?第三题. Mybatis都有哪些Executor执行器&#xff1f;它们之间的区别是什么&#xff1f;第四题. Mybatis中如何指定使用哪一种Executor执行器&#xff1f;第五题. Mybatis是否支持延迟加载…

如何学习一个大型分布式Java项目

前言 很多同学在没有实习经验的时候看到一个多模块分布式项目总是有一种老虎吃天的无力感&#xff0c;就像我刚毕业去到公司接触项目的时候一样&#xff0c;模块多的夸张&#xff0c;想学都不知道从哪开始学&#xff0c;那么我们拿到一份代码后如何从头开始学习一个新项目呢。…

挑战杯 机器视觉目标检测 - opencv 深度学习

文章目录 0 前言2 目标检测概念3 目标分类、定位、检测示例4 传统目标检测5 两类目标检测算法5.1 相关研究5.1.1 选择性搜索5.1.2 OverFeat 5.2 基于区域提名的方法5.2.1 R-CNN5.2.2 SPP-net5.2.3 Fast R-CNN 5.3 端到端的方法YOLOSSD 6 人体检测结果7 最后 0 前言 &#x1f5…

【鸿蒙HarmonyOS开发笔记】常用组件介绍篇 —— Button按钮组件

概述 Button为按钮组件&#xff0c;通常用于响应用户的点击操作。 参数 Button组件有两种使用方式&#xff0c;分别是不包含子组件和包含子组件&#xff0c;两种方式下&#xff0c;Button 组件所需的参数有所不同&#xff0c;下面分别介绍 不包含子组件 不包含子组件时&…

解决 Nginx 1.24 版本下载视频慢和文件问题的方法

解决 Nginx 1.24 版本下载视频慢和文件问题的方法 如果你最近在腾讯云服务器上遇到了下载视频慢以及视频文件无法正常使用的问题&#xff0c;可能需要检查一下你的 Nginx 版本。下面是一个真实案例的分析和解决方案&#xff0c;希望能帮助你避免或解决类似问题。 背景 一个运…

使用gitee自动备份文件

需求 舍友磁盘前两天gg了&#xff0c;里面的论文没有本地备份&#xff0c;最后费劲巴拉的在坚果云上找到了很早前的版本。我说可以上传到github&#xff0c;建一个私人仓库就行了&#xff0c;安全性应该有保证&#xff0c;毕竟不是啥学术大亨&#xff0c;不会有人偷你论文。但是…

从JVM的退出机制分析Java程序的优雅关闭退出

前言 Java程序启动从main函数开始启动&#xff0c;是程序入口和主线程&#xff0c;但程序会在什么时候结束&#xff1f;为什么有的Java程序在启动后很快就结束了&#xff0c;比如HelloWorld程序&#xff0c;有的程序却能一直在运行&#xff0c;比如Tomcat启动后就一直保持进程…

AI:149-法律电子邮件图像中的欺诈检测与敲诈勒索追踪—深度学习技术

🚀点击这里跳转到本专栏,可查阅专栏顶置最新的指南宝典~ 🎉🎊🎉 你的技术旅程将在这里启航! 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带关键代码,详细讲解供大家学习,希望…

JSONP漏洞详解

目录 同源策略 JSONP简介 JSONP劫持漏洞 漏洞原理 漏洞利用过程 利用工具 JSONP漏洞挖掘思路 JSONP防御 首先&#xff0c;要了解一下什么是同源策略&#xff1f; 同源策略 同源策略&#xff08;SOP&#xff09;是浏览器的一个安全基石&#xff0c;浏览器为了保证数据…

AI系统性学习01- Prompt Engineering

文章目录 面向开发者的Prompt Engineering一、简介二、Prompt设计原则1 环境配置2.两个基本原则2.1 原则1&#xff1a;编写清晰、具体的指令2.1.1 策略一&#xff1a;分割2.1.2 策略2&#xff1a;结构化输出2.1.3 策略3&#xff1a;模型检测2.1.4 策略4&#xff1a;提供示例 2.…

[数据集][目标检测]焊接件表面缺陷检测数据集VOC+YOLO格式2292张10类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;2292 标注数量(xml文件个数)&#xff1a;2292 标注数量(txt文件个数)&#xff1a;2292 标注…

【GPT-SOVITS-03】SOVITS 模块-生成模型解析

说明&#xff1a;该系列文章从本人知乎账号迁入&#xff0c;主要原因是知乎图片附件过于模糊。 知乎专栏地址&#xff1a; 语音生成专栏 系列文章地址&#xff1a; 【GPT-SOVITS-01】源码梳理 【GPT-SOVITS-02】GPT模块解析 【GPT-SOVITS-03】SOVITS 模块-生成模型解析 【G…

【PyTorch】进阶学习:一文详细介绍 torch.load() 的应用场景、实战代码示例

【PyTorch】进阶学习&#xff1a;一文详细介绍 torch.load() 的应用场景、实战代码示例 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程…

栈和队列(Java实现)

栈和队列&#xff08;Java实现&#xff09; 栈 栈(Stack)&#xff1a;栈是先进后出&#xff08;FILO, First In Last Out&#xff09;的数据结构。Java中实现栈有以下两种方式&#xff1a; stack类LinkedList实现&#xff08;继承了Deque接口&#xff09; &#xff08;1&am…