04-泛型、数据结构与排序算法

对应原始资料：JavaSE进阶_day05~day06

一、泛型（Generics）

1. 为什么要有泛型

JDK 5 之前集合默认存 Object，取出需强转，容易 ClassCastException。泛型在编译期做类型检查，把运行期异常前移。

2. 泛型类

public class Box<T> {
    private T item;
    public void set(T item) { this.item = item; }
    public T get() { return item; }
}

Box<String> b = new Box<>();
b.set("hello");

3. 泛型方法

public static <E> void print(E[] arr) {
    for (E e : arr) System.out.println(e);
}

4. 泛型接口

interface MyList<E> { void add(E e); }
class MyArrayList<E> implements MyList<E> {
    public void add(E e) { }
}

5. 泛型通配符

写法	含义
<?>	任意类型
<? extends Number>	Number 及其子类（上限，只能取不能存）
<? super Integer>	Integer 及其父类（下限，能存不能取）

PECS 原则：Producer Extends，Consumer Super。

6. 注意事项

• 泛型只支持引用类型，基本类型要用包装类。
• 泛型在编译后被「类型擦除」，运行时没有泛型信息。
• 不能 new T()、不能 new T[]、不能用泛型类做静态字段。

二、常见数据结构

1. 数组

查询快（索引访问 O(1)），增删慢（要移动元素）。

2. 链表

• 单链表：节点存数据 + 下一个节点地址。
• 双向链表：节点存数据 + 前/后节点地址。
• 查询慢 O(n)，首尾增删快 O(1)。

3. 栈（Stack）

后进先出（LIFO）：push 入栈、pop 出栈。LinkedList 可作栈。

4. 队列（Queue）

先进先出（FIFO）：offer 入队、poll 出队。LinkedList 可作队列。

5. 哈希表

通过 hashCode 直接定位元素，查询 O(1)。

• 组成：数组 + 链表 + 红黑树。

6. 树

• 二叉树：每个节点最多两个子节点。
• 二叉搜索树（BST）：左 < 根 < 右，中序遍历是有序的。
• 平衡二叉树（AVL）：左右子树高度差 ≤ 1。
• 红黑树：自平衡 BST，增删查 O(log n)。TreeSet/TreeMap 底层。

三、排序算法

1. 冒泡排序

每轮相邻元素两两比较，把最大值"冒泡"到末尾。时间 O(n²)。

for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t;
        }
    }
}

2. 选择排序

每轮选最小的放到前面。时间 O(n²)。

for (int i = 0; i < arr.length - 1; i++) {
    int min = i;
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[min]) min = j;
    }
    if (min != i) { int t = arr[i]; arr[i] = arr[min]; arr[min] = t; }
}

3. 插入排序

把后一个元素插入到前面已排序序列的正确位置。时间 O(n²)，近乎有序时最快。

4. 快速排序（重点）

分治：选基准，左边比它小，右边比它大，递归。平均 O(n log n)，最坏 O(n²)。

void quickSort(int[] a, int left, int right) {
    if (left >= right) return;
    int i = left, j = right, base = a[i];
    while (i < j) {
        while (i < j && a[j] >= base) j--;
        while (i < j && a[i] <= base) i++;
        if (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
    }
    a[left] = a[i]; a[i] = base;
    quickSort(a, left, i - 1);
    quickSort(a, i + 1, right);
}

5. Arrays.sort 底层

• 基本类型：双轴快速排序。
• 对象：TimSort（归并 + 插入，稳定）。

四、查找算法

1. 顺序查找

遍历比较，O(n)。

2. 二分查找（折半，重点）

前提：数组有序。每次折半。O(log n)。

int binarySearch(int[] a, int key) {
    int l = 0, r = a.length - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (a[m] == key) return m;
        else if (a[m] < key) l = m + 1;
        else r = m - 1;
    }
    return -1;
}

五、Map 的两种排序实现

// 自然排序：Student 实现 Comparable<Student>
class Student implements Comparable<Student> {
    public int compareTo(Student o) { return this.age - o.age; }
}
// 比较器排序：传 Comparator
TreeSet<Student> ts = new TreeSet<>((a, b) -> a.getAge() - b.getAge());

练习建议

1. 自定义泛型类 MyArrayList<T>，实现 add/get/size。
2. 手写冒泡、选择、快速排序，并打印每轮结果。
3. 在有序数组上用二分查找定位元素。
4. 用 TreeSet 对自定义对象按多字段排序（Comparator）。
5. 统计 1000 万个 int 中重复次数最多的前 10（HashMap + 排序）。