交换排序详讲:冒泡排序+快速排序(多方法+思路+图解+代码)

文章目录

  • 交换排序
      • 一.冒泡排序
      • 二.快速排序
          • 1.挖坑法
          • 2.Hoare法


交换排序


  • 根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
  • 将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

一.冒泡排序

在这里插入图片描述

    /**
     * 冒泡排序
     * 时间复杂度 n^2
     * 空间复杂度  1
     * @param array
     */
    public static void bubbleSort(int[]array){
        for (int i = 0; i < array.length-1; i++) {//趟数
            boolean flg =false;
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if (flg == false){
                return;
            }
        }
    }


1.遍历 i 代表交换的趟数,遍历 j 进行两两交换

2.j < array.length-1-i 是对于趟数的优化,每走一趟,交换就少一次

3.boolean flg =false;当两两交换时,flg变为true

4.进一步优化:如果遍历完,没发生交换,flg还是false,直接返回,排序结束

  • 时间复杂度:O ( N2 )
  • 空间复杂度:O ( 1 )
  • 稳定性:稳定

二.快速排序

  • 二叉树结构的交换排序方法

  • 任取一个待排序元素作为基准值,把序列一分为二,左子序都比基准值小,右子序都比基准值大,左右两边再重复进行

在这里插入图片描述

  • 左边找比基准值大的,右边找比基准值小的
1.挖坑法

在这里插入图片描述

  • 基准值位置挖一个坑,后面找一个比基准值小的把坑埋上
  • 前面找一个比基准值大的,埋后面的坑
  • 当l==r时,把基准值填入剩下的坑中

在这里插入图片描述

  • 左右两边重复进行上述步骤,直到排完为止
  • 左右两边都以同样的方法进行划分,运用递归来实现
    /**
     * 快速排序 ---挖坑法
     *
     * @param array
     */

    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;//结束条件
            // start == end,说明只剩一个了,是有序的,返回
            //start > end ,说明此时的基准值在开头或者末尾
            //在开头:start不变,end=pivot-1,start > end ,end=-1 没有左树
            //在结尾:end不变,start = pivot+1,start > end,超出索引,没有右树
        }
        //不断递归quick
        int pivot = partition(array, start, end);// 进行排序,划分找到pivot
        //然后递归划分法左边,递归划分的右边
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //划分,返回基准值
    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];//挖一个坑,取left位置为基准值
        while (left < right) {
            //在右边找一个比基准值小的把坑填上
            while (left < right && array[right] >= tmp) {//防止越界
                right--;
            }
            array[left] = array[right];//找到比tmp小的数,填坑,

            //在左边找一个比tmp大的值,填到右边的坑
            while (left < right && array[left] <= tmp) {//防止越界
                left++;
            }
            array[right] = array[left];
        }//如果相遇了,退出循环
        array[left] = tmp;//填坑
        return left;
    }

  • 先划分序列,递归左边,然后再递归右边

  • 递归结束条件:

    start == end时,说明只剩一个了,是有序的,返回
    start > end 时 ,说明此时的基准值在开头或者末尾

    如果基准值在开头:start不变,end=pivot-1,start > end ,end=-1 没有左树
    如果基准值在结尾:end不变,start = pivot+1,start > end,超出索引,没有右树


2.Hoare法

在这里插入图片描述

  • 不同的方法,找出基准值,排的序列是不一样的

在这里插入图片描述

  • i记录基准值一开始在left位置的下标
  • r找到比基准值小的停下来,l找到比基准值大的停下来,互相交换
  • l和r相遇的时候,把i 记录基准值的初始下标和相遇位置交换

以左边为基准,先找右边再找左边,相遇的位置就是以右边为基准的值,要比基准小,才能交换

    /**
     * Hoare法 划分排序找基准值
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition2(int[] array, int left, int right) {
        int tmp = array[left];
        int i  = left;//记录基准值一开始在left位置的下标
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,i,left);
        return left;
    }

点击移步博客主页,欢迎光临~

偷cyk的图

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

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

相关文章

【开源】基于JAVA的大学兼职教师管理系统

项目编号&#xff1a; S 004 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S004&#xff0c;文末获取源码。} 项目编号&#xff1a;S004&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、研究内容三、界面展示3.1 登录注册3.2 学生教师管…

《effective C++》条款10

令operator返回一个reference to *this int main() {int a, b, c 5;a b c;cout << a; } 这个代码&#xff0c;很明显输出的是5。所以我们在写这种连续赋值的时候&#xff0c;其对应的赋值运算符应当返回一个*this &#xff1a; class A { public:A(string ss, int x) …

vs2017打开工程提示若要解决此问题,请使用以下选择启动 Visual Studio 安装程序: 用于 x86 和 x64 的 Visual C++ MFC

下载 error MSB8036: 找不到 Windows SDK 版本8.1。请安装所需的版本的 Windows SDK 或者在项目属性页中或通过右键单击解决方案并选择“重定解决方案目标”来更改 SDK 版本。 error&#xff1a;D8016 “/ZI”和“/Gy-”命令行选项不兼容 ”问题解决

linux systemd start stop enable disable命令区别

一、systemd 的服务在三个文件件下 /lib/systemd/system /etc/systemd/system /usr/lib/systemd/system 终于明白这几个命令的区别 systemd star systemd stop systemd enable systemd disable 二、 1、用ssh服务为例&#xff0c;&#xff0c;ssh是客户端&#xff0c;远程ss…

delphi电子处方流转(医院)

【delphi电子处方流转(医院)】支持 就诊登记、电子处方上传预核验、处方处方医保电子签名、电子处方上传、电子处方撤销、电子处方信息查询、电子处方审核结果查询、电子处方取药结果查询、电子处方药品目录查询等功能。

短视频账号矩阵系统源码

短视频账号矩阵系统源码搭建步骤包括以下几个方面&#xff1a; 1. 确定账号类型和目标受众&#xff1a;确定要运营的短视频账号类型&#xff0c;如搞笑、美食、美妆等&#xff0c;并明确目标受众和定位。 2. 准备账号资料&#xff1a;准备相关资质和资料&#xff0c;如营业执照…

数据结构--栈与队列

目录 前言 1.栈 1.1栈的概念及结构 1.2接口函数 1.3函数实现 1.4如何使用 2.队列 2.1队列的概念及结构 2.2接口函数 2.3函数实现 2.4如何使用 前言 前面我们已经学习了顺序表和链表&#xff0c;今天我们来学习栈与队列&#xff0c;这两种结构也属于线性表&#xff0c;实…

解决windeployqt打包exe的“VCINSTALLDIR is not set“问题

今天在使用windeployqt部署qt的.exe文件时&#xff0c; 出现如下错误&#xff1a; windeployqt HelloQt.exe图(1) 报"VCINSTALLDIR路径"找不到 出现这种情况的原因是&#xff1a;VCINSTALLDIR环境没有配置&#xff0c;需要把Visual Studio的编译路径: ## 1) 社区版…

2018年五一杯数学建模A题徐州潘安湖风景区游览路线设计解题全过程文档及程序

2019年五一杯数学建模 A题 徐州潘安湖风景区游览路线设计 原题再现 徐州是一个老工业基地和资源型城市&#xff0c;煤炭开采历史长达130年。长期煤炭开采在徐州累计形成采煤塌陷区达数十万亩。位于徐州市贾汪区西南部、紧邻马庄的潘安湖湿地公园原来就是徐州最大的、塌陷最严…

关系代数、SQL语句和Go语言示例

近些年&#xff0c;数据库领域发展日新月异&#xff0c;除传统的关系型数据库外&#xff0c;还出现了许多新型的数据库&#xff0c;比如&#xff1a;以HBase、Cassandra、MongoDB为代表的NoSQL数据库&#xff0c;以InfluxDB、TDEngine为代表的时序数据[1]库&#xff0c;以Neo4J…

【UE5】物体沿样条线移动

目录 效果 步骤 一、使用样条线创建路径 二、创建沿样条线路径移动的物体 三、定义可移动物体的生成器 效果 步骤 一、使用样条线创建路径 先创建一个Actor蓝图&#xff0c;这里命名为“BP_Line” 该蓝图中只需添加一个样条组件 将“BP_Line”拖入场景中 按住Alt鼠标左键…

生存分析后如何绘制亚组森林图?小白也能快速搞定!(附教程)

本周为大家重点介绍一下风暴统计平台的最新板块——亚组森林图&#xff01; 现在亚组分析好像越来越流行&#xff0c;无论是观察性研究还是RCT研究&#xff0c;亚组分析一般配备森林图。 比如这张图&#xff1a; 还有这个&#xff1a; 森林图不仅是画图的画法&#xff0c;背后还…

Javaweb之Vue指令的详细解析

2.3 Vue指令 在上述的快速入门中&#xff0c;我们发现了html中输入了一个没有学过的属性v-model&#xff0c;这个就是vue的指令。 指令&#xff1a;HTML 标签上带有 v- 前缀的特殊属性&#xff0c;不同指令具有不同含义。例如&#xff1a;v-if&#xff0c;v-for… 在vue中&a…

Zookeeper Java 开发,自定义分布式锁示例

文章目录 一、概述二、导入依赖包三、创建锁的过程3.1 通过 create 创建节点信息3.2 AsyncCallback.StringCallback 回调函数3.3 AsyncCallback.Children2Callback 的回调函数3.4 Watcher 的回调函数 四、完整示例4.1 完整分布式锁代码4.2 测试类 如果您还没有安装Zookeeper请看…

第四章 串【24王道数据结构笔记】

1.串的基本概念 串&#xff0c;即字符串 (String) 是由零个或多个字符组成的有限序列。一般记为Sa1a2.....an(n>0) S"HelloWorld!" TiPhone 11 Pro Max? 其中&#xff0c;S是串名&#xff0c;单引号括起来的字符序列是串的值;a;可以是字母、数字或其他字符;串中…

智能售货柜:小本投资的不二之选

智能售货柜&#xff1a;小本投资的不二之选 智能售货柜的运营优势在于&#xff1a;一是降低运营成本&#xff0c;不需要大量员工&#xff1b;二是具备自动识别和智能结算功能&#xff0c;提高运营效率&#xff1b;三是提供数据分析&#xff0c;优化产品和服务。相比传统零售店&…

初学UE5 C++②

目录 导入csv表格数据 创建、实例化、结构体 GameInstance Actor camera 绑定滚轮控制摇臂移动 碰撞绑定 角色碰撞设定 按钮 UI显示 单播代理 多播和动态多播 写一个接口 其他 NewObject 和 CreateDefaultSubobject区别 导入csv表格数据 创建一个object的C类 …

怎样备份电脑文件比较安全

域智盾软件是一款功能强大的电脑监控软件&#xff0c;它不仅具备实时屏幕监控、行为审计等功能&#xff0c;还能够对电脑文件进行备份和管理。下面将介绍域智盾软件如何备份电脑文件&#xff0c;以确保数据安全。 1、开启文档备份功能 部署后台&#xff0c;然后点击文档安全&a…

30天黑客(网络安全)自学

前言 前几天发布了一篇 网络安全&#xff08;黑客&#xff09;自学 没想到收到了许多人的私信想要学习网安黑客技术&#xff01;却不知道从哪里开始学起&#xff01;怎么学 今天给大家分享一下&#xff0c;很多人上来就说想学习黑客&#xff0c;但是连方向都没搞清楚就开始学习…

科技创新 共铸典范 | 江西卫健办邓敏、飞图影像董事长洪诗诗一行到访拓世科技集团,提振公共卫生事业发展

2023年11月15日&#xff0c;拓世科技集团总部迎来了江西省卫健项目办项目负责人邓敏、江西飞图影像科技有限公司董事长洪诗诗一行的考察参观&#xff0c;集团董事长李火亮、集团高级副总裁方高强进行热情接待。此次多方交流&#xff0c;旨在共同探讨携手合作&#xff0c;激发科…