【JavaSE】Java基础语法(二十三):递归与数组的高级操作

这篇具有很好参考价值的文章主要介绍了【JavaSE】Java基础语法(二十三):递归与数组的高级操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。




【JavaSE】Java基础语法(二十三):递归与数组的高级操作

1. 递归

1.1 递归

  • 递归的介绍
    • 以编程的角度来看,递归指的是方法定义中调用方法本身的现象
    • 把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
    • 递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算
  • 递归的基本使用
public class MyFactorialDemo2 {
	public static void main(String[] args) {
		int sum = getSum(100);
		System.out.println(sum);
	}
	
	private static int getSum(int i) {
		//1- 100之间的和
		//100 + (1-99之间的和)
		// 99 + (1- 98之间的和)
		//....
		//1
		//方法的作用: 求 1- i 之间和
		if(i == 1){
			return 1;
		}else{
			return i + getSum(i -1);
		}
	}
}
  • 递归的注意事项
    • 递归一定要有出口。否则内存溢出
    • 递归虽然有出口,但是递归的次数也不宜过多。否则内存溢出

1.2 递归求阶乘

  • 案例需求
    • 用递归求5的阶乘,并把结果在控制台输出
  • 代码实现
public class DiGuiDemo01 {
	public static void main(String[] args) {
		//调用方法
		int result = jc(5);
		//输出结果
		System.out.println("5的阶乘是:" + result);
	}
	
	//定义一个方法,用于递归求阶乘,参数为一个int类型的变量
	public static int jc(int n) {
		//在方法内部判断该变量的值是否是1
		if(n == 1) {
			//是:返回1
			return 1;
		} else {
			//不是:返回n*(n-1)!
			return n*jc(n-1);
		}
	}
}

2. 数组的高级操作

2.1 二分查找

  • 二分查找概述
    查找指定元素在数组中的位置时,以前的方式是通过遍历,逐个获取每个元素,看是否是要查找的元素,
    这种方式当数组元素较多时,查找的效率很低
    二分查找也叫折半查找,每次可以去掉一半的查找范围,从而提高查找的效率

  • 需求
    在数组{1,2,3,4,5,6,7,8,9,10}中,查找某个元素的位置


  • 实现步骤
  1. 定义两个变量,表示要查找的范围。默认min = 0 ,max = 最大索引
  2. 循环查找,但是min <= max
  3. 计算出mid的值
  4. 判断mid位置的元素是否为要查找的元素,如果是直接返回对应索引
  5. 如果要查找的值在mid的左半边,那么min值不变,max = mid -1.继续下次循环查找
  6. 如果要查找的值在mid的右半边,那么max值不变,min = mid + 1.继续下次循环查找
  7. 当min > max 时,表示要查找的元素在数组中不存在,返回-1.
  • 代码实现
public class MyBinarySearchDemo {
	public static void main(String[] args) {
		int [] arr = {1,2,3,4,5,6,7,8,9,10};
		int number = 11;
		//1,我现在要干嘛? --- 二分查找
		//2.我干这件事情需要什么? --- 数组 元素
		//3,我干完了,要不要把结果返回调用者 --- 把索引返回给调用者
		int index = binarySearchForIndex(arr,number);
		System.out.println(index);
	}
	
	private static int binarySearchForIndex(int[] arr, int number) {
		//1,定义查找的范围
		int min = 0;
		int max = arr.length - 1;
		//2.循环查找 min <= max
		while(min <= max){
			//3.计算出中间位置 mid
			int mid = (min + max) >> 1;
			//mid指向的元素 > number
			if(arr[mid] > number){
				//表示要查找的元素在左边.
				max = mid -1;
			}else if(arr[mid] < number){
				//mid指向的元素 < number
				//表示要查找的元素在右边.
				min = mid + 1;
			}else{
				//mid指向的元素 == number
				return mid;
			}
		}
		//如果min大于了max就表示元素不存在,返回-1.
		return -1;
	}
}

注意事项
有一个前提条件,数组内的元素一定要按照大小顺序排列,如果没有大小顺序,是不能使用二分查
找法的


2.2 冒泡排序

  • 冒泡排序概述
    一种排序的方式,对要进行排序的数据中相邻的数据进行两两比较,将较大的数据放在后面,依次对所有的数据进行操作,直至所有数据按要求完成排序
    如果有n个数据进行排序,总共需要比较n-1次 每一次比较完毕,下一次的比较就会少一个数据参与

  • 代码实现

public class MyBubbleSortDemo2 {
	public static void main(String[] args) {
		int[] arr = {3, 5, 2, 1, 4};
		//1 2 3 4 5
		bubbleSort(arr);
	}
	
	private static void bubbleSort(int[] arr) {
		//外层循环控制的是次数 比数组的长度少一次.
		for (int i = 0; i < arr.length -1; i++) {
			//内存循环就是实际循环比较的
			//-1 是为了让数组不要越界
			//-i 每一轮结束之后,我们就会少比一个数字.
			for (int j = 0; j < arr.length - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
			printArr(arr);
		}
		
		private static void printArr(int[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
		}
}

2.3 快速排序

  • 快速排序概述
    冒泡排序算法中,一次循环结束,就相当于确定了当前的最大值,也能确定最大值在数组中应存入的位置 快速排序算法中,每一次递归时以第一个数为基准数,找到数组中所有比基准数小的.再找到所有比基准数大的.小的全部放左边,大的全部放右边,确定基准数的正确位置

  • 核心步骤
  1. 从右开始找比基准数小的
  2. 从左开始找比基准数大的
  3. 交换两个值的位置
  4. 红色继续往左找,蓝色继续往右找,直到两个箭头指向同一个索引为止
  5. 基准数归位
  • 代码实现
public class MyQuiteSortDemo2 {
	public static void main(String[] args) {
		// 1,从右开始找比基准数小的
		// 2,从左开始找比基准数大的
		// 3,交换两个值的位置
		// 4,红色继续往左找,蓝色继续往右找,直到两个箭头指向同一个索引为止
		// 5,基准数归位
		int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
		quiteSort(arr,0,arr.length-1);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	private static void quiteSort(int[] arr, int left, int right) {
		// 递归结束的条件
		if(right < left){
			return;
		}
		int left0 = left;
		int right0 = right;
		//计算出基准数
		int baseNumber = arr[left0];
		while(left != right){
			// 1,从右开始找比基准数小的
			while(arr[right] >= baseNumber && right > left){
				right--;
			}
			// 2,从左开始找比基准数大的
			while(arr[left] <= baseNumber && right > left){
				left++;
			}
			// 3,交换两个值的位置
			int temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
		
		//基准数归位
		int temp = arr[left];
		arr[left] = arr[left0];
		arr[left0] = temp;
		// 递归调用自己,将左半部分排好序
		quiteSort(arr,left0,left-1);
		// 递归调用自己,将右半部分排好序
		quiteSort(arr,left +1,right0);
	}
}

2.4 Arrays (应用)

  • Arrays的常用方法
    【JavaSE】Java基础语法(二十三):递归与数组的高级操作

  • 示例代码

public class MyArraysDemo {
	public static void main(String[] args) {
	// public static String toString(int[] a) 返回指定数组的内容的字符串
	表示形式
	// int [] arr = {3,2,4,6,7};
	// System.out.println(Arrays.toString(arr));
	// public static void sort(int[] a) 按照数字顺序排列指定的数组
	// int [] arr = {3,2,4,6,7};
	// Arrays.sort(arr);
	// System.out.println(Arrays.toString(arr));
	// public static int binarySearch(int[] a, int key) 利用二分查找返回指
	定元素的索引
	int [] arr = {1,2,3,4,5,6,7,8,9,10};
	int index = Arrays.binarySearch(arr, 0);
	System.out.println(index);
	//1,数组必须有序
	//2.如果要查找的元素存在,那么返回的是这个元素实际的索引
	//3.如果要查找的元素不存在,那么返回的是 (-插入点-1)
	//插入点:如果这个元素在数组中,他应该在哪个索引上.
	}
}
  • 工具类设计思想
  1. 构造方法用 private 修饰
  2. 成员用 public static 修饰

【JavaSE】Java基础语法(二十三):递归与数组的高级操作文章来源地址https://www.toymoban.com/news/detail-461420.html

到了这里,关于【JavaSE】Java基础语法(二十三):递归与数组的高级操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【JavaSE】Java基础语法(十八):接口

    接口就是一种公共的规范标准,只要符合规范标准,大家都可以通用。 Java中接口存在的两个意义 用来定义规范 用来做功能的拓展 接口用interface修饰 类实现接口用implements表示 接口不能实例化 我们可以创建接口的实现类对象使用 接口的子类 要么重写接口中的所有抽

    2024年02月06日
    浏览(55)
  • 【JavaSE】Java基础语法(十六):抽象类

    当我们在做子类共性功能抽取时,有些方法在父类中并没有具体的体现,这个时候就需要抽象类了! 在Java中,一个没有方法体的方法应该定义为抽象方法,而类中如果有抽象方法,该类必须定义为抽 象类! 抽象类和抽象方法必须使用 abstract 修饰 抽象类中不一定有抽

    2024年02月07日
    浏览(51)
  • 【JavaSE】java刷题——基础语法熟练应用

    通过本篇题目,可以让初学Java的小伙伴们更加熟练Java的基础语法~ 欢迎关注个人主页:逸狼 创造不易,可以点点赞吗~ 如有错误,欢迎指出~  题述:编写程序数一下 1到 100 的所有整数中出现多少个数字9 分两步 取个位上的9  有9 19 29……99 有10个 取十位上的9  有90 91 92 93…

    2024年04月17日
    浏览(45)
  • 【JavaSE】Java基础语法(十二):ArrayList

    集合和数组的区别 : 共同点:都是存储数据的容器 不同点:数组的容量是固定的,集合的容量是可变的 ArrayList : 可调整大小的数组实现 是一种特殊的数据类型,泛型。 怎么用呢 ? 在出现E的地方我们使用引用数据类型替换即可 举例:ArrayList, ArrayList 成员方法 : 案例需求

    2024年02月06日
    浏览(58)
  • 【JavaSE】Java基础语法(三十一):可变参数

    可变参数介绍 可变参数又称参数个数可变,用作方法的形参出现,那么方法参数个数就是可变的了 方法的参数类型已经确定,个数不确定,我们可以使用可变参数 可变参数定义格式 可变参数的注意事项 这里的变量其实是一个数组 如果一个方法有多个参数,包含可变参数,可

    2024年02月08日
    浏览(54)
  • 【JavaSE】Java基础语法(三十二):Stream流

    案例需求 按照下面的要求完成集合的创建和遍历 创建一个集合,存储多个字符串元素 把集合中所有以\\\"张\\\"开头的元素存储到一个新的集合 把\\\"张\\\"开头的集合中的长度为3的元素存储到一个新的集合 遍历上一步得到的集合 原始方式示例代码 使用Stream流示例代码 Stream流的好处

    2024年02月07日
    浏览(48)
  • 【JavaSE】Java基础语法(三十四):实现多线程

    是指从软件或者硬件上实现多个线程并发执行的技术。 具有多线程能力的计算机因有硬件支持而能够在同一时间执行多个线程,提升性能。 并行:在同一时刻,有多个指令在多个CPU上同时执行。 并发:在同一时刻,有多个指令在单个CPU上交替执行。 进程:是正在运行的程序

    2024年02月08日
    浏览(43)
  • 初始Java篇(JavaSE基础语法)(6)(继承和多态)(上)

                                                            Java学习篇  个人主页(找往期文章包括但不限于本期文章中不懂的知识点):我要学编程(ಥ_ಥ)-CSDN博客 目录 继承篇  为什么需要继承? 继承概念 继承的语法 父类成员访问 super 子类

    2024年04月15日
    浏览(51)
  • 【JavaSE】Java基础语法(三十六):File & IO流

    java.io.File类是文件和目录路径名的抽象表示形式,主要用于文件和目录的创建、查找和删除等操作。 File:它是文件和目录路径名的抽象表示 文件和目录可以通过File封装成对象 File封装的对象仅仅是一个路径名。它可以是存在的,也可以是不存在的。 | 方法名 | 说明 | | —

    2024年02月07日
    浏览(41)
  • 初始Java篇(JavaSE基础语法)(5)(类和对象(上))

    个人主页(找往期文章包括但不限于本期文章中不懂的知识点):我要学编程(ಥ_ಥ)-CSDN博客 目录 面向对象的初步认知 面向对象与面向过程的区别 类的定义和使用  类的定义格式 类的实例化 this引用 什么是this引用? this引用的特性 对象的构造及初始化 如何初始化对象(的

    2024年04月08日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包