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

简介: 1. 递归1.1 递归递归的介绍以编程的角度来看,递归指的是方法定义中调用方法本身的现象把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算

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

计算出mid的值

判断mid位置的元素是否为要查找的元素,如果是直接返回对应索引

如果要查找的值在mid的左半边,那么min值不变,max = mid -1.继续下次循环查找

如果要查找的值在mid的右半边,那么max值不变,min = mid + 1.继续下次循环查找

当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  clapublic 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的常用方法

ebc56a94e73947e98d04127a2c433500.png

  • 示例代码
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 修饰

相关文章
|
1月前
|
Java Apache Maven
Java百项管理之新闻管理系统 熟悉java语法——大学生作业 有源码!!!可运行!!!
文章提供了使用Apache POI库在Java中创建和读取Excel文件的详细代码示例,包括写入数据到Excel和从Excel读取数据的方法。
59 6
Java百项管理之新闻管理系统 熟悉java语法——大学生作业 有源码!!!可运行!!!
|
24天前
|
Java 开发工具 Android开发
Kotlin语法笔记(26) -Kotlin 与 Java 共存(1)
本系列教程笔记详细讲解了Kotlin语法,适合需要深入了解Kotlin的开发者。若需快速学习Kotlin,建议查看“简洁”系列教程。本期重点介绍了Kotlin与Java的共存方式,包括属性、单例对象、默认参数方法、包方法、扩展方法以及内部类和成员的互操作性。通过这些内容,帮助你在项目中更好地结合使用这两种语言。
41 1
|
25天前
|
Java 开发工具 Android开发
Kotlin语法笔记(26) -Kotlin 与 Java 共存(1)
Kotlin语法笔记(26) -Kotlin 与 Java 共存(1)
32 2
|
24天前
|
Java 编译器 Android开发
Kotlin语法笔记(28) -Kotlin 与 Java 混编
本系列教程详细讲解了Kotlin语法,适合需要深入了解Kotlin的开发者。对于希望快速学习Kotlin的用户,推荐查看“简洁”系列教程。本文档重点介绍了Kotlin与Java混编的技巧,包括代码转换、类调用、ProGuard问题、Android library开发建议以及在Kotlin和Java之间互相调用的方法。
20 1
|
24天前
|
安全 Java 编译器
Kotlin语法笔记(27) -Kotlin 与 Java 共存(二)
本教程详细讲解Kotlin语法,适合希望深入了解Kotlin的开发者。若需快速入门,建议查阅“简洁”系列教程。本文重点探讨Kotlin与Java共存的高级话题,包括属性访问、空安全、泛型处理、同步机制及SAM转换等,助你在项目中逐步引入Kotlin。
20 1
|
25天前
|
Java 编译器 Android开发
Kotlin语法笔记(28) -Kotlin 与 Java 混编
Kotlin语法笔记(28) -Kotlin 与 Java 混编
25 2
|
30天前
|
Java 程序员 编译器
在Java编程中,保留字(如class、int、for等)是具有特定语法意义的预定义词汇,被语言本身占用,不能用作变量名、方法名或类名。
在Java编程中,保留字(如class、int、for等)是具有特定语法意义的预定义词汇,被语言本身占用,不能用作变量名、方法名或类名。本文通过示例详细解析了保留字的定义、作用及与自定义标识符的区别,帮助开发者避免因误用保留字而导致的编译错误,确保代码的正确性和可读性。
42 3
|
2月前
|
Java
java基础(11)函数重载以及函数递归求和
Java支持函数重载,即在同一个类中可以声明多个同名方法,只要它们的参数类型和个数不同。函数重载与修饰符、返回值无关,但与参数的类型、个数、顺序有关。此外,文中还展示了如何使用递归方法`sum`来计算两个数之间的和,递归的终止条件是当第一个参数大于第二个参数时。
32 1
java基础(11)函数重载以及函数递归求和
|
25天前
|
安全 Java 编译器
Kotlin语法笔记(27) -Kotlin 与 Java 共存(二)
Kotlin语法笔记(27) -Kotlin 与 Java 共存(二)
29 0
|
2月前
|
Java 数据安全/隐私保护
java之基本语法
java之基本语法
27 6