数据结构初阶（算法的复杂度 + 包装类 + 泛型）

一、算法复杂度

1. 算法效率

• 我们一般是通过算法的复杂度去判断一个算法的好坏，其评判的标准，一般是从时间、空间两个维度来衡量，即时间复杂度和空间复杂度
• 时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间
• 早期，我们更看重于空间复杂度，但随着技术的发展，我们现在更看重时间复杂度

2. 时间复杂度(算法中基本操作的执行次数)

• 概念
  • 算法的时间是难以高效率地测出来的，所以我们通过一个函数去定量描述算法的时间复杂度
    • 不能掐表，因为运行的时间和电脑的硬件是有关系的
    • 时间是要运行的时候才能体现出来，不能每次都上机测试，所以时间复杂度是一个分析方式
    • 时间复杂度是一个估算的值
• 计算：先算出执行的次数，将其转化为函数之后，用O的渐进表示法表示

（1） O的渐进表示法

• 大O符号（Big O notation）：是用于描述函数渐进行为的数学符号

• 推导大O阶方法

  • 用常数1取代运行时间中的所有加法常数。
  • 在修改后的运行次数函数中，只保留最高阶项。
  • 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

• 效果：去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数

• 结果形式：

  • 最坏情况：任意输入规模的最大运行次数(上界)
  • 平均情况：任意输入规模的期望运行次数
  • 最好情况：任意输入规模的最小运行次数(下界)
    在实际中一般情况关注的是算法的最坏运行情况

3. 空间复杂度

概念：对一个算法在运行过程中临时占用存储空间大小的量度，在实际上算的是变量的个数
计算方式：求出变量的个数后，用大O渐进表示法表示

二、包装

2.1 为什么会出现包装

    在Java中，由于基本数据类型不是继承与Object的，为了在泛型代码中可以支持基本类型，Java中每一个基本数据类型都有一个对应的包装类
    对于基本类型来说，包装类中的属性和方法，可以让数据的转换等使用方法更加方便

2.2 分类

除了 Integer 和 Character ，其余基本类型的包装类都是首字母大写

2.3 装箱和拆箱

（1）装箱/装包

• 概念：基本类型------------>包装类型
• 实现方式：新建一个 包装类型对象，将基本数据类型的值放入对象的某个属性中
• 代码示例:

public static void main1(String[] args) {
    int a = 10;
    int b = 20;
    //自动装箱
    Integer i = a;//与Integer i = Integer.valueOf(a);是一样的，JVM会帮着调用一个valueOf方法
    Integer iiii = (Integer) b;

    显示装箱
    int c = 30;
    int d = 40;
    Integer iii = Integer.valueOf(c);//使用类调用的，说明是被static修饰的

    Integer ii = new Integer(d);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

❤️Integer.valueOf方法介绍

• 源代码：

public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}
1
2
3
4
5

• 含义：
  • 如果该 int 类型的值在-127 ~ 128 之间，会缓存在一个数组中，每个数对应的下标是 i + (-IntegerCache.low)
  • 如果不是在-127 ~ 128 之间，会new一个新的对象

（2）拆箱/拆包

• 概念：包装类型------------>类型类型
• 实现方式：将包装类型对象的值取出，放到一个基本数据类型中
• 代码示例：

    public static void main2(String[] args) {
        Integer a = 10;
        //自动拆箱
        int ii = a;
        int iii = (int)a;

        //显示拆箱
        int i = a.intValue();   //用对象调用，说明这是一个类中的方法
        float f = a.floatValue();
    }
1
2
3
4
5
6
7
8
9
10

三、泛型

3.1 泛型的基本概念

• 什么是泛型
  泛型就是适用于许多类型，从代码上讲，就是将类型作为参数
• 泛型的目的
  虽然我们希望泛型适用于许多类型（什么类型的都可以接收），但是如果同时存有不同类型，数据的拿取就会变得很麻烦。
  所以更多情况下，我们还是希望泛型只能持有一种数据类型。
  泛型的主要目的，就是指定当前的容器，要持有什么类型的对象，在编译的时候，让编译器去做检查类型和类型的转换
• 注意
  Java的泛型机制是在编译级别实现的，编译器生成的字节码在运行期间并不包含泛型的类型信息

3.2 泛型的使用

<>里面一定是个引用类型

语法（1）------------>定义一个泛型类
class 泛型类名称<类型形参列表>{
       //这里可以使用类型参数
}

语法（2）------------>定义一个继承某个类的泛型类
class 泛型类名称<类型形参列表> extends 继承类(这里可以使用类型参数){
       //可以只使用部分类型参数
}

语法（3）------------>定义一个泛型类引用
泛型类<类型实参>变量名;      

语法（4）------------>实例化一个泛型类对象
new 泛型类<类型实参>(构造方法实参);      

语法（5）------------>裸类型
概念：是一个泛型类但是没有带着类型实参，意味着什么都能放，那取出来还要强转
注意：不要主动去使用裸类型，因为这是为了兼容老版本保留的机制

• 写法注意

class MyArray4<T>{  //定义一个泛型类，T这边的效果就是传什么就是什么,T表示的是这是一个占位符，表示当前类是一个泛型类
    public Object[] objects = new Object[10];   //最好的写法
    //public T[] objects2 = new T[5];   错误，数组在new的时候，后面一定要跟一个具体的类型
    public T[] objects3 = (T[])new Object[5];   //这种可以，但是不好

    public Object getPos(int pos){
        return objects3[pos];
    }
}

public class Test {
    public static void main(String[] args) {
        MyArray<Integer> myArray = new MyArray<>();   //语法3+语法4，Integer表示指定传的是int类型的
        MyArray<Integer> myArray1 = new MyArray<Integer>();   //裸类型
        //效果和上一行是一样的，实例化对象那边的<>中的包装类型是可以省略的，因为可以根据上下文推导出实例化所需要的类型实参

        //数组在new的时候，后面一定要跟一个具体的类型，因为T这种占位符在运行的时候是不知道是什么的
        //T[] ts = new T[5];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 规范写法（还是用Object接收，取的时候，强制转换就好了）

class MyArray1<T>{
    public Object[] objects = new Object[10];

    public T getPos(int pos){
        return (T)objects[pos];
    }

    public void setPos(int pos, T val){
        objects[pos] = val;
    }
}

public class Test{
    public static void main(String[] args){
        MyArray1<Integer> myArray1 = new MyArray1<>();
        myArray1.setPos(0, 20);
        System.out.println(myArray1.getPos(0));

        MyArray1<String> myArray2 = new MyArray1<>();
        myArray2.setPos(0, "aaa");
        System.out.println(myArray2.getPos(0));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.3 泛型的编译

泛型的编译中需要遵循一个擦除机制
擦除机制就是在编译的过程当中把所有的T替换成Object这种机制，所以在运行的时候是没有T的，即没有泛型的概念

• 既然T[5] = new T[5]在编译的时候，会把T替换成Object，不是相当于Object[5] = new Object[5]吗？为什么是错的？
  • 答：因为数组在new的时候后面一定需要的是一个具体的类型
• 类型擦除，一定是把T变成Object吗？

❤️为什么不能实例化泛型数组
错误示例

class MyArray<T>{
	public T[]array = (T[])new Object[10];

	public T getPos(int pos){
		return this.array[pos];
	}
	
	public void setVal(int pos, T val){
		this.arrar[pos] = val;
	}
	
	public T[] getArray(){
		return array;
	}
}

public class Main{
	public static void main(String[]args){
		MyArrar<Integer> myArray1 = new MyArray<Integer>();
		Integer[] intgers = myArray1.getArray();   //不知道该用什么接收
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

会报错，返回的Object数组里面，可能存放的是任何的数据类型，运行的时间直接传给Integer等类型的数组，会被编译器认为不安全
那怕是强转都不行，因为Object类型表示这里面什么类型都可以放，即可能有char、String等类型，全部都转为Integer会不安全

正确解法

class MyArray1<T>{
    public Object[] objects = new Object[10];

    public T getPos(int pos){
        return (T)objects[pos];
    }

    public void setPos(int pos, T val){
        objects[pos] = val;
    }

    public Object[] getArray(){
        return objects;
    }
}

public class Test{
    public static void main(String[] args){
        MyArray1<Integer> myArray1 = new MyArray1<>();
        myArray1.setPos(0, 20);
        System.out.println(myArray1.getPos(0));

        MyArray1<String> myArray2 = new MyArray1<>();
        myArray2.setPos(0, "aaa");
        System.out.println(myArray2.getPos(0));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3.4 泛型的上界

概念：在定义泛型类时，对传入的类型变量通过类型边界作一定的约束
语法：
         class 泛型类名称<类型形参 extends 类型边界>{
         }
示例
         class MyArray< E extends Number>{
         }
         E要么是Number的子类，要么就是Number

代码示例 ------------------> 写一个泛型类，求数组中的最大值

<>里面的一定是个引用类型，而引用类型是不可以通过大于和小于进行比较的，因为T在编译的时候会变成Object类，Object类是所有类的父类，本身并没有关联Comparable接口，所以这个泛型类要关联Comparable接口

class Alg<T extends Comparable<T>>{   //擦除为一个实现了这个接口的类型
    public T findMax(T[] array) {
        T max = array[0];
        for (int i = 1; i < array.length; i++) {
            //引用类型不可以通过 大于和小于进行比较
            if(max.compareTo(array[i]) < 0 ) {
                max = array[i];
            }
        }
        return max;
    }
}

public class Test{
    public static void main(String[] args){
        Alg<Integer> alg = new Alg<>();
        Integer[] array = {1, 5, 2, 7, 19, 4};
        Integer max = alg.<Integer>findMax(array);  //可以通过array类判断传的是什么类型的数据
        System.out.println(max);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//这是用静态泛型方法去写
class Alg2 {
    public static<T extends Comparable<T>> T findMax(T[] array) {
        T max = array[0];
        for (int i = 1; i < array.length; i++) {
            if(max.compareTo(array[i]) < 0 ) {
                max = array[i];
            }
        }
        return max;
    }
}
public class Test2 {

    public static void main(String[] args) {
        Integer[] array = {1,5,2,7,19,4};
        Integer max = Alg2.<Integer>findMax(array);//可以通过array类判断传的是什么类型的数据
        System.out.println(max);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.4 泛型方法

语法：
方法限定符<类型形参列表> 返回值类型 方法名称（形参列表）{
}

示例

public class Util {
//静态的泛型方法 需要在static后用<>声明泛型类型参数
	public static <E> void swap(E[] array, int i, int j) {
		E t = array[i];
		array[i] = array[j];
		array[j] = t;
	}
}
1
2
3
4
5
6
7
8

使用示例-可以类型推导

Integer[] a = { ... };
swap(a, 0, 9);
String[] b = { ... };
swap(b, 0, 9);
1
2
3
4

使用示例-不使用类型推导

Integer[] a = { ... };
Util.<Integer>swap(a, 0, 9);
String[] b = { ... };
Util.<String>swap(b, 0, 9);
1
2
3
4

3.5 通配符

1. 使用场景

概念：? 用于在泛型的使用，即为通配符
使用场景：可以接收所有的泛型类型，但是又不能够让用户随意修改

public class TestDemo {
	public static void main(String[] args) {
		Message<Integer> message = new Message() ;
		message.setMessage(55);
		fun(message);
	}
	
	// 此时使用通配符"?"描述的是它可以接收任意类型，但是由于不确定类型，所以无法修改
	
	public static void fun(Message<?> temp){
		//temp.setMessage(100); 无法修改！
		System.out.println(temp.getMessage());
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2. 通配符上界

• 语法：
  • <? extends 上界>
  • <? extends Number>//可以传入的实参类型是Number或者Number的子类

class Food {

}

class Fruit extends Food {

}

class Apple extends Fruit {

}
class Banana extends Fruit {

}

class Message<T> { // 设置泛型
	private T message ;
	public T getMessage() {
		return message;
	}
	
	public void setMessage(T message) {
		this.message = message;
	}
}

public class TestDemo {
	public static void main(String[] args) {
		Message<Apple> message = new Message<>() ;
		message.setMessage(new Apple());
		fun(message);
		Message<Banana> message2 = new Message<>() ;
		message2.setMessage(new Banana());
		fun(message2);
}

// 此时使用通配符"?"描述的是它可以接收任意类型
//但是由于不确定类型，所以无法修改.此时无法在fun函数中对temp进行添加元素，
//因为temp接收的是Fruit和他的子类，此时存储的元素应该是哪个子类无法确定
//所以添加会报错！但是可以获取元素。
public static void fun(Message<? extends Fruit> temp){
	//temp.setMessage(new Banana()); //仍然无法修改！
	//temp.setMessage(new Apple()); //仍然无法修改！
	System.out.println(temp.getMessage());
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

通配符的上界，不能进行写入数据，只能进行读取数据

3. 通配符下界

• 语法
  • <? super 下界>
  • <? super Integer>//代表 可以传入的实参的类型是Integer或者Integer的父类类型

class Food {

}

class Fruit extends Food {

}
class Apple extends Fruit {

}

class Plate<T> {
	private T plate ;
	
	public T getPlate() {
		return plate;
	}
	
	public void setPlate(T plate) {
		this.plate = plate;
	}
}

public class TestDemo {
	public static void main(String[] args) {
		Plate<Fruit> plate1 = new Plate<>();
		plate1.setPlate(new Fruit());
		fun(plate1);
		Plate<Food> plate2 = new Plate<>();
		plate2.setPlate(new Food());
		fun(plate2);
}

	public static void fun(Plate<? super Fruit> temp){
		// 此时可以修改！！添加的是Fruit 或者Fruit的子类
	temp.setPlate(new Apple());//这个是Fruit的子类
	temp.setPlate(new Fruit());//这个是Fruit的本身
	//Fruit fruit = temp.getPlate(); 不能接收，这里无法确定是哪个父类
	System.out.println(temp.getPlate());//只能直接输出
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

通配符的下界，不能进行读取数据，只能写入数据。