[数据结构与算法]常用API、包装类、数组高级

1.0? API

1.1.0? Math类api

1.2.0? System类api

1.3.0? Object类api

1.4.0? Objects类api

?1.4.0? BigDecimal类api

?1.4.1? 构造方法

1.4.2? 常用方法

参数放字符串才可以进行精确运算

1.4.2? 特殊方法

比如当运行除不尽的时候，就会报错，此时可以使用这个方法

2.0? 基本类型包装类

2.1.0? 概述

?2.2.0? Integer类的概述和使用

??2.2.1? Integer类自动拆箱和自动装箱

???2.2.1? 类型转换

3.0? 数组高级

3.1.0? 二分查找

mid计算公式：

?3.1.1? 冒泡排序

?结论：

??3.1.2? 递归

?

递归内存图：

??3.1.2? 快排

代码实现：

• 快速排序概述

  冒泡排序算法中,一次循环结束,就相当于确定了当前的最大值,也能确定最大值在数组中应存入的位置

  快速排序算法中,每一次递归时以第一个数为基准数,找到数组中所有比基准数小的.再找到所有比基准数大的.小的全部放左边,大的全部放右边,确定基准数的正确位置

• 核心步骤

  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);
  ?
   ?  }
  }

4.0? Arrays

• Arrays的常用方法

  方法名	说明
  public static String toString(int[] a)	返回指定数组的内容的字符串表示形式
  public static void sort(int[] a)	按照数字顺序排列指定的数组
  public static int binarySearch(int[] a, int key)	利用二分查找返回指定元素的索引

• 示例代码

  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 修饰

?