6.归并+快排

5. 归并排序

核心思想

将无序数组从中间分为左右两个部分，分别给左右两个部分排序，排序以后把两个有序区间进行合并
在这里插入图片描述

  1. 把数组从中间分为左右两部分
  2. 分别对前后两部分进行排序
  3. 将排好序的两部分合并

在这里插入图片描述
包含两个部分：拆解阶段和合并阶段

归并排序的递归性质

在这里插入图片描述

归并排序递归代码逻辑

在这里插入图片描述

public class MergeSorter {
    public void sort(int[] data){
        if(data == null || data.length<2) return;
        sort(data,0,data.length-1); //大问题
    }

    //给子数组进行排序，子区间
    private void sort(int[] data,int left,int right){
        //1.终止递归条件
        if(left == right) return;

        //2.分别对两个子问题求解
        int mid = (left + right) / 2;
        sort(data,left,mid);
        sort(data,mid+1,right);

        //3.合并两个有序的数组，即合并[left...mid] 和 [mid+1...right]
        //[left...mid] 和 [mid+1,right]这两个数组在上面已经排好序了
        merge(data,left,mid,right);
    }

    private void merge(int[] data, int left, int mid, int right) {

    }
}

在这里插入图片描述

归并排序合并的逻辑

以最后一次合并为例：

  1. 定义两个指针i和j，i指针用来遍历前半部分的数据，j指针用来遍历后半部分的数据
  2. 申请一个额外数组tmp用来存放排好序的数据，(注意这里是每次合并都需要去申请一个额外的临时数组)
  3. 对比i指针和j指针指向元素哪个大，谁小就把谁存入额外数组中
  4. 排序完成后将额外数组tmp中的元素再挨个复制到原来的数组中去
//合并
private void merge(int[] data, int left, int mid, int right) {
    int num = right - left + 1;
    //临时数组tmp
    int[] tmp = new int[num];
    //临时数组指针
    int tmpPos = 0;
    //i指针遍历前半部分
    int i = left;
    //j指针遍历后半部分
    int j = mid + 1;
    //将左边和右边的元素按照顺序拷贝到临时数组中
    while (i<=mid && j<=right){
        if(data[i] <= data[j]){
            tmp[tmpPos++] = data[i++];
        }else{  // data[i] > data[j]
            tmp[tmpPos++] = data[j++];
        }
    }
    //如果左边还有元素，则直接将左边的元素拷贝到临时数组
    while (i<=mid){
        tmp[tmpPos++] = data[i++];
    }
    //如果左边还有元素，则直接将右边的元素拷贝到临时数组
    while (j<=right){
        tmp[tmpPos++] = data[j++];
    }
}

归并排序拷贝实现

在这里插入图片描述

public class MergeSorter {
    public void sort(int[] data){
        if(data == null || data.length<2) return;
        sort(data,0,data.length-1); //大问题
    }

    //给子数组进行排序，子问题
    private void sort(int[] data,int left,int right){
        //终止递归条件
        if(left == right) return;

        //分别对两个子问题求解
        int mid = (left + right) / 2;
        sort(data,left,mid);
        sort(data,mid+1,right);

        //合并两个有序的数组，即合并[left...mid] 和 [mid+1...right]
        //[left...mid] 和 [mid+1,right]这两个数组在上面已经排好序了
        merge(data,left,mid,right);
    }

    //合并
    private void merge(int[] data, int left, int mid, int right) {
        int num = right - left + 1;
        //临时数组tmp
        int[] tmp = new int[num];
        //临时数组指针
        int tmpPos = 0;
        //i指针遍历前半部分
        int i = left;
        //j指针遍历后半部分
        int j = mid + 1;
        //将左边和右边的元素按照顺序拷贝到临时数组中
        while (i<=mid && j<=right){
            if(data[i] <= data[j]){
                tmp[tmpPos++] = data[i++];
            }else{  // data[i] > data[j]
                tmp[tmpPos++] = data[j++];
            }
        }
        //如果左边还有元素，则直接将左边的元素拷贝到临时数组
        while (i<=mid){
            tmp[tmpPos++] = data[i++];
        }
        //如果左边还有元素，则直接将右边的元素拷贝到临时数组
        while (j<=right){
            tmp[tmpPos++] = data[j++];
        }

        //拷贝
        for (tmpPos = 0; tmpPos < tmp.length; tmpPos++) {
            data[left++] = tmp[tmpPos];
        }
    }
}

归并排序临时数组优化

一次性申请一个和原始输入数组长度一样的临时数组，后面合并就不再申请了
例如合并后四个元素，只需要用到临时数组的4到7，tmpPos从left=4开始
在这里插入图片描述
例如合并全部元素，就是从0到7
在这里插入图片描述

package com.xiaoyi.line.algo.sort;

import java.util.Arrays;

public class MergeSorter {
    public void sort(int[] data){
        if(data == null || data.length<2) return;
        //一次性申请一个和原始数组同样大小的临时数组
        int[] tmp = new int[data.length];
        sort(data,0,data.length-1,tmp); //大问题
    }

    //给子数组进行排序，子问题
    private void sort(int[] data,int left,int right,int[] tmp){
        //终止递归条件
        if(left == right) return;

        //分别对两个子问题求解
        int mid = (left + right) / 2;
        sort(data,left,mid,tmp);
        sort(data,mid+1,right,tmp);

        //合并两个有序的数组，即合并[left...mid] 和 [mid+1...right]
        //[left...mid] 和 [mid+1,right]这两个数组在上面已经排好序了
        merge(data,left,mid,right,tmp);
    }

    //合并
    private void merge(int[] data, int left, int mid, int right,int[] tmp) {
        int tmpPos = left;
        //i指针遍历前半部分
        int i = left;
        //j指针遍历后半部分
        int j = mid + 1;
        //将左边和右边的元素按照顺序拷贝到临时数组中
        while (i<=mid && j<=right){
            if(data[i] <= data[j]){
                tmp[tmpPos++] = data[i++];
            }else{  // data[i] > data[j]
                tmp[tmpPos++] = data[j++];
            }
        }
        //如果左边还有元素，则直接将左边的元素拷贝到临时数组
        while (i<=mid){
            tmp[tmpPos++] = data[i++];
        }
        //如果左边还有元素，则直接将右边的元素拷贝到临时数组
        while (j<=right){
            tmp[tmpPos++] = data[j++];
        }

        //拷贝
        for (tmpPos = left; tmpPos < right; tmpPos++) {
            data[left++] = tmp[tmpPos];
        }
    }

    public static void main(String[] args) {
        int[] data = new int[]{12,23,36,9,24,42};
        new MergeSorter().sort(data);
        System.out.println(Arrays.toString(data));
    }
}

归并两个有序的数组区间(写法二)

之前的做法是将两个有序的数组归并到一个临时数组中，然后把临时数组拷贝到原始数组区间里面去
还有一种做法是将原始数组先拷贝到临时数组去，然后再针对临时数据把它们归并到原始数组里面去，和之前的做法相反了，但是效果一样
在这里插入图片描述

public class MergeSorter {
    public void sort(int[] data){
        if(data == null || data.length<2) return;
        //一次性申请一个和原始数组同样大小的临时数组
        int[] tmp = new int[data.length];
        sort(data,0,data.length-1,tmp); //大问题
    }

    //给子数组进行排序，子问题
    private void sort(int[] data,int left,int right,int[] tmp){
        //终止递归条件
        if(left == right) return;

        //分别对两个子问题求解
        int mid = (left + right) / 2;
        sort(data,left,mid,tmp);
        sort(data,mid+1,right,tmp);

        //合并两个有序的数组，即合并[left...mid] 和 [mid+1...right]
        //[left...mid] 和 [mid+1,right]这两个数组在上面已经排好序了
        merge(data,left,mid,right,tmp);
    }

    //合并
    private void merge2(int[] data, int left, int mid, int right,int[] tmp) {
        for (int i = left; i <= right; i++) {
            tmp[i] = data[i];
        }

        int i = left;
        int j = mid + 1;
        for (int k = left; k <= right;k++){
            if(i == mid+1){ //左边没有元素，右边有元素
                data[k] = tmp[j++];
            }else if(j == right+1){ //左边有元素，右边没有元素
                data[k] = tmp[i++];
            }else if(tmp[i] <= tmp[j]){    //两边都有元素，左边元素小于右边元素
                data[k] = tmp[i++];
            }else{
                data[k] = data[j++];    //两边都有元素，左边元素大于右边元素
            }
        }
    }
}

归并排序时间复杂度分析

在这里插入图片描述
O(nlogn)

归并排序的特点

  • 空间复杂度是O(n)，不是原地排序，会申请一个临时数组
  • 归并排序是稳定的排序算法

data[i]<=data[j]会将data[i]左边的元素放入tmp中

自底朝上的归并排序逻辑

之前使用的是自定向下的归并排序
在这里插入图片描述
还有一种是自底朝上的归并排序
在这里插入图片描述
自底朝上归并排序实现

public void sortBU(int[] data){
    if(data == null || data.length<=1)return;
    int len = data.length;
    int[] tmp = new int[len];
    for (int size = 1;size<len;size += size){   // size 表示子数组的长度 1,2,4,8...
        for (int left = 0; left < len - size; left += 2 * size) {
            int mid = left + size -1;
            int right = Math.min(left+2*size-1,len-1);
            merge(data,left,mid,right,tmp);
        }
    }
}

6. 快速排序

快速排序VS归并排序
在这里插入图片描述
快速排序：将数组一分为二，分为两个子数组，然后分别对两个子数组进行独立排序，排完之后整个数组就有序了。
归并排序：将数组从中间一分为二，分别对两个子数组进行排序，就得到了两个有序的子数组，然后对两个有序的子数组进行合并
归并排序有一个合并的过程，快排没有合并的过程
归并排序是简单的从中间一分为二，快排并非如此

快速排序切分数组的逻辑

首先找到一个分区点，这个分区点可以是数组中任意一个元素，可以是第一个也可以是最后一个
假设最后一个元素为分区点(pivot)
然后将数组元素根据分区点进行分区，将大于分区点的元素放到分区点后面，将小于分区点的元素放到分区点前面，这样就可以把数组分为两部分，前面是小于分区点的，后面是大于分区点的
然后再对分区点的左边子数组进行单独排序，对分区点的右边子数组进行排序，这样整个数组就有序了，就没必要再去合并数组了
在这里插入图片描述

快速排序符合递归的三个条件

根据分区点一分为二以后，应该如何给左右两边的子数组进行排序呢？不断递归
不断递归解决子问题的过程
在这里插入图片描述

快排的递归代码实现

在这里插入图片描述

public class QuickSorter {
    public void sort(int[] data){
        if(data == null || data.length<=1) return;
        sort(data,0,data.length-1);
    }

    //子问题
    private void sort(int[] data,int lo,int hi){
        if(lo>=hi) return;
        //分区
        int j = partition(data,lo,hi);
        //对左边数组排序
        sort(data,lo,j-1);
        //对右边数组排序
        sort(data,j+1,hi);
    }

    private int partition(int[] data, int lo, int hi) {
        //TODO
        return 0;
    }
}

深入理解快排过程

每次都假设最后一个元素作为分区点，进行分区
在这里插入图片描述

分区的逻辑过程

两个指针lo 和 hi ，选择最后一个元素作为分区点(pivot)20
定义两个指针less 和 great ，都是从lo开始，less指向小于分区点的元素的后一个位置，great指向大于20的最后一个元素
首先判断great指针如果指向的数值比pivot小的话，将less和great进行交换，比pivot大就向前移动

分区逻辑代码实现

public class QuickSorter extends Sorter {
    public void sort(int[] data){
        if(data == null || data.length<=1) return;
        sort(data,0,data.length-1);
    }

    //子问题
    private void sort(int[] data,int lo,int hi){
        if(lo>=hi) return;
        //分区
        int j = partition(data,lo,hi);
        //对左边数组排序
        sort(data,lo,j-1);
        //对右边数组排序
        sort(data,j+1,hi);
    }

    //分区过程
    private int partition(int[] data, int lo, int hi) {
        int pivot = data[hi];    //将最后一个元素作为分区点
        int less = lo;
        int great = lo;    
        for (; great <= hi-1 ; great++) {    //遍历整个数组
            if(data[great] < pivot){    //如果小于分区点，将元素交换
                swap(data,less,great);
                less++;
            }
        }
        //great 遍历到 hi -1，将less和 hi 也就是分区点进行交换
        swap(data,less,hi);
        return less;
    }

    public static void main(String[] args) {
        int[] data = new int[]{12,23,36,9,24,42};
        new QuickSorter().sort(data);
        System.out.println(Arrays.toString(data));
    }
}

快速排序的特点

  • 时间复杂度：O(nlogn)
  • 空间复杂度O(logn)，原地排序算法

在这里插入图片描述

  • 不稳定的排序算法
    在这里插入图片描述

结论：并不是原地排序算法的空间复杂度就是O(1)
空间复杂度是O(1)的排序算法，肯定是原地排序算法

快速排序的优化

在极端情况下，数组已经有序，并且选择了最后一个元素作为分区点，这个时候时间复杂度会退化成O(n2)
在给已经有序的数组进行排序的情况下，假设最后一个元素为分区点，这个时候第一遍分区，要比较n-1个元素，分区完后，小于20的都在左边，接下来遍历前一个，又需要进行n-2次比较；
每次分区得到的区间是不均等的，每次分区后所有的元素都在分区点的左边
在这里插入图片描述
导致退化成O(n2)的主要原因还是分区点选择的不合理
要保证分区点左右两侧数据量差不多
性能优化：

  1. 三数取中法
    取第一个元素，中间元素，最后一个元素的中间值作为分区点
  2. 随机法，随机选择一个元素，不能保证每次选择的分区点很好

三路快排的逻辑

有很多重复元素的数组
在这里插入图片描述

左侧还会去分区，已经有序了，再去分区就是浪费资源了

引入三路快排
在这里插入图片描述

i到great之间就是正在处理的元素空间处理后会分为三个部分，重复的元素都会放到pivot；只需要对小于pivot和大于pivot的元素进行分区就可以了

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

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

相关文章

跨平台看抖音、哔哩哔哩、虎牙、斗鱼啦，一个app即可完成

跨平台看抖音、哔哩哔哩、虎牙、斗鱼啦，一个app即可完成

一、简介 1、一款免费、开源、无广告、跨平台的，可以观看抖音、哔哩哔哩、虎牙、斗鱼等平台的直播内容的软件。它简单好用，支持 Windows、MacOS、Linux、Android、iOS 等平台。 二、下载 1、文末有下载链接，apk手机可直接安装，不明白可以私聊我哈（麻烦咚咚咚，动动小手给个…
阅读更多...
详解QFileSystemModel的使用

详解QFileSystemModel的使用

在Qt应用程序开发中&#xff0c;QFileSystemModel是一个强大的类&#xff0c;用于展示和操作文件系统的信息。它基于标准的QAbstractItemModel&#xff0c;提供了浏览本地文件系统目录树的能力&#xff0c;并且能够自动更新以反映文件系统的变化。本文将详细讲解QFileSystemMod…
阅读更多...
MongoDB——写入耗时

MongoDB——写入耗时

mongodb写入10万条数据的耗时差不多是1s import time import pymongo from pymongo import MongoClient# 连接到MongoDB client MongoClient(mongodb://localhost:27017/) db client[test_db] collection db[test_collection]# 生成10万条数据 documents [{"name&quo…
阅读更多...
ThinkPHP内核在线客服系统源码多商户版 对接适用场景(PC+WAP+公众号)

ThinkPHP内核在线客服系统源码多商户版 对接适用场景(PC+WAP+公众号)

源码介绍 大部分站长都了解美洽系统&#xff0c;就跟这种类似的&#xff0c;可以实现一行代码接入客服&#xff0c;非常舒服&#xff0c;支持无限客服&#xff0c;无限坐席! 私有化源码部署&#xff0c;数据可控&#xff0c;稳定可靠。可自定义版权、logo。支持网页、微信公众…
阅读更多...
CPN tools学习——可执行的 PN

CPN tools学习——可执行的 PN

目录 1添加令牌 2.转换防护Guard 1添加令牌 左侧新建颜色集和变量的声明定义&#xff1a; 为库所分配颜色集&#xff1a;左键tab键 P1处&#xff1a;添加多重集合&#xff0c;表示添加了两个令牌&#xff0c;第一个令牌值为A&#xff0c;第二个为B。 P2处&#xff1a;表示…
阅读更多...
docker的教程长亭

docker的教程长亭

把我的常用docker写在这里 之前用 vul - hub 靶场经常用 现在docker不知道为什么挂了 开启 docker-compose up -d 关闭 docker-compose down docker ps 只是运行 docker ps -a 所有 包括停止 docker ps -q 只看id docker stop <container_name_or_id> docker 的容器…
阅读更多...
辣椒属2个T2T基因组-文献精读23

辣椒属2个T2T基因组-文献精读23

Two telomere-to-telomere gapless genomes reveal insights into Capsicum evolution and capsaicinoid biosynthesis 两个端粒到端粒无缝基因组揭示了辣椒进化和辣椒素生物合成的相关见解 摘要 辣椒&#xff08;Capsicum&#xff09;因其果实中含有辣椒素而闻名&#xff0c…
阅读更多...
zabbix自定义监控mysql状态和延迟

zabbix自定义监控mysql状态和延迟

zabbix自定义监控mysql状态和延迟 文章目录 zabbix自定义监控mysql状态和延迟zabbix自定义监控mysql状态配置主从配置自定义监控添加监控项添加触发器模拟测试异常 zabbix自定义监控mysql延迟配置自定义监控添加监控项添加触发器测试 zabbix自定义监控mysql状态 配置主从 1.安…
阅读更多...
【区间合并 差分 栈】3169. 无需开会的工作日

【区间合并 差分 栈】3169. 无需开会的工作日

本文涉及知识点 区间合并 差分数组&#xff08;大约2024年7月1号发) LeetCode3169. 无需开会的工作日 给你一个正整数 days&#xff0c;表示员工可工作的总天数&#xff08;从第 1 天开始&#xff09;。另给你一个二维数组 meetings&#xff0c;长度为 n&#xff0c;其中 me…
阅读更多...
蓝牙模块的安全性与隐私保护

蓝牙模块的安全性与隐私保护

蓝牙模块作为现代无线通信的重要组成部分&#xff0c;在智能家居、可穿戴设备、健康监测等多个领域得到了广泛应用。然而&#xff0c;随着蓝牙技术的普及&#xff0c;其安全性和隐私保护问题也日益凸显。本文将探讨蓝牙模块在数据传输过程中的安全性问题&#xff0c;分析隐私保…
阅读更多...
Web应用安全测试-业务功能滥用（二）

Web应用安全测试-业务功能滥用（二）

Web应用安全测试-业务功能滥用&#xff08;二&#xff09; 7、未验证的URL跳转 漏洞描述&#xff1a;服务端未对传入的跳转url变量进行检查和控制&#xff0c;可能导致可恶意构造任意一个恶意地址&#xff0c;诱导用户跳转到恶意网站。由于是从可信的站点跳转出去的&#xff…
阅读更多...
如何扩展自己的外部竞争力

如何扩展自己的外部竞争力

前言 程序员是一个需要不断学习的职业&#xff0c;面对层出不穷的新技术&#xff0c;假如你不能够保持一个不断学习的热情。那么&#xff0c;在未来的就业市场中&#xff0c;可能优势会不太明显。那么&#xff0c;除了提高自己内部的技术竞争力外&#xff0c;有什么渠道可以提…
阅读更多...
Linux下的GPIO编程

Linux下的GPIO编程

目录 一、前言 二、sysfs方式 1、sysfs简介 2、基本目录结构 3、编号计算 4、sysfs方式控制GPIO 三、libgpiod库 1、libgpiod库简介 2、API函数 四、LED灯编程 一、前言 在Linux下&#xff0c;我们通常使用 sysfs 和 libgpiod库 两种方式进行控制GPIO&#xff0c;目前…
阅读更多...
哈喽GPT-4o——对GPT-4o Prompt的思考与看法

哈喽GPT-4o——对GPT-4o Prompt的思考与看法

目录 一、提示词二、提示词的优势1、提升理解能力2、增强专注力3、提高效率 三、什么样的算无效提示词&#xff1f;1、过于宽泛2、含糊不清3、太过复杂4、没有具体上下文5、缺乏明确目标6、过于开放7、使用专业术语但未定义8、缺乏相关性&#xff1a; 四、提示词正确的编写步骤…
阅读更多...
ofd文件预览

ofd文件预览

文件列表 <template><div><div classfile v-if$myUtils.coll.isNotEmpty(filesList)><div classfile-view><div classfile-view-item :style{justifyContent: align } v-for(item, index) in filesList :keyindex><img classfile-view-item-…
阅读更多...
纵深发力 持续推进，富格林平台发展势头喜人

纵深发力 持续推进，富格林平台发展势头喜人

自2024年2月1日正式上线以来,富格林互联网投融资平台已迅速崛起,吸引了业内专家学者的高度认可以及广大投资者的青睐。平台规模持续扩大,目前累计注册用户已超过10万人,总投资额突破50亿美元。这一卓越表现不仅体现了平台的稳健运营和出色的投资项目,也展示了其在互联网投融资领…
阅读更多...
产品应用 | 小盒子跑大模型！英码科技基于算能BM1684X平台实现大模型私有化部署

产品应用 | 小盒子跑大模型！英码科技基于算能BM1684X平台实现大模型私有化部署

当前&#xff0c;在人工智能领域&#xff0c;大模型在丰富人工智能应用场景中扮演着重要的角色&#xff0c;经过不断的探索&#xff0c;大模型进入到落地的阶段。而大模型在落地过程中面临两大关键难题&#xff1a;对庞大计算资源的需求和对数据隐私与安全的考量。为应对这些挑…
阅读更多...
typora+Picgo使用Lsky pro搭建本地服务图床

typora+Picgo使用Lsky pro搭建本地服务图床

typoraPicgo使用Lsky pro搭建本地服务图床 Picgo下载lankong插件lankong插件安装Auth token获取 Picgo测试typora测试问题说明 Picgo下载 Picgo下载&#xff1a;https://github.com/Molunerfinn/PicGo/releases&#xff0c;注意&#xff1a;请直接使用尝鲜版&#xff0c;正式版…
阅读更多...
一文让你清晰了解医疗行业采购堡垒机的必要性

一文让你清晰了解医疗行业采购堡垒机的必要性

医疗行业&#xff0c;一个与大家息息相关的行业。随着医疗行业的快速发展和信息化建设的深入推进&#xff0c;传统网络安全防护手段已经难以满足现代医疗信息系统的安全需求&#xff0c;特别是在处理敏感的患者信息和保障医院内部数据安全方面。因此采购堡垒机是非常必要的。 堡…
阅读更多...
python310: pip install Could not install packages (HTTPSConnectionPool)问题

python310: pip install Could not install packages (HTTPSConnectionPool)问题

一、问题描述 在使用pip install安装包或者升级pip版本&#xff08;pip install --upgrade pip&#xff09;时遇到以下错误&#xff1a; WARNING: Retrying (Retry(total4, connectNone, readNone, redirectNone, statusNone)) after connection broken by ReadTimeoutError(…
阅读更多...
最新文章

Copyright @ 2022~2023