常见算法(按需研究)

各种算法可视化网站推荐：https://visualgo.net/en

冒泡排序的基础算法

冒泡排序的基础算法运行原理：

1. 比较相邻元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对。最终，最后的元素是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码示例：冒泡排序的基础算法

package algorithm.jungle.test;

import java.util.Arrays;
// 测试冒泡排序的基础算法
public class MaoPao01 {
    public static void main(String[] args) {
        int[] values =  {3,12,4,553,6,2,34,22};
        bubbleSort(values);
        System.out.println(Arrays.toString(values));
    }
    public static void bubbleSort(int[] values){
        int temp;
        for(int i=0;i < values.length;i++){
            // 不对最后一个值操作，然后索引位置依次往后，所以是 values.length -1 - i
            for (int j=0;j < values.length -1 - i;j++){
                if(values[j] > values[j+1]){
                    // 调换位置
                    temp = values[j];
                    values[j] = values[j+1];
                    values[j+1] = temp;
                }
            }
        }
    }
}

冒泡排序的优化算法

冒泡排序的基础算法运行原理：

1. 整个数列分成两部分：前面是无序数列，后面是有序数列。
2. 初始状态下，整个数列都是无序的，有序数列为空。
3. 每一趟循环可以让无序数列中最大数排到最后（即有序数列的元素个数增加 1），即不用去顾及有序数列。
4. 每一趟循环都从数列的第一个元素开始进行比较，依次比较相邻的两个元素，比较无序数列的末尾即可（而不是去比较数列的末尾）；如果前一个大于后一个，就交换。
5. 判断每一趟是否发生了数组元素的交换，如果没有发生，则说明此时数组已经有序，无序再进行后续趟数的比较了，此时就可以中止比较。

代码示例：冒泡排序的优化算法

package algorithm.jungle.test;

import java.util.Arrays;
// 测试冒泡排序的优化算法
public class MaoPao02 {
    public static void main(String[] args) {
        int[] values2 = {1,23,4,5,123,213,12};
        bubbleSort(values2);
        System.out.println(Arrays.toString(values2));
    }
    // 定义冒泡排序的优化算法
    public static void bubbleSort(int[] values2){
        int temp;
        // 外层循环：n 个元素排序，则至多需要 n-1 趟循环
        for (int i=0;i < values2.length -1;i++){
            // 定义一个布尔类型的变量，标记数组是否已达到有序状态
            boolean flag = true;
            /*内存循环：每一趟循环都从数组的前面两个元素开始进行比较，比较到无序数组的最后*/
            for (int j=0;j < values2.length -1 - i;j++){
                // 如果前一个元素大于后一个元素，则交换两元素的值
                if (values2[j] < values2[j+1]){
                    temp = values2[j];
                    values2[j] = values2[j+1];
                    values2[j+1] = temp;
                    // 本趟发生了交换，表明该数组在本趟处于无序状态，需要继续进行比较
                    flag = false;
                }
            }
            // 根据标记量的值判断数组是否有序，如果有序，则退出循环；若无序，则继续循环
            if (flag){
                break;
            }
        }
    }
}

二分法查找

二分法查找又称为折半检索，
基本思想是设数组中元素从小到大有序的存放在数组中，先做好数组排序
首先给定与数组中间位置上元素的关键码 key 比较，
如果 key 相等，则检索成功；
如果 key 小，则在数组前半部分中继续进行二分法检索；
如果 key 大，则在数组后半部分中继续进行二分法检索；
经过一次次比较，不断缩小一半的检索区间，直到检索成功或检索失败。

示意图：

代码示例：

package algorithm.jungle.test;

import java.util.Arrays;
// 测试二分法查找
public class ErFen {
    public static void main(String[] args) {
        // 定义一个数组
        int[] arr = {30,20,50,10,80,9,7,12,100,40,8};
        int searchWord = 40; // 定义要查找的数
        Arrays.sort(arr);  // 二分法查找之前，先对数组元素进行排序
        System.out.println("当前数组：" + Arrays.toString(arr));  // 打印一下当前数组
        System.out.println(searchWord + "元素的索引：" + binarySearch(arr,searchWord));
    }

    // 定义二分法查找的方法
    public static int binarySearch(int[] array,int value){   // 定义数组和查找元素的形参
        int low = 0;
        int high = array.length -1;
        while(low <= high){
            int middle = (low + high) / 2;
            if(value == array[middle]){
                // 返回查询到的索引位置
                return middle;
            }
            if(value > array[middle]){
                low = middle + 1;
            }
            if(value < array[middle]){
                high = middle -1;
            }
        }
        // 上面循环完毕，如果返回 -1，说明没有找到；
        return -1;
    }
}

常用类

知道如何用以及实现原理
主要内容分为

1. 包装类
2. 字符串相关类（String、StringBuilder、StringBuffer）
3. 时间相关类（Date、DateFormat、Calendar）
4. 其他类（Math、Random、File、枚举）
5. 递归打印目录树结构

包装类

简述

Java 在设计类时为每个基本数据类型设计了一个对应的类进行代表，这样的八个和基本数据类型对应的类统称为包装类。
包装类均位于 java.lang 包，八种包装类和基本数据类型的对应关系如下表：

六个类的基本结构继承图：

Number 类是抽象类，因此它的抽象方法，所有子类都需要提供实现。
Number 类提供了抽象方法：intValue()、longValue()、floatValue()、doubleValue()
代表所有的 "数字型" 包装类都可以互相转型。

代码示例：初识包装类

// 测试包装类
public class TestWraperClass {
    public static void main(String[] args) {
        Integer i = new Integer(10);  // 从 Java9开始废弃
        Integer j = new Integer(50);
    }
} 

包装类用途

1. 把基本数据类型转化为对象或把一个包装类对象转为基本数据类型，如 Object[]、集合等操作
2. 包含每种基本数据类型的相同属性，如最大值、最小值等，以及相关的操作方法（这些操作方法的作用是在基本数据类型、包装类对象、字符串之间提供相互之间的转化！）。

包装类测试代码：测试包装类 Integer 的用法，其余包装类与 Integer 类似

package com.jungle.test;

// 测试包装类 Integer 的用法，其余包装类与 Integer 类似
public class TestWraperClass {
    void testInteger() {
        // 基本类型转化成 Integer 对象
        Integer int1 = new Integer(100);
        Integer int2 = Integer.valueOf(20); // 推荐写法
        // Integer 对象转化为 int
        int a = int1.intValue();
        // 字符串转化为 Integer 对象
        Integer int3 = Integer.parseInt("334");
        Integer int4 = Integer.parseInt("9999");
        // Integer 对象转化为字符串
        String str1 = int3.toString();
        // 一些常见 int 类型相关的变量
        System.out.println("int 能代表的最大整数：" + Integer.MAX_VALUE); // int 能代表的最大整数：2147483647
    }
    public static void main(String[] args) {
        TestWraperClass test = new TestWraperClass();
        test.testInteger();
    }
}

自动装箱和自动拆箱

自动装箱和拆箱即将基本数据类型和包装类之间进行自动的互相转换（JDK1.5后引入）。
自动装箱过程通过调用包装类的 valueOf()方法实现。
自动拆箱过程通过调用包装类的 xxxValue() 方法实现（xxx 代表 int、double 等数据类型名词）。

自动装箱

基本类型的数据处于需要对象的环境中时，会自动转为 “对象”。
如： Integer i = 5;

自动拆箱

每当需要一个值时，对象会自动转为基本数据类型，可不去显式调用 intValue()、doubleValue() 等转型方法。
如：Integer i = 5; int j = i;

代码示例：自动装箱和自动拆箱

package com.jungle.test;

import java.util.Arrays;
// 测试自动装箱和拆箱
public class TestInteger02 {
    public static void main(String[] args) {
        // 自动装箱
        Integer a1 = 300;
        // 上方代码等同于下方代码、调用的是 valueOf(300),不是 new Integer(300)
        Integer a2 = Integer.valueOf(300);

        // 自动拆箱
        int b1 = a1;
        // 上方代码等同于下方代码
        int b2 = a1.intValue();
    }
}

包装类空指针异常问题

空指针异常情况是当你对象为空，但是去调用了 空指针对象 的属性或方法，所以报错。
空指针异常报错 java.lang.NullPointerException 含义：对象为 null，然后调用了对象的方法和属性。
注意点：如果遇到空指针异常，那就去看对应的那一行周围都有哪些对象，然后就去看哪个对象是空的，然后调用了哪些方法和属性。

// 空指针异常报错
Integer c1 = null;   // c1 为空对象
int c2 = c1;  // 报错，编译器会自动装箱，会把 c1 改为 c1.intValue();
// java.lang.NullPointerException：对象为 null，然后调用了对象的属性和方法。

包装类缓存问题

整型、char 类型所对应的包装类，在自动装箱时，对于 -128~127 之间的值会进行缓存处理，其目的是提高效率。

// 包装类缓存问题
Integer d1 = 3000;
Integer d2 = 3000;
// 当数字在 [-128,127] 之间时，会去缓存数组中取对应的某个元素对象
Integer d3 = 125;   // 从缓存数组中取 123 元素对象
Integer d4 = 125;   // 从缓存数组中取 123 元素对象
// 互相比较
System.out.println(d1 == d2); // false，d1 和 d2 是两个不同的对象
System.out.println(d3 == d4); // true，d3 和 d4 都是从缓存数组中取的 123 对象
System.out.println(d1.equals(d2)); // true ，equals() 仅比较值

自定义包装类(了解即可)

测试代码：自定义一个包装类(了解即可)

package com.jungle.test;

// 自定义一个包装类(了解即可)
public class MyInteger {
    // 定义缓存值属性
    private int value;
    // 定义一个 MyIteger类的缓存数组，数组名是 cache，数组声明以后需要申请空间
    private static MyInteger[] cache = new MyInteger[256];  // 因为只需要一份缓存数组，所以直接用 static 修饰
    // 定义两个常量来代替 -128，127
    public static final int LOW = -128;
    public static final int HIGH = 127;
    // 静态属性初始化
    static {
        // [-128,127]
        for (int i = LOW;i < HIGH;i++){
            cache[i+128] = new MyInteger(i); // 对元素进行初始化和装箱
        }
    }
    // valueOf() 方法需要外部定义和调用
    public static MyInteger valueOf(int i){
        if (i >= LOW && i <= HIGH){
            return cache[i+128];
        }
        return new MyInteger(i);
    }
    // 定义一个私有构造方法
    private MyInteger(int i){
        this.value = i;
    }
    // 重写 toStrng() 方法
    @Override
    public String toString(){
        // 原本 value 值是数字，使用 "" 进行字符串拼接，让 value 数据类型转换为 String 字符串
        return this.value + "";
    }
    public static void main(String[] args) {
        // 通过 .valueOf(300) 传一个值 300
        MyInteger m1 = MyInteger.valueOf(300);
        // 通过 .valueOf(300) 传一个值 123
        MyInteger m2 = MyInteger.valueOf(123);
        // 原本打印的是一个内存地址（如：com.jungle.test.MyInteger@4554617c），但是可以通过重写 toString() 方法输出为数字
        System.out.println(m1);   // 300
        System.out.println(m2);   // 123
    }
}

基本作业