归并排序和快速排序

目录

归并排序

思路:

 代码执行:

快速排序

运行流程图:

代码思路:

代码执行:


归并排序

        定义:归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

思路:

1)首先将给定的数组{51, 46, 20, 18, 95, 67, 82, 30}一分为二,直到每个数组的长度等于1

        {51, 46, 20, 18} {95, 67, 82, 30}

        {51, 46} {20, 18} {95, 67} {82, 30}

        {51} {46}   {20} {18}   {95} {67}   {82} {30}

2)两两比较进行交换{46, 51}   {18, 20}   {67, 95}   {30, 82}

3)最后进行合并得到排序后的数组{18, 20, 30, 46, 51, 67, 82, 95}
 

整体的递归思路就是:

 

 代码执行:

import java.util.Arrays;

public class MergeSort {
    public static int sum = 0;
    public static void main(String[] args) {
        int[] a = {51, 46, 20, 18, 95, 67, 82, 30};
        mergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    public static void mergeSort(int[] a, int left, int right) {
        //二分
        int mid = (left + right) / 2;
        //拆分过程就是递归,需要不断进行递归,减小子数组的规模,最终减小到每个数组的规模为1或者为0
        if (left < right) {
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }

    public static void merge(int[] a, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];//临时数组,用来进行归并
        int i = left, j = mid + 1, k = 0;//左半段用i指向,右半段用j指向,temp中用k指向
        while (i <= mid && j <= right) {
            if (a[i] < a[j]) {
                //如果左边的a[i]小于右边的a[j],就放到数组的第k个,k和i自增
                temp[k++] = a[i++];
            } else {
                //否则,就把右边的第j个放到数组的第k个,k和j自增
                temp[k++] = a[j++];
            }
        }
        while (i <= mid) temp[k++] = a[i++];//如果左边在循环比较后还有剩余,就放到k中、
        while (j <= right) temp[k++] = a[j++];//如果剩余直接放到k中
        for (int l = 0; l < temp.length; l++) {
            //让temp数组放到左半段和右半段有序的数据
            a[left + l] = temp[l];
        }
    }
}

快速排序

运行流程:

1)首先设定一个分界值,通过该分界值将数组分成左右两部分。

2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。

3)左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

运行流程图:

代码思路:

1)首先确定left、rigeht和基准点temp

2)当i(left) 和 j(right)相等的时候就结束循环

3)在循环中再次循环找出a[j]小于temp的时候把a[j]赋给a[i++],以及找出a[i]大于temp的时候把a[i]赋给a[j--]

4)不断递归进行排序

代码执行:

import java.util.Arrays;

public class quickSortDemo {
    public static void main(String[] args) {
        int[] a = {49, 38, 65, 97, 76, 13, 27, 49};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    public static void quickSort(int[] a, int left, int right) {
        if (left > right) return;//区间无效不需要递归
        int i = left, j = right, temp = a[left];//temp为基准点
        while (i != j) {
            while (a[j] >= temp && j > i) j--;//一直循环找a[j]小于temp的时候
            if (j > i) a[i++] = a[j];//将a[j]赋给a[i++]
            while (a[i] <= temp && i < j) i++;//循环找a[i]大于temp的时候
            if (i < j) a[j--] = a[i];//将a[i]赋给a[j--]
        }
        a[i] = temp;//将基准点的元素放到a[i]处
        quickSort(a, left, i - 1);//已经确定i为基准点所以right就位i - 1
        quickSort(a, i + 1, right);//已经确定i为基准点所以left就位i + 1
    }
}

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

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

相关文章

【JavaSE】类和对象(中)

类和对象&#xff08;中&#xff09;4. this引用4.1 为什么要有this引用4.2 什么是this引用4.3 this引用的特性5. 对象的构造及初始化5.1 如何初始化对象5.2 构造方法&#xff08;构造器&#xff09;5.2.1 概念5.2.2 特性5.3 默认初始化5.4 就地初始化6. 封装6.1 封装的概念6.2…

常用hook

Hook 是 React 16.8 的新增特性。它可以让你在不编写 class 的情况下使用 state 以及其他的 React 特性。理解&#xff1a;hook是react提供的函数API官方提供的hook基础hookuseState APIconst [state, setState] useState(initialState); //返回state值 以及更新state的方法 …

壹沓科技完成近2亿元B轮融资:构建数字机器人,实现业务超自动化

RPA中国获悉&#xff0c;全球领先的数字机器人公司壹沓科技近期宣布完成近2亿元B轮融资&#xff0c;本轮融资由鼎晖VGC(创新与成长基金)领投&#xff0c;创享欢聚投资基金、IDG资本、钟鼎资本跟投&#xff0c;指数资本继续担任独家财务顾问。 壹沓科技CEO卞晓瑜表示&#xff1…

栈、队列、优先级队列的模拟实现

优先级队列的模拟实现栈stack的模拟实现push()pop()top()size()empty()swap()stack总代码队列queue的模拟实现push()pop()front()back()empty()size()swap()queue总代码优先级队列(堆)push()pop()top()empty()size()swap()priority_queue总代码deque的了解栈 在CSTL中栈并不属…

吃透Java面试题,建议收藏

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址&#xff1a;https://github.com/…

LeetCode:27. 移除元素

&#x1f34e;道阻且长&#xff0c;行则将至。&#x1f353; &#x1f33b;算法&#xff0c;不如说它是一种思考方式&#x1f340;算法专栏&#xff1a; &#x1f449;&#x1f3fb;123 一、&#x1f331;27. 移除元素 题目描述&#xff1a;给你一个数组 nums 和一个值 val&am…

Chapter6.2:其他根轨迹及综合实例分析

该系列博客主要讲述Matlab软件在自动控制方面的应用&#xff0c;如无自动控制理论基础&#xff0c;请先学习自动控制系列博文&#xff0c;该系列博客不再详细讲解自动控制理论知识。 自动控制理论基础相关链接&#xff1a;https://blog.csdn.net/qq_39032096/category_10287468…

使用vite创建vue3工程

定义 什么是vite&#xff1f;-----新一代前端构建工具 优势 开发环境中&#xff0c;无需打包操作&#xff0c;可快速的冷启动---最牛的地方轻量快速的热重载&#xff08;HMR&#xff09;---一修改代码就局部刷新&#xff0c;webpack也具备&#xff0c;但vite更快真正的按需编…

【数据结构与算法】用队列实现栈

文章目录&#x1f60e;前言如何用队列实现栈&#xff1f;用队列实现栈整体的实现代码&#x1f60e;写在最后&#x1f60e;前言 &#x1f63c;前面我们相继实现了 栈 和 队列 &#xff0c;是不是愁没有练手的地方呢&#xff1f;别担心&#xff0c;本章带大家用队列来实现一个栈&…

synchronized 加锁 this 和 class 的区别

synchronized 是 Java 语言中处理并发问题的一种常用手段&#xff0c;它也被我们亲切的称之为“Java 内置锁”&#xff0c;由此可见其地位之高。然而 synchronized 却有着多种用法&#xff0c;当它修饰不同对象时&#xff0c;其意义也是不同的&#xff0c;下面我们一起来看。 ​…

云原生时代顶流消息中间件Apache Pulsar部署实操之Pulsar IO与Pulsar SQL

文章目录Pulsar IO (Connector连接器)基础定义安装Pulsar和内置连接器连接Pulsar到Cassandra安装cassandra集群配置Cassandra接收器创建Cassandra Sink验证Cassandra Sink结果删除Cassandra Sink连接Pulsar到PostgreSQL安装PostgreSQL集群配置JDBC接收器创建JDBC Sink验证JDBC …

【网络】网络层协议——IP

目录网络层IP协议IP基础知识IP地址IP报头格式网段划分CIDR特殊的IP地址IP地址的数量限制私有IP地址和公有IP地址路由IP总结网络层 在复杂的网络环境中确定一个合法的路径。 IP协议 IP协议作为整个TCP/IP中至关重要的协议&#xff0c;主要负责将数据包发送给最终的目标计算机…

多线程 (六) 单例模式

&#x1f389;&#x1f389;&#x1f389;点进来你就是我的人了 博主主页&#xff1a;&#x1f648;&#x1f648;&#x1f648;戳一戳,欢迎大佬指点!人生格言&#xff1a;当你的才华撑不起你的野心的时候,你就应该静下心来学习! 欢迎志同道合的朋友一起加油喔&#x1f9be;&am…

蓝桥杯刷题冲刺 | 倒计时19天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.抓住那头牛2.排列序数1.抓住那头牛 题目 链接&#xff1a; 抓住那头牛 - C语言网 (dotcpp.com…

网络安全之防火墙

目录 网络安全之防火墙 路由交换终归结底是联通新设备 防御对象&#xff1a; 定义&#xff1a; 防火墙的区域划分&#xff1a; 包过滤防火墙 --- 访问控制列表技术 --- 三层技术 代理防火墙 --- 中间人技术 --- 应用层 状态防火墙 --- 会话追踪技术 --- 三层、四层 UTM …

CrossOver零知识学习1 —— 初识

本文部分内容参考CrossOver22全新版功能简介 免费mac虚拟机工具_CoCo玛奇朵的博客-CSDN博客 特此致谢&#xff01; 一、CrossOver简介 CrossOver是由CODE WEAVERS公司开发的类虚拟机软件&#xff0c;目的是使Linux和Mac OS X操作系统和Window系统兼容。CrossOver英文原意为“…

强烈推荐:0基础入门网安必备《网络安全知识图谱》

蚁景网安学院一直专注于网安实战技能培养&#xff0c;提供全方位的网安安全学习解决方案。我们集聚专业网安技术大佬资源&#xff0c;倾力打造了这本更全面更系统的“网络安全知识图谱”&#xff0c;让大家在网络安全学习路上不迷茫。 在这份网安技能地图册里&#xff0c;我们对…

01 | Msyql系统架构

目录MySQL系统架构连接器查询缓存分析器优化器执行器MySQL系统架构 大体来说&#xff0c;MySQL分为Server层和引擎层两部分。 Server层包含链接器、查询缓存、分析器、优化器和执行器&#xff0c;而引擎层负责的是数据的存储和读取&#xff0c;支持InnoDB、Myisam、Memory等多…

CSS实现文字凹凸效果

使用两个div分别用来实现凹凸效果&#xff1b;text-shadow语法 text-shadow: h-shadow v-shadow blur color; h-shadow&#xff1a;必需。水平阴影的位置。允许负值。 v-shadow &#xff1a;必需。垂直阴影的位置。允许负值。 blur&#xff1a;可选&#xff0c;模糊的距离。 co…

【C语言】你真的了解结构体吗

引言✨我们知道C语言中存在着整形(int、short...)&#xff0c;字符型(char)&#xff0c;浮点型(float、double)等等内置类型&#xff0c;但是有时候&#xff0c;这些内置类型并不能解决我们的需求&#xff0c;因为我们无法用这些单一的内置类型来描述一些复杂的对象&#xff0c…