归并排序(java)

大家好我是苏麟 , 今天说说归并排序 . 

归并排序

递归

正式学习归并排序之前,我们得先学习一下递归算法。

定义:

定义方法时,在方法内部调用方法本身,称之为递归.

public void show(){System.out.println("aaaa");show();
}

作用:

它通常把一个大型复杂的问题,层层转换为一个与原问题相似的,规模较小的问题来求解。递归策略只需要少量的 程序就可以描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

注意事项:

在递归中,不能无限制的调用自己,必须要有边界条件,能够让递归结束,因为每一次递归调用都会在栈内存开辟 新的空间,重新执行方法,如果递归的层级太深,很容易造成栈内存溢出。

需求:

请定义一个方法,使用递归完成求N的阶乘

分析:
1!: 1
2!: 2*1=2*1!
3!: 3*2*1=3*2!
4!: 4*3*2*1=4*3!
...
n!: n*(n-1)*(n-2)...*2*1=n*(n-1)!
所以,假设有一个方法factorial(n)用来求n的阶乘,那么n的阶乘还可以表示为n*factorial(n-1)

代码实现:

public class Test {public static void main(String[] args) throws Exception {int result = factorial(5);System.out.println(result);}public static int factorial(int n){if (n==1){return 1;}return n*factorial(n-1);}
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子 序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序 表,称为二路归并。

需求:

排序前:{8,4,5,7,1,3,6,2} 排序后:{1,2,3,4,5,6,7,8}

排序原理:

1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是 1为止。

2.将相邻的两个子组进行合并成一个有序的大组;

3.不断的重复步骤2,直到最终只有一个组为止。

代码 :

package src.sl.sort;/*** 归并排序* 数据类型 : int*/
public class MergeSort {//辅助数组public static int[] assist;public static void main(String[] args) {int[] arr = new int[]{2,5,6,1,3,2,4,8,6,7,5};sort(arr);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}/*** 对数组全部排序** @param arr*/public static void sort(int[] arr) {assist = new int[arr.length];int left = 0;int right = arr.length-1;sort(arr, left, right);}/*** 对数组部分排序** @param arr* @param left* @param right*/public static void sort(int[] arr, int left, int right) {if (left >= right) {return;}int mid = left +  (right-left) / 2;sort(arr, left, mid);sort(arr,mid + 1,right);//归并merge(arr, left, mid, right);}/*** 归并** @param arr* @param left* @param mid* @param right*/public static void merge(int[] arr, int left, int mid, int right) {int i = left;int p1 = left;int p2 = mid + 1;while (p1 <= mid && p2 <= right){if (arr[p1] < arr[p2]){assist[i++] = arr[p1++];}else {assist[i++] = arr[p2++];}}while (p1 <= mid){assist[i++] = arr[p1++];}while (p2 <= right){assist[i++] = arr[p2++];}for (int j = left; j<=right;j++){arr[j] = assist[j];}}
}

这期就到这里 , 下期见!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

软考高级系统架构师冲关预测

[ – 2023年10月27日 – ] 去年11月通过了软考高级系统架构师的考试&#xff0c;原本想立即分享下过关的总结回顾&#xff0c;但是随着软考新版大纲及教程的发布&#xff0c;也意味着题目及内容的复盘总结经验便不那么适用。在即将迎来今年的软考高架的时候&#xff0c;想着透…

Azure - 机器学习企业级服务概述与介绍

目录 一、什么是 Azure 机器学习&#xff1f;大规模生成业务关键型机器学习模型 二、Azure 机器学习适合哪些人群&#xff1f;三、Azure 机器学习的价值点加快价值实现速度协作并简化 MLOps信心十足地开发负责任地设计 四、端到端机器学习生命周期的支持准备数据生成和训练模型…

k8s statefulSet 学习笔记

文章目录 缩写: stsweb-sts.yaml创建sts扩缩容金丝雀发布OnDelete 删除时更新 缩写: sts 通过 kubectl api-resources 可以查到&#xff1a; NAMESHORTNAMESAPIVERSIONNAMESPACEDKINDstatefulsetsstsapps/v1trueStatefulSet web-sts.yaml apiVersion: v1 kind: Service met…

LabVIEW开发TDS1000 和TDS2000 系列泰克示波器

LabVIEW开发TDS1000 和TDS2000 系列泰克示波器 泰克示波器是经常用到的工具&#xff0c;一般手动操作即可&#xff0c;但有时候也要集成到系统中&#xff0c;需要程控。这时候先要下载厂家提供的例子&#xff0c;了解LabVIEW的demo。根据不用的示波器型号&#xff0c;选择和计…

【SpringCloudNetflix】一图理解Spring Cloud Netflix解决了那些微服务问题?

什么是微服务理解&#xff1a; SpringCloudNetflix解决的问题理解&#xff1a; SpringCloudNetflix核心点&#xff1a; 注册中心&#xff1a;Eureka负载均衡&#xff1a;Ribbon、Feign服务熔断&#xff1a;Hystrix服务降级&#xff1a;Hystrix服务监控&#xff1a;Hystrix Da…

CSS 滚动驱动动画与 @keyframes 新语法

CSS 滚动驱动动画与 keyframes 在 CSS 滚动驱动动画相关的属性出来之后, keyframes 也迎来变化. 以前, keyframes 的值可以是 from, to, 或者百分数. 现在它多了一种属性的值 <timeline-range-name> <percentage> 建议先了解 animation-range 不然你会对 timeli…

高三高考免费试卷真题押题知识点合集

发表于安徽 温馨提示&#xff1a;有需要的真题试卷可联系本人&#xff0c;百卷内上免费资源。 感觉有用的下方三连&#xff0c;谢谢 ​ 。 免费版卷有6-60卷每卷平均4-30页 高三免费高三地理高三英语高三化学高三物理高三语文高三历史高三政治高三数学高三生物 付费版卷有1…

Linux shell编程学习笔记15:定义数组、获取数组元素值和长度

一、 Linux shell 脚本编程中的数组概述 数组是一种常见的数据结构。跟大多数编程语言一样&#xff0c;大多数Linux shell脚本支持数组&#xff0c;但对数组的支持程度各不相同&#xff0c;比如数组的维度&#xff0c;是支持一维数组还是多维数组&#xff1f;再如&#xff0c;…

[Docker]三.Docker 部署nginx,以及映射端口,挂载数据卷

一.Docker 部署 Nginx 以及端口映射 Docker 部署 Nginx,首先需要下载nginx镜像,然后启动这个镜像,就运行了一个nginx的容器了 1.下载 nginx 镜像并启动容器 #查看是否存在nginx镜像:发现没有nginx镜像 [rootlocalhost zph]# docker images | grep nginx#下载nginx镜像 [rootl…

IO流框架,缓冲流

一.缓冲流有什么优点 Java中的缓冲流&#xff08;Buffered Stream&#xff09;具有以下优势&#xff1a; 提高效率&#xff1a;缓冲流通过在内存中缓存一部分数据&#xff0c;减少了直接从内存到磁盘或从磁盘到内存的频繁IO操作&#xff0c;从而提高了读写效率。缓冲区大小调整…

Java8与JDK1.8与JDK8之间的关系是什么?

1.Java8等价于JDK8 2.JDK8或者JDK1.8是由于自从JDK1.5/JDK5命名方式改变后遗留的历史问题。所以JDK8或者JDK1.8是等价的。 2004年9月30日&#xff0c;J2SE1.5发布。为了表示该版本的重要性&#xff0c;J2SE 1.5更名为Java SE 5.0&#xff0c;从此开始&#xff0c;如下图像jav…

C++之#pragma once实例总结(二百四十七)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…

OpenCV官方教程中文版 —— 直方图的计算,绘制与分析

OpenCV官方教程中文版 —— 直方图的计算&#xff0c;绘制与分析 前言一、原理1.统计直方图2. 绘制直方图3. 使用掩模 前言 • 使用 OpenCV 或 Numpy 函数计算直方图 • 使用 Opencv 或者 Matplotlib 函数绘制直方图 • 将要学习的函数有&#xff1a;cv2.calcHist()&#xf…

二叉树:有了如此高效的散列表,为什么还需要二叉树?

文章来源于极客时间前google工程师−王争专栏。 上一节我们学习了树、二叉树以及二叉树的遍历&#xff0c;今天我们再来学习一种特殊的的二叉树&#xff0c;二叉查找树。二叉查找树最大的特点就是&#xff0c;支持动态数据集合的快速插入、删除、查找操作。 我们之前说过&…

StripedFly恶意软件框架感染了100万台Windows和Linux主机

导语 近日&#xff0c;一款名为StripedFly的恶意软件框架在网络安全研究人员的监视之外悄然感染了超过100万台Windows和Linux系统。这款跨平台的恶意软件平台在过去的五年中一直未被察觉。在去年&#xff0c;卡巴斯基实验室发现了这个恶意框架的真实本质&#xff0c;并发现其活…

设计高信度和效度的问卷:关键要点与技巧

设计调查问卷是任何研究过程中至关重要的一部分&#xff0c;无论是出于学术目的还是商业目的。调查是用于收集数据的常用工具&#xff0c;它们可以为消费者行为、意见、客户满意度和其他重要因素提供有价值的见解。然而&#xff0c;调查的可靠性和有效性对于确保收集的数据准确…

WireShark使用入门

背景 Wireshark&#xff0c;又被称为网络封包分析软件&#xff0c;是一种开源且功能十分强大的工具。该工具的主要功能是截取各种网络封包&#xff0c;并尽可能显示出最为详细的网络封包资料。它使用WinPCAP作为接口&#xff0c;直接与网卡进行数据报文交换。 Wireshark支持W…

SpringCloudAlibaba实战-nacos集群部署

写在前面&#xff1a;在学习阶段&#xff0c;我们想快速学习SpringCloudAlibaba功能&#xff0c;但总是花费大量时间跟着视频或博客做组件配置。由于版本的更迭&#xff0c;我们学习时的组件版本很可能和作者的不一致&#xff0c;又或者是各自环境不一&#xff0c;只能一坑又一…

【Python爬虫三天从0到1】Day1:爬虫核心

目录 1.HTTP协议与WEB开发 &#xff08;1&#xff09;简介 &#xff08;2&#xff09;请求协议和响应协议 2. requests&反爬破解 &#xff08;1&#xff09;UA反爬 &#xff08;2&#xff09;referer反爬 &#xff08;3&#xff09;cookie反爬 3.请求参数 &#x…