数据结构与算法基础

概述

数据结构概述

什么是数据结构

​ 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。

数据的存储结构

顺序存储结构

​ 顺序存储结构是把数据元素存放在地址连续的存储单元里，其数据间逻辑关系和物理关系是一致的。

​ 数组就是顺序存储结构的典型代表。

链式存储结构

数据的逻辑结构

集合结构

​ 集合结构中的数据元素同属于一个集合，他们之间是并列的关系，除此之外没有其他关系。

线性结构

​ 线性结构中的元素存在一对一的相互关系。

树形结构

​ 树形结构中的元素存在一对多的相互关系。

图形结构

​ 图形结构中的元素存在多对多的相互关系。

算法概述

算法的定义

是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

线性结构

数组(Array)

数组的基本使用

…

面向对象的数组

import java.util.Arrays;

public class MyArray {
    private int[] elements;

    public MyArray() {
        elements = new int[0];
    }

    // 获取数组长度
    public int size() {
        return elements.length;
    }

    // 获取指定元素的索引
    public int indexOf(int element) {
        for (int i = 0; i < elements.length; i++) {
            if (elements[i] == element) {
                return i;
            }
        }
        return -1;
    }

    // 向数组中增加元素
    public void append(int element) {
        int[] newArr = new int[elements.length + 1];
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        newArr[elements.length] = element;
        elements = newArr;
    }

    // 移除列表中的一个元素（默认最后一个元素）
    public void delete() {
        delete(elements.length - 1);
    }

    public int delete(int index) {
        if (index < 0 || index >= elements.length) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int[] newArr = new int[elements.length - 1];
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = i < index ? elements[i] : elements[i + 1];
        }
        elements = newArr;
    }

    // 删除指定元素
    public boolean remove(int element) {
        if (this.indexOf(element) == -1) {
            return false;
        }
        this.delete(this.indexOf(element));
        return true;
    }

    // 修改指定索引元素
    public int set(int index, int newElement) {
        int oldElement = elements[index];
        elements[index] = newElement;
        return oldElement;
    }

    // 添加元素到指定索引
    public void insert(int index, int newElement) {
        if (index < 0 || index >= elements.length) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int[] newArr = new int[elements.length + 1];
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = i < index ? elements[i] : elements[i - 1];
        }
        newArr[index] = newElement;
        elements = newArr;
    }

    // 获取指定索引元素
    public int get(int index) {
        return elements[index];
    }

    // 反向列表中元素
    public void reverse() {
        int[] newArr = new int[elements.length];
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = elements[elements.length - i - 1];
        }
        elements = newArr;
    }

    // 清空数组
    public void clear() {
        elements = new int[0];
    }

    // 重写toString方法
    public String toString() {
        return Arrays.toString(elements);
    }
}

查找算法

线性查找

// 目标数组
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 8; // 目标元素
int targetIdx = -1; // 目标元素所在下标

for (int i = 0; i < elements.length; i++) {
    if (elements[i] == target) {
        targetIdx = i;
        break;
    }
}

二分查找法

// 目标数组(有序)
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 2; // 目标元素
int start = 0; // 起始索引
int end = arr.length - 1; // 结束索引
int mid = (start + end) / 2; // 中间索引
int index = -1; // 目标元素所在下标

while (true) {
    if (target == arr[mid]) {
        index = mid;
        break;
    } else {
        if (target > arr[mid]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    mid = (start + end) / 2;
}

栈(Stack)

图示

Java中实现

import java.util.Arrays;

public class MyStack {
    Object[] elements;

    public MyStack() {
        elements = new Object[0];
    }

    // 压入元素
    public void push(Object element) {
        Object[] newArr = new Object[elements.length + 1];
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        newArr[elements.length] = element;
        elements = newArr;
    }

    // 弹出元素
    public Object pop() {
        if (elements.length == 0) {
            throw new RuntimeException("Stack is empty");
        }
        Object[] newArr = new Object[elements.length - 1];
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = elements[i];
        }
        Object poppedEle = elements[newArr.length];
        elements = newArr;
        return poppedEle;
    }

    // 查看栈顶元素
    public Object peek() {
        if (elements.length == 0) {
            throw new RuntimeException("Stack is empty");
        }
        return elements[elements.length - 1];
    }

    // 查看栈是否为空
    public boolean isEmpty() {
        return elements.length == 0;
    }

    // 重写toString
    public String toString() {
        return Arrays.toString(elements);
    }
}

队列(Queue)

图示

Java中实现

import java.util.Arrays;

public class MyQueue {
    Object[] elements;

    public MyQueue() {
        elements = new Object[0];
    }

    // 入队
    public void add(Object element) {
        Object[] newArr = new Object[elements.length + 1];
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        newArr[elements.length] = element;
        elements = newArr;
    }

    // 出队
    public Object pull() {
        if (elements.length == 0) {
            throw new RuntimeException("Queue is empty");
        }
        Object[] newArr = new Object[elements.length - 1];
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = elements[i + 1];
        }
        Object pulledEle = elements[0];
        elements = newArr;
        return pulledEle;
    }

    // 查看队列是否为空
    public boolean isEmpty() {
        return elements.length == 0;
    }

    // 重写toString
    public String toString() {
        return Arrays.toString(elements);
    }
}

单链表(Singly Linked List)

图示

Java中实现

public class Node {
    Object data;
    Node next;

    public Node(Object data) {
        this.data = data;
    }

    // 追加节点
    public Node append(Node node) {
        // 递归
//        if (this.next == null) {
//            this.next = node;
//        } else {
//            this.next.append(node);
//        }
        // 循环
        Node currentNode = this;
        while (true) {
            Node nextNode = currentNode.next();
            if (nextNode == null) {
                break;
            }
             currentNode = nextNode;
        }
        currentNode.next = node;
        return this;
    }

    // 获取下一个节点
    public Node next() {
        return this.next;
    }

    // 判断是否是最后一个节点
    public boolean isLast() {
        return this.next == null;
    }

    // 在下一个节点处插入节点
    public void insertAfter(Node node) {
        node.next = this.next;
        this.next = node;
    }

    // 删除下一个节点
    public void removeNext() {
        this.next = this.next.next;
    }

    // 显示当前节点结构
    public void show() {
        Node currentNode = this;
        while (true) {
            if (currentNode.next == null) {
                break;
            }
            System.out.print(currentNode.next.next == null ? currentNode : currentNode + " => ");
            currentNode = currentNode.next;
        }
        System.out.println();
    }

    public String toString() {
        return this.data.toString();
    }
}

循环链表(Circular Linked List)

图示

Java中实现

public class LoopNode {
    Object data;
    LoopNode next = this;

    public LoopNode(Object data) {
        this.data = data;
    }

    // 获取下一个节点
    public LoopNode next() {
        return this.next;
    }

    // 在下一个节点处插入节点
    public LoopNode insertAfter(LoopNode node) {
        node.next = this.next;
        this.next = node;
        return node;
    }

    // 删除下一个节点
    public void removeNext() {
        this.next = this.next.next;
    }

    public String toString() {
        return this.data.toString();
    }
}

双向循环链表(Doubly Circular Linked List)

图示

Java中实现

public class DoubleNode {
    Object data;
    DoubleNode prev = this;
    DoubleNode next = this;

    public DoubleNode(Object data) {
        this.data = data;
    }

    public DoubleNode insertAfter(DoubleNode node) {
        node.prev = this;
        node.next = this.next;
        this.next.prev = node;
        this.next = node;
        return node;
    }

    public DoubleNode prev() {
        return this.prev;
    }

    public DoubleNode next() {
        return this.next;
    }

    public String toString() {
        return this.data.toString();
    }
}

递归

定义

在一个方法（函数）的内部调用该方法（函数）本身的编程方式。

实例

斐波那契数列

public class TestFibonacci {
    public static void main(String[] args) {
        // 斐波那契数列: 1 1 2 3 5 8 13
        System.out.println(fibonacci(7)); // 输出斐波那契数
    }

    public static int fibonacci(int i) {
        if (i == 1 || i == 2) {
            return 1;
        } else {
            return fibonacci(i - 1) + fibonacci(i - 2);
        }
    }
}

汉诺塔问题

​ 有A、B、C三根杆，在A杆自下而上、由大到小按顺序放置n个金盘。把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上。

解决思想

1. 以 C杆 为中介，从 A杆 将 1至n-1号盘 移至 B杆；

2. 将 A杆 中剩下的 第n号盘 移至 C杆 ；

3. 以 A杆 为中介，从 B杆 将 1至n-1号盘 移至 C杆。

public class TestHanoi {
    public static void main(String[] args) {
        hanoi(4, 'A', 'B', 'C');
    }

    /**
     * @param n     共有n个盘子
     * @param from  开始的柱子
     * @param assist    中间的柱子
     * @param to    目标柱子
     */
    public static void hanoi(int n, char from, char assist, char to) {
        if (n > 0) {
            // 1. 以C杆为中介，从A杆将1至n-1号盘移至B杆；
            hanoi(n - 1, from, to, assist);
            // 2. 将A杆中剩下的第n号盘移至C杆；
            System.out.println(from + "-->" + to);
            // 3. 以A杆为中介，从B杆将1至n-1号盘移至C杆。
            hanoi(n - 1, assist, from, to);
        }
    }
}

算法

如何衡量一个算法的优劣

空间复杂度

是指执行当前算法需要占用多少内存空间

时间复杂度

是指执行当前算法所消耗的时间

事后计算的方法

这种方法可行，但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。

事前估算的方法

时间频度T(n)

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 $T(n)$。

时间复杂度O(n)

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用 $T(n)$ 表示，若有某个辅助函数 $f(n)$，使得当 $n$ 趋近于无穷大时，$T(n) / f(n)$ 的极限值为不等于零的常数，则称 $f(n)$ 是$T(n)$ 的同数量级函数。记作 $T(n)=O(f(n))$，称 $O(f(n))$ 为算法的渐进时间复杂度，简称时间复杂度。

$T(n)$不同，但时间复杂度可能相同。如: $T(n)=n²+5n+6$ 与 $T(n)=3n²+3n+2$ 它们的 $T(n)$ 不同，但时间复杂度相同，都为 $O(n^2)$。

在 $T(n)=4n²-2n+2$ 中，就有 $f(n)=n^2$，使得 $T(n)/f(n)$ 的极限值为 4，那么 $O(f(n))$，也就是时间复杂度为 $O(n^2)$

• 对于不是只有常数的时间复杂度忽略时间频度的系数、低次项常数
• 对于只有常数的时间复杂度，将常数看为1

常见的时间复杂度

常数阶 $O(1)$

int i = 1;
i++;

无论代码执行了多少行，只要没有循环等复杂的结构，时间复杂度都是 $O(1)$

对数阶 $O(\log_{2}{n})$

while(i < n) {
    i = i * 2;
}

此处 i 并不是依次递增到 n，而是每次都以倍数增长。假设循环了 x 次后 i > n。则 $2^x == n$，$x=\log_{2}{n}$

线性阶 $O(n)$

for (int i = 0; i < n; i++) {
	i++;
}

这其中，循环体中的代码会执行 n+1 次，时间复杂度为 $O(n)$

线性对数阶 $O(n\log_{2}{n})$

for (int i = 0; i < n; i++) {
    j = 1;
	while(j < n) {
		j = j * 2;
	}
}

此处外部为一个循环，循环了 n 次。内部也是一个循环，但内部循环的时间复杂度是 $O(\log_{2}{n})$

所以总体的时间复杂度为线性对数阶 $O(n\log_{2}{n})$

平方阶 $O(n^2)$

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		//循环体
	}
}

立方阶 $O(n^3)$

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		for (int k = 0; k < n; k++) {
			// 循环体
		}
	}
}

可以看出平方阶、立方阶的复杂度主要是否循环嵌套了几层来决定的。

k 次方阶 $O(n^k)$

for (int i1 = 0; i < n; i1++) {
	for (int i2 = 0; i2 < n; i2++) {
		for (int i3 = 0; i3 < n; i3++) {
			...
                for (int ik = 0; ik < n; ik++) {
                    // 循环体
                }
		}
	}
}

k 次方阶同理。

指数阶 $O(2^n)$

运行时间为 $O(2^n)$ 的算法通常是递归算法，通过递归求解两个大小为 n-1 的小问题来解决大小为 n 的问题。

例如汉诺塔问题：

void solveHanoi(int n, String from, String to, String spare) {
    if (n < 1) return;
    if (n > 1) solveHanoi(n - 1, from, spare, to);
    System.out.println("move from " + from + " to " + to);
    if (n > 1) solveHanoi(n - 1, spare, to, from);
}

设 $T(n)$ 为移动 n 个盘子所需要的时间，那么有：

$$T(n) = \begin{cases} O(1) & n = 1\\ O(1) + 2*O(n-1) & n >1 \end{cases}$$

如果我们反复展开 n>1 的情况：

\begin{align*} T(n) &= 3*O(1) + 4*T(n-2)\\ T(n) &= 7*O(1) + 8*T(n-3)\\ ...\\ T(n) &= (2^{n-1}-1)*O(1) + 2^{n-1}*T(1)\\ T(n) &= (2^n-1)*O(1)\\ T(n) &= O(2^n)\\ \end{align*}

某些递归关系中会导致指数级的结果，一般来说会造成 $O(x^n)$ 的时间复杂度。递推关系式：T(N) = ... + C*T(N-1) (C>1)。

平均时间复杂度和最坏时间复杂度

• 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
• 最坏情况下的时间复杂度称最坏时间复杂度。

一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时向不会比最坏情况更长。

排序算法

常见排序算法

排序算法	时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
冒泡排序	O(n2)	O(n2)	O(n)	O(1)	稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
插入排序	O(n2)	O(n2)	O(n)	O(1)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定
希尔排序	O(n1.3)	O(n2)	O(n)	O(1)	不稳定
快速排序	O(nlog2n)	O(n2)	O(nlog2n)	O(nlog2n)	不稳定
归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不稳定

1、冒泡排序

过程

1. 比较相邻的元素，如果当前元素比后一个大，就交换它俩位置。
2. 循环比较每一对相邻元素，从第一对比较到最后一对，此时数组末尾的元素会是最大的。
3. 每进行一轮循环比较，就会有一个元素被排好顺序，需要比较的元素也就会少一个。
4. 总共进行数组元素个数-1轮循环比较。

优化

• 如果在某轮循环比较发现没有发生交换，则证明数组已经有序。

代码

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{18, 15, 31, 65, 70, 46, 91, 63, 35, 47}; // 目标数组
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        // 总共进行数组元素个数-1轮循环比较
        for (int i = 0; i < arr.length - 1; i++) {
            // 标识，记录本轮循环比较是否发生了交换
            boolean hasSwap = false;
            // 每进行一轮循环比较，需要比较的元素少一个
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                    // 发生了交换，更改标识为true
                    hasSwap = true;
                }
            }
            // 如果这轮循环没发生交换，直接停止外层循环
            if (!hasSwap) break;
        }
    }
}

2、快速排序

过程

1. 从数列中挑出一个元素，称为 “基准”（pivot）。
2. 进行某种操作，使所有比基准值小的元素摆在基准左边，所有比基准值大的元素摆在基准的右边（相同的数可以归到任一边）。某种操作：
   1. （指针）从数组的右侧下标开始向左边移动，找到小于基数的值时停止，将右（指针对应的）的数值赋给左（指针）。
   2. （指针）从数组的左侧下标开始向右边移动，找到大于基数的值时停止，将左（指针对应的）的数值赋给右（指针）。
   3. 将基数插入到合适的位置。
   4. 循环以上三步直至左右（指针）指向同一元素。
3. 递归地把基准值元素左边的子数列和基准值元素的右边子数列排序。

代码

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{18, 15, 31, 65, 70, 46, 91, 63, 35, 47}; // 目标数组
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @param arr 目标数组
     * @param start 开始下标
     * @param end 结束下标
     */
    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return; // 待排序的区域元素小于1个时，直接返回
        int left = start; // 左指针(取区域开始下标)
        int right = end; // 右指针(取区域结束下标)
        int pivot = arr[left]; // 基准数值(取左指针数值)
        // 左右指针指向同一元素时停止循环
        while (left < right) {
            // 指针从数组的右侧下标开始向左边移动，找到小于基数的值时停止
            while(left < right && arr[right] >= pivot) --right;
            // 交换右左指针对应的的数值（此时基准保存着左指针对应的值，不会丢失）
            arr[left] = arr[right];
            // 指针从数组的左侧下标开始向右边移动，找到大于基数的值时停止
            while(left < right && arr[left] <= pivot) ++left;
            // 交换左右指针对应的的数值（此时左指针保存着右指针对应的值）
            arr[right] = arr[left];
            // 将基数插入到左指针的位置
            arr[left] = pivot;
        }
        // 递归处理基准值元素左边的子数列
        quickSort(arr, start, left);
        // 递归处理基准值元素的右边子数列
        quickSort(arr, left + 1, end);
    }
}

3、插入排序

过程

1. 将待排序序列的第一个元素看作有序序列，第二个元素到最后一个元素看作未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

代码

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{18, 15, 31, 65, 70, 46, 91, 63, 35, 47};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        // 从数组的第二个元素开始选择位置插入
        for (int i = 1; i < arr.length; i++) {
            // 保存该位置上元素的值,后面移动元素可能会覆盖该位置上元素的值
            int tmp = arr[i];
            // 遍历前面的有序数组
            int j = i;
            while (j > 0 && temp < arr[j-1]) {
                // 如果有序数组中的元素大于tmp，则后移一个位置
                arr[j] = arr[j-1];
                j--;
            }

            // j选择所指位置就是待插入的位置
            if(j != i) {
                arr[j] = tmp;
            }
        }
    }
}

4、希尔排序

插入排序存在的问题

​ 当最后一个元素为整个数组的最小元素时，需要将前面的有序数组中的每个元素都向后移一位，这样是非常花时间的。所以有了希尔排序来帮我们将数组从无序变为整体有序再变为有序。

过程

1. 选择一个初始步长（一般为数组长度 / 2），步长循环 / 2直到步长为1记作k次。
2. 对数组进行k次插入排序，其中每次插入排序以对应步长把待排序数组分割为（数组长度 / 步长）份，直到步长为1时，整个数组进行一次直接插入排序。

代码

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[]{18, 15, 31, 65, 70, 46, 91, 63, 35, 47};
        shellSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {
        // 计算步长
        for (int step = arr.length / 2; step > 0; step /= 2) {
            // 插入排序
            for (int i = step; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - step;
                for (; j >= 0 && tmp < arr[j]; j -= step) {
                    arr[j + step] = arr[j];
                }
                arr[j + step] = tmp;
            }
        }
    }
}

5、选择排序

过程

1. 遍历整个数组，找到最小（大）的元素，放到数组的起始位置。
2. 再遍历剩下的数组，找到剩下元素中的最小（大）元素，放到数组的第二个位置。
3. 重复以上步骤，直到排序完成。
4. 一共需要遍历数组元素个数-1次，当找到第二大（小）的元素时，可以停止。这时最后一个元素必是最大（小）元素。

代码

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = new int[]{18, 15, 31, 65, 70, 46, 91, 63, 35, 47};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        // 循环数组元素个数-1次
        for (int i = 0; i < arr.length - 1; i++) {
            // 保存最小元素的下标
            int minIndex = i;
            // 将该元素与剩下的元素比较，找出最小元素的下标
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

			// 如果不是 arr[i] 不是最小的元素，就交换元素
            if (minIndex != i) {
                int tmp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = tmp;
            }
        }
    }
}

6、归并排序

过程

归并排序用到了分而治之的思想，其难点是治

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复上一步 直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

代码

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{18, 15, 31, 65, 70, 46, 91, 63, 35, 47};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int start, int end) {
        int split = (start + end) / 2;
        if (start < end) {
            mergeSort(arr, start, split);
            mergeSort(arr, split + 1, end);
            merge(arr, start, end, split);
        }
    }

    /**
    * 将分解的序列进行合并，合并的同时完成排序
    * @param arr 待合并的数组
    * @param left 数组左边界
    * @param right 数组右边界
    */
    public static void merge(int[] arr, int start, int end, int split) {
        // 合并后的临时数组
        int[] mergeArr = new int[end - start + 1];
        int fstHalfIdx = start; // 第一个序列的首元素下标
        int secHalfIdx = split + 1; // 第二个序列的首元素下标
        int mergeArrIdx = 0; // 要插入临时数组的下标

        while (fstHalfIdx <= split && secHalfIdx <= end) {
            // 如果第一个序列的元素小于第二序列的元素，就插入临时数组中
            if (arr[fstHalfIdx] < arr[secHalfIdx]) {
                mergeArr[mergeArrIdx] = arr[fstHalfIdx];
                mergeArrIdx++;
                fstHalfIdx++
            }
            else {
                mergeArr[mergeArrIdx] = arr[secHalfIdx];
                mergeArrIdx++;
                secHalfIdx++;
            }
        }
        
		// 将不为空的序列中的元素依次放入临时数组中
        while (fstHalfIdx <= split) {
            mergeArr[mergeArrIdx] = arr[fstHalfIdx];
            mergeArrIdx++;
            fstHalfIdx++;
        }
        while (secHalfIdx <= end) {
            mergeArr[mergeArrIdx] = arr[secHalfIdx];
            mergeArrIdx++;
            secHalfIdx++;
        }
		
        // 将临时数组中的元素放回原数组
        for (int i = 0; i < mergeArr.length; i++) {
            arr[i + start] = mergeArr[i];
        }
    }
}

7、基数排序

过程

1. 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
2. 从最低位开始，依次进行一次排序
3. 从最低位排序一直到最高位（个位->十位->百位->…->最高位）排序完成以后, 数列就变成一个有序序列

代码

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{9, 3, 94, 31, 52, 409, 7895, 5595, 260};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        // 获取数组中最大的元素
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }
        // 获取最大元素位数
        int maxLength = 0; 
        while (max != 0) {
            max /= 10;
            maxLength++;
        }

        // 循环位数
        for (int n = 0, x = 1; n < maxLength; n++, x *= 10) {
            // 创建一个二维数组，用于表示桶
            // 桶的个数固定为10个（个位是0~9），最大容量由数组的长度决定
            int[][] digitMatrix = new int[10][arr.length];
            // 记录每个桶中有多少个元素
            int[] digitCount = new int[10];
            for (int i = 0; i < arr.length; i++) {
                int digit = arr[i] / x % 10;
                // 存入对应位数
                digitMatrix[digit][digitCount[digit]] = arr[i];
                digitCount[digit]++;
            }

            // 将桶中的元素重新放回到数组中
            int arrIdx = 0; // 用于记录应该放入原数组的哪个位置
            for (int i = 0; i < digitMatrix.length; i++) {
                for (int j = 0; j < digitCount[i]; j++, arrIdx++) {
                    arr[arrIdx] = digitMatrix[i][j];
                }
            }
        }
    }
}

使用队列实现

import demo02.util.MyQueue;

// 基数排序 使用队列实现
public class RadixQueueSort {
    public static void main(String[] args) {
        int[] arr = new int[]{9, 3, 94, 31, 52, 409, 7895, 5595, 260};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) if (arr[i] > max) max = arr[i];
        int maxLength = 0;
        while (max != 0) {
            max /= 10;
            maxLength++;
        }

        for (int n = 0, x = 1; n < maxLength; n++, x *= 10) {
            MyQueue[] digitQueue = new MyQueue[10];
            for (int i = 0; i < digitQueue.length; i++) {
                digitQueue[i] = new MyQueue();
            }

            for (int i = 0; i < arr.length; i++) {
                int digit = arr[i] / x % 10;
                digitQueue[digit].add(arr[i]);
            }

            int arrIdx = 0;
            for (int i = 0; i < digitQueue.length; i++) {
                while(!digitQueue[i].isEmpty()) {
                    arr[arrIdx++] = (int)digitQueue[i].pull();
                }
            }
        }
    }
}

demo02.util.MyQueue

public class MyQueue {
    Object[] elements;

    public MyQueue() {
        elements = new Object[0];
    }

    // 入队
    public void add(Object element) {
        Object[] newArr = new Object[elements.length + 1];
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        newArr[elements.length] = element;
        elements = newArr;
    }

    // 出队
    public Object pull() {
        if (elements.length == 0) {
            throw new RuntimeException("Queue is empty");
        }
        Object[] newArr = new Object[elements.length - 1];
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = elements[i + 1];
        }
        Object pulledEle = elements[0];
        elements = newArr;
        return pulledEle;
    }

    // 查看队列是否为空
    public boolean isEmpty() {
        return elements.length == 0;
    }

    // 重写toString
    public String toString() {
        return Arrays.toString(elements);
    }
}

8、堆排序

介绍

• 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序

• 堆是具有以下性质的完全二叉树：

  • 每个节点的值都大于或等于其左右孩子节点的值，称为

    大顶堆

    • 注意 : 没有要求节点的左孩子的值和右孩子的值的大小关系

  • 每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆

• 一般升序排序采用大顶堆，降序排列使用小顶堆

过程

• 堆是一种树结构，但是排序中会将堆进行顺序存储（变为数组结构）
• 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
• 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
• 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

代码

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{18, 15, 31, 65, 70, 46, 91, 63, 35, 47};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        // 开始位置是最后一个非叶子节点，即最后一个节点的父节点
        int start = (arr.length - 1) / 2;
        // 调整为大顶堆
        for (int i = start; i >= 0; i--) {
            maxHeap(arr, arr.length, i);
        }
        // 把数组中的第0个和堆中的最后一个数交换位置，再把前面的处理为大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            maxHeap(arr, i, 0);
        }
    }

    public static void maxHeap(int[] arr, int size, int index) {
        int leftIdx = 2 * index + 1; // 左子节点索引
        int rightIdx = 2 * index + 2; // 右子节点索引
        int maxIdx = index;
        // 和两个子节点分别对比，找出最大节点
        if (leftIdx < size && arr[leftIdx] > arr[maxIdx]) maxIdx = leftIdx;
        if (rightIdx < size && arr[rightIdx] > arr[maxIdx]) maxIdx = rightIdx;
		// 交换位置
        if (maxIdx != index) {
            int tmp = arr[index];
            arr[index] = arr[maxIdx];
            arr[maxIdx] = tmp;
            // 交换位置后，可能会破坏之前拍好的堆，所以之前排好的堆需要重新调整
            maxHeap(arr, size, maxIdx);
        }
    }
}

树结构

树结构概述

二叉树

基本概念

每个节点最多只能有两个子节点的一种树称为二叉树。

二叉树的子节点分为左节点和右节点。

完全二叉树

​ 所有叶子节点都在最后一层或倒数第二层，且最后一层的叶子节点在左边连续，倒数第二节的叶子节点在右边连续。

满二叉树

​ 所有叶子节点都在最后一层，而且节点总数= 2ⁿ-1 ，n是树的高度。满二叉树是一种特殊的完全二叉树。

链式存储的二叉树

二叉树的遍历

• 前序遍历：先遍历父节点，再遍历左子节点，最后遍历右子节点
• 中序遍历：先遍历左子节点，再遍历父节点，最后遍历右子节点
• 后序遍历：先遍历左子节点，再遍历右子节点，最后遍历父节点

前中后的区别在于父节点遍历的时机

如上：

• 前序遍历结果：1、2、4、5、3
• 中序遍历结果：4、2、5、1、3
• 后序遍历结果：4、5、2、3、1

二叉树的查找

​ 前、中、后序查找与遍历相似，当找到对应的元素时，直接返回即可。

二叉树的删除

需求

• 如果删除的是叶子节点，则直接删除即可。
• 如果删除的是非叶子节点，则删除该子树。

过程

1. 因为二叉树是单向的，所以需要判断当前节点的子节点是否需要删除节点，而不能去判断当前这个节点是不是需要删除节点。
2. 如果当前节点的左子节点不为空且左子节点就是要删除节点，就直接删除左子节点并返回（结束递归）。
3. 如果当前节点的右子节点不为空且右子节点就是要删除节点，就直接删除右子节点并返回（结束递归）。
4. 如果前两步没有删除节点，那么就向左右子树分别进行递归删除。

代码实现

demo.util.BinaryTree.java

public class BinaryTree {
    TreeNode root; // 根节点

    // 设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    // 获取根节点
    public TreeNode getRoot() {
        return root;
    }

    // 前序遍历
    public void preorderTraversal() {
        if (root != null) root.preorderTraversal();
    }

    // 中序遍历
    public void inorderTraversal() {
        if (root != null) root.inorderTraversal();
    }

    // 后序遍历
    public void postorderTraversal() {
        if (root != null) root.postorderTraversal();
    }

    // 前序查找
    public TreeNode preorderSearch(int i) {
        return root.preorderSearch(i);
    }

    // 删除节点
    public void delete(int v) {
        if (root.value == v) {
            root = null;
        } else {
            root.delete(v);
        }
    }
}

demo.util.TreeNode.java

public class TreeNode {
    int value; // 节点的权

    TreeNode leftNode; // 左子节点
    TreeNode rightNode; // 右子节点

    public TreeNode(int value) {
        this.value = value;
    }

    // 前序遍历
    public void preorderTraversal() {
        System.out.println(value);
        if (leftNode != null) leftNode.preorderTraversal();
        if (rightNode != null) rightNode.preorderTraversal();
    }

    // 中序遍历
    public void inorderTraversal() {
        if (leftNode != null) leftNode.inorderTraversal();
        System.out.println(value);
        if (rightNode != null) rightNode.inorderTraversal();
    }

    // 后序遍历
    public void postorderTraversal() {
        if (leftNode != null) leftNode.postorderTraversal();
        if (rightNode != null) rightNode.postorderTraversal();
        System.out.println(value);
    }

    // 前序查找
    public TreeNode preorderSearch(int v) {
        TreeNode target = null;
        if (this.value == v) {
            return this;
        }else {
            if (leftNode != null) {
                target = leftNode.preorderSearch(v);
            }
            if (target != null) return target;
            if (rightNode != null) {
                target = rightNode.preorderSearch(v);
            }
        }
        return target;
    }

    // 中序查找
    public TreeNode inorderSearch(int v) {
        if (leftNode.inorderSearch(v) != null) {
            return leftNode;
        } else if (this.value == v) {
            return this;
        } else if (rightNode.inorderSearch(v) != null) {
            return rightNode;
        }
        return null;
    }

    // 后序查找
    public TreeNode postorderSearch(int v) {
        if (leftNode.postorderSearch(v) != null) {
            return leftNode;
        } else if (rightNode.postorderSearch(v) != null) {
            return rightNode;
        } else if (this.value == v) {
            return this;
        }
        return null;
    }

    // 设置左子节点
    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    // 设置右子节点
    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    // 删除节点
    public void delete(int v) {
        if (leftNode != null) {
            if (leftNode.value == v) {
                leftNode = null;
                return;
            } else {
                leftNode.delete(v);
            }
        }
        if (rightNode != null) {
            if (rightNode.value == v) {
                rightNode = null;
            } else {
                rightNode.delete(v);
            }
        }
    }
}

顺序存储的二叉树

基本概述

​ 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。

性质

• 顺序存储的二叉树通常情况只考虑完全二叉树。
• 第 n 个元素的左子节点为：2*n+1
• 第 n 个元素的右子节点为：2*n+2
• 第 n 个元素的父节点为：(n-1)/2

代码实现

public class ArrayBinaryTree {
    int[] data;

    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }

    // 前序遍历
    public void preorderTraversal() {
        preorderTraversal(0);
    }

    public void preorderTraversal(int index) {
        if (data == null || data.length == 0) return;
        System.out.println(data[index]);
        if (2 * index + 1 < data.length) {
            preorderTraversal(2 * index + 1);
        }
        if (2 * index + 2 < data.length) {
            preorderTraversal(2 * index + 2);
        }
    }
}

线索化二叉树

基本概述

​ 一般的二叉树叶子节点的左右指针都为空，这样就会造成空间的浪费。为了减少浪费，便有了线索化二叉树

• n个节点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继节点的指针。
• 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
• 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
• 如果一个节点已经有了左右子节点(子树)，那么该节点就不能被线索化了，所以线索化二叉树后，节点的 leftNode 和 rightNode 有如下两种情况：
  • leftNode 可能指向左子节点(子树)，也可能指向的是前驱节点
  • rightNode 可能指向的是右子节点(子树)，也可能指向的是后继节点

中序线索化前

中序遍历结果：4, 2, 5, 1, 3, 6

中序线索化后

思路

• 每个节点需要用两个变量(leftType, rightType)来表示左右指针的类型（保存左右子节点(子树)，还是前驱后继）。
• 需要用两个变量(leftNode, rightNode)来表示当前节点和当前节点的前驱节点。
• 通过将当前节点的左指针指向前驱节点，来实现前驱节点的绑定。
• 通过将前驱节点的右指针指向当前节点，来实现后继节点的绑定。

遍历中序线索化二叉树

• 各个节点可以通过线性(循环)的方式遍历，无需使用递归的方式遍历。
• 首先有一个外循环，代替递归操作，循环条件的暂存节点不为空。
• 第一个内循环用于找到第一个元素，然后打印。
• 第二个循环用于找到节点的后继元素。
• 最后将暂存节点改为右子节点。

代码实现

demo08.util.ThreadedBinaryTree.java

package demo08.util;

public class ThreadedBinaryTree {
    ThreadedTreeNode root; // 根节点
    ThreadedTreeNode preNode; // 临时存储前驱节点

    // 中序线索化二叉树
    public void threadNodes() {
        threadNodes(root);
    }

    public void threadNodes(ThreadedTreeNode node) {
        if (node == null) return; // 当前节点为叶子节点 返回
        threadNodes(node.leftNode); // 处理左子树
        // 处理左指针
        if (node.leftNode == null) {
            node.leftType = 1; // 改变左值针类型
            node.leftNode = preNode;
        }
        // 处理前驱节点的右指针
        if (preNode != null && preNode.rightNode == null) {
            preNode.rightType = 1;
            preNode.rightNode = node;
        }
        // 每处理一个节点，当前节点就是下一个节点的前驱节点
        preNode = node;
        threadNodes(node.rightNode); // 处理右子树

    }

    // 遍历中序线索化二叉树
    public void threadIterate() {
        ThreadedTreeNode node = root;
        while (node != null) {
            while(node.leftType == 0) {
                node = node.leftNode;
            }
            System.out.println(node.value);
            while (node.rightType == 1) {
                node = node.rightNode;
                System.out.println(node.value);
            }
            node = node.rightNode;
        }
    }


    public void setRoot(ThreadedTreeNode root) {
        this.root = root;
    }

    public ThreadedTreeNode getRoot() {
        return root;
    }

    public void preorderTraversal() {
        if (root != null) root.preorderTraversal();
    }

    public void inorderTraversal() {
        if (root != null) root.inorderTraversal();
    }

    public void postorderTraversal() {
        if (root != null) root.postorderTraversal();
    }

    public void delete(int v) {
        if (root.value == v) {
            root = null;
        } else {
            root.delete(v);
        }
    }
}

demo08.util.ThreadedTreeNode.java

package demo08.util;

public class ThreadedTreeNode {
    public int value;

    public ThreadedTreeNode leftNode; // 左指针
    public ThreadedTreeNode rightNode; // 右指针
    int leftType, rightType; // 标识指针类型

    public ThreadedTreeNode(int value) {
        this.value = value;
    }
    
    public void setLeftNode(ThreadedTreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(ThreadedTreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public void preorderTraversal() {
        System.out.println(value);
        if (leftNode != null) leftNode.preorderTraversal();
        if (rightNode != null) rightNode.preorderTraversal();
    }

    public void inorderTraversal() {
        if (leftNode != null) leftNode.inorderTraversal();
        System.out.println(value);
        if (rightNode != null) rightNode.inorderTraversal();
    }

    public void postorderTraversal() {
        if (leftNode != null) leftNode.postorderTraversal();
        if (rightNode != null) rightNode.postorderTraversal();
        System.out.println(value);
    }

    public void delete(int v) {
        if (leftNode != null) {
            if (leftNode.value == v) {
                leftNode = null;
                return;
            } else {
                leftNode.delete(v);
            }
        }
        if (rightNode != null) {
            if (rightNode.value == v) {
                rightNode = null;
            } else {
                rightNode.delete(v);
            }
        }
    }
}

赫夫曼树

定义

• 给定 n 个权值作为 n 个叶子节点，构造一棵二叉树，若该树的带权路径长度(WPL)达到最小，则该树为最优二叉树，也被称为 哈夫曼树(Huffman Tree)。
• 哈夫曼树是带权路径长度最短的树，权值越大的节点离根越近。

基本概念

• 路径和路径长度：在一棵树中，从一个节点往下可以达到的孩子或孙子节点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根节点的层数为1，则从根节点到第L层节点的路径长度为 L-1。
• 节点的权：若将树中节点赋给一个有着某种含义的数值，则这个数值称为该节点的权。
• 节点的带权路径长度：从根节点到该节点之间的路径长度与该节点的权的乘积（W×L）。
• 树的带权路径长度：树的带权路径长度规定为所有叶子节点的带权路径长度之和（W1×L1+W2×L2…），记为WPL(Weighted Path Length) ，权值越大的节点离根节点越近的二叉树才是最优二叉树。

$$WPL(a) = 9×2+4×2+5×2+2×2 = 40\\ WPL(b) = 9×1+5×2+4×3+2×3 = 37\\ WPL(c) = 4×1+2×2+3×5+9×3 = 50$$

创建赫夫曼树的流程

1. 从小到大进行排序，将每一个数据看成是一棵最简单的二叉树。
2. 取出根节点权值最小的两颗二叉树。
3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和。
4. 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复直到数组中所有的数据都被处理，就得到一颗赫夫曼树。

代码实现

demo09.util.HuffmanTree.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {
    public TreeNode rootNode;

    public HuffmanTree(int[] arr) {
        this.rootNode = HuffmanTree.create(arr);
    }

    // 创建赫夫曼树
    public static TreeNode create(int[] arr) {
        // 先使用数组中所有的元素创建若干个单节点二叉树
        List<TreeNode> treeNodes = new ArrayList<>();
        for (int value : arr) {
            treeNodes.add(new TreeNode(value));
        }

        // 循环处理
        while (treeNodes.size() > 1) {
            // 排序
            Collections.sort(treeNodes);
            // 取出来权值最小的两个二叉树
            TreeNode minNode = treeNodes.get(treeNodes.size() - 1);
            TreeNode secMinNode = treeNodes.get(treeNodes.size() - 2);
            // 创建一棵新的二叉树
            TreeNode parentNode = new TreeNode(minNode.value + secMinNode.value);
            parentNode.leftNode = minNode;
            parentNode.rightNode = secMinNode;
            // 把取出来的两个二叉树移除
            treeNodes.remove(treeNodes.size() - 1);
            treeNodes.remove(treeNodes.size() - 1);
            // 把新二叉树放入原数组中
            treeNodes.add(parentNode);
        }

        return treeNodes.get(0);
    }

    // 前序遍历树
    public void preTraversal() {
        preTraversal(rootNode);
    }

    public void preTraversal(TreeNode node) {
        node.preTraversal();
    }
}

demo09.util.TreeNode.java

public class TreeNode implements Comparable<TreeNode> {
    int value;
    public TreeNode leftNode, rightNode;

    public TreeNode(int value) {
        this.value = value;
    }

    public void preTraversal () {
        System.out.println(this);
        if (leftNode != null) leftNode.preTraversal();
        if (rightNode != null) rightNode.preTraversal();
    }

    @Override
    public int compareTo(TreeNode o) {
        return o.value - this.value;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                '}';
    }
}

赫夫曼编码

基本概念

前缀编码: 字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码。

创建赫夫曼编码

1. 统计需编码的字符串中，各个字符出现的次数。
   • can you can a can as a can canner can a can.
   • r:1 s:1 e:1 y:1 .:1 o:1 c:7 n:8 :11 a:11
2. 将字符出现的次数作为权值，构建哈弗曼树。
3. 根据哈弗曼树进行编码，向左的路径为0，向右的路径为1，字符编码结果如图：

字符串编码结果为：

11110000111001011000110100011111000011001111100001101101110110011111000011111000001101011101100111110000110011111000110011

代码实现

demo10.util.HuffmanCode.java

import java.io.*;
import java.util.*;

public class HuffmanCode {
    final byte[] UNICODE;
    byte[] huffmanCode;
    Map<Byte, String> huffmanCodeTable;

    public HuffmanCode(String msg) {
        this(msg.getBytes());
    }

    public HuffmanCode(byte[] bytes) {
        this.UNICODE = bytes;
        List<Node> nodes = getNodes(bytes);
        Node huffmanTree = createHuffmanTree(nodes);
        this.huffmanCodeTable = getHuffmanTable(huffmanTree);
        this.huffmanCode = huffmanEncode(bytes, this.huffmanCodeTable);
    }
    // 进行赫夫曼编码
    public static byte[] zip(String msg) {
        return zip(msg.getBytes());
    }

    /**
     * 进行赫夫曼编码
     *
     * @param bytes
     * @return
     */
    public static byte[] zip(byte[] bytes) {
        // 统计每一个byte出现的次数，并放入一个集合中
        List<Node> nodes = getNodes(bytes);
        // 创建赫夫曼树
        Node huffmanTree = createHuffmanTree(nodes);
        // 创建赫夫曼编码表
        Map<Byte, String> huffmanTable = getHuffmanTable(huffmanTree);
        // 编码并返回
        return huffmanEncode(bytes, huffmanTable);
    }

    // 解码
    public static String unzipToStr(byte[] huffmanCode, Map<Byte, String> huffmanTable) {
        return new String(unzip(huffmanCode, huffmanTable));
    }

    public static byte[] unzip(byte[] huffmanCode, Map<Byte, String> huffmanTable) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < huffmanCode.length; i++) {
            // 最后一个不用补零
            if (i == huffmanCode.length - 1) {
                sb.append(Integer.toBinaryString(huffmanCode[i]));
                break;
            }
            sb.append(byteToBitStr(huffmanCode[i]));
        }

        // 把字符串按照指定的赫夫曼编码进行解码
        // 把赫夫曼编码的键值对进行调换
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanTable.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        // 创建一个集合用于存放byte数组
        List<Byte> list = new ArrayList<>();

        // 处理字符串
        for (int i = 0; i < sb.length();) {
            int count = 1;
            boolean flag = true;
            // 截取出一个byte
            while (flag) {
                String key = sb.substring(i, i + count);
                Byte b = map.get(key);
                if (b == null) {
                    count++;
                } else {
                    list.add(b);
                    flag = false;
                }
            }
            i += count;
        }

        // 集合转换为数组
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < list.size(); i++) {
            bytes[i] = list.get(i);
        }

        return bytes;
    }

    /**
     * 压缩文件
     * @param src 输入路径
     * @param dst 输出路径
     * @throws IOException
     */
    public static void zipFile(String src, String dst) throws IOException {
        // 创建一个输入流
        InputStream is = new FileInputStream(src);
        // 创建一个和输入流指向的文件大小一样的byte数组
        byte[] bytes = new byte[is.available()];
        // 读取文件内容
        is.read(bytes);
        is.close();
        // 使用赫夫曼编码进行编码
        byte[] byteZip = zip(bytes);
        System.out.println("ori:" + bytes.length);
        System.out.println("zipped:" + byteZip.length);
        // 输出流
        OutputStream os = new FileOutputStream(dst);
        ObjectOutputStream oos  = new ObjectOutputStream(os);
        // 把压缩后的byte数组写入文件
        oos.writeObject(byteZip);
        // 把赫夫曼编码表写入文件
        oos.writeObject(huffmanCodes);
        oos.close();
        os.close();
    }

    /**
     * 解压文件
     * @param src 输入路径
     * @param dst 输出路径
     */
    public static void unzipFile(String src, String dst) throws IOException, ClassNotFoundException {
        // 创建一个输入流
        InputStream is = new FileInputStream(src);
        ObjectInputStream ois = new ObjectInputStream(is);
        // 读取byte数组
        byte[] bytes = (byte[]) ois.readObject();
        // 读取赫夫曼编码表
        Map<Byte, String> map = (Map<Byte, String>) ois.readObject();
        ois.close();
        is.close();
        // 解码
        byte[] byteUnzip = unzip(bytes, map);
        // 创建一个输出流
        OutputStream os = new FileOutputStream(dst);
        // 写出数据
        os.write(byteUnzip);
        os.close();

    }


    /**
     * 把byte数组转为node集合
     *
     * @param bytes
     * @return
     */
    private static List<Node> getNodes(byte[] bytes) {
        List<Node> nodes = new ArrayList<>();
        // 统计每一个byte出现了多少次
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            if (!counts.containsKey(b)) {
                counts.put(b, 1);
            } else {
                counts.put(b, counts.get(b) + 1);
            }
        }
        // 把每一个键值对转为node对象
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    /**
     * 创建赫夫曼树
     *
     * @param nodes
     * @return
     */
    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            // 排序
            Collections.sort(nodes);
            // 取出来权值最小的两个二叉树
            Node minNode = nodes.get(nodes.size() - 1);
            Node secMinNode = nodes.get(nodes.size() - 2);
            // 创建一棵新的二叉树
            Node parent = new Node(null, minNode.weight + secMinNode.weight);
            parent.left = minNode;
            parent.right = secMinNode;
            // 把取出来的两个二叉树移除
            nodes.remove(nodes.size() - 1);
            nodes.remove(nodes.size() - 1);
            // 把新二叉树放入原数组中
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    /**
     * 根据赫夫曼树获取赫夫曼编码表
     *
     * @param huffmanTree
     * @return
     */
    // 临时存储上一次的路径
    private static StringBuilder prevPath = new StringBuilder();
    // 存储赫夫曼编码
    private static Map<Byte, String> huffmanCodes = new HashMap<>();

    private static Map<Byte, String> getHuffmanTable(Node node) {
        if (node == null) return null;
        getHuffmanTable(node.left, "0", prevPath);
        getHuffmanTable(node.right, "1", prevPath);
        return huffmanCodes;
    }

    private static void getHuffmanTable(Node node, String path, StringBuilder prevPath) {
        StringBuilder thisPath = new StringBuilder(prevPath);
        thisPath.append(path);
        if (node.data == null) {
            getHuffmanTable(node.left, "0", thisPath);
            getHuffmanTable(node.right, "1", thisPath);
        } else {
            huffmanCodes.put(node.data, thisPath.toString());
        }
    }

    /**
     * 根据原byte数组和赫夫曼编码表编码
     *
     * @param bytes
     * @param huffmanTable
     * @return
     */
    private static byte[] huffmanEncode(byte[] bytes, Map<Byte, String> huffmanTable) {
        // 字符串形式的赫夫曼编码
        StringBuilder strHuffmanCode = new StringBuilder();
        // 赫夫曼编码
        byte[] huffmanCode;
        // 把需要压缩的byte数组处理成二进制的字符串
        for (byte b : bytes) {
            strHuffmanCode.append(huffmanTable.get(b));
        }
        // 定义长度
        if (strHuffmanCode.length() % 8 == 0) {
            huffmanCode = new byte[strHuffmanCode.length() / 8];
        } else {
            huffmanCode = new byte[strHuffmanCode.length() / 8 + 1];
        }

        for (int i = 0; i < strHuffmanCode.length(); i += 8) {
            String strByte;
            if (i + 8 > strHuffmanCode.length()) {
                strByte = strHuffmanCode.substring(i);
            } else {
                strByte = strHuffmanCode.substring(i, i + 8);
            }
            byte b = (byte)Integer.parseInt(strByte, 2);
            huffmanCode[i / 8] = b;
        }
        return huffmanCode;
    }


    private static String byteToBitStr(byte b) {
        int tmp = b;
        tmp |= 256;
        String str = Integer.toBinaryString(tmp);
        return str.substring(str.length() - 8);
    }

    public byte[] getHuffmanCode() {
        return huffmanCode;
    }

    public Map<Byte, String> getHuffmanCodeTable() {
        return huffmanCodeTable;
    }
}

demo10.util.Node.java

public class Node implements Comparable<Node> {
    Byte data;
    int weight;
    Node left, right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return o.weight - this.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
}

二叉排序（搜索）树

二叉排序树(Binary Sort Tree)又称二叉搜索树(Binary Search Tree)

定义

• 一棵空树，或者是一棵二叉树，对于这个二叉树中任何一个非叶子节点，要求其左子节点的权值比其权值要小，右子节点的权值比其权值要大，这样的二叉树被称为二叉排序树(二叉搜索树)。

• 权值相同的节点可以互相交换位置。

图示

有一组数据 [7, 3, 10, 12, 5, 1, 9] ，其对应的二叉排序树为：

二叉排序树的添加

1. 判断新加入节点的权值比根节点权值的大小关系
2. 如果小于，且根节点有左子节点，则将新节点添加进根节点的左子树
3. 如果大于，且根节点有右子节点，则将新节点添加进根节点的右子树
4. 递归进行以上三步，直到左/右子节点为空，就将新节点放入对应位置

二叉排序树的查找

1. 把所给值与根节点左右子节点的权值比较
2. 如果小于，在根节点的左子树递归查找
3. 如果大于，在根节点的右子树递归查找

二叉排序树的删除

1. 找到待删除的节点
2. 找到待删除节点的父节点
3. 判断待删除节点是其父节点的左孩子还是右孩子

删除叶子节点

4. 然后让其令为空

删除度为1的节点(只有一棵子树/子节点)

4. 判断待删除节点的子树是其左孩子还是右孩子
5. 让父节点指向待删除节点的子树指向待删除节点的子树

删除度为2的节点(有两棵子树/子节点)

4. 顺着待删除节点的右子树，找到一个值最小的节点（该值的大小最接近待删除节点的值）
5. 将上面找到节点的值赋给待删除节点
6. 删除上面找到的节点

代码实现

demo11.util.BinarySortTree.java

public class BinarySortTree {
    Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void preorderTraversal() {
        if (root != null) root.preorderTraversal();
    }

    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public void delete(int value) {
        if (root == null) return;
        Node target = root.search(value);
        if (target == null) return;
        Node parent = searchParent(value);
        // 要删除的节点是叶子节点
        if (target.left == null && target.right == null) {
            if (parent.left.value == value) {
                parent.left = null;
            } else parent.right = null;
        // 要删除的节点有两颗子树
        } else if (target.left != null && target.right != null) {
            // 找到目标右子树中最小的节点拿到其值并删除
            int min = deleteMin(target.right);
            // 把目标节点的值替换为上面得到的值
            target.value = min;
        // 要删除的节点只有一棵子树
        } else {
            if (parent.left.value == value) {
                if (target.left != null) {
                    parent.left = target.left;
                } else parent.left = target.right;
            }
            if (parent.right.value == value) {
                if (target.left != null) {
                    parent.right = target.left;
                } else parent.right = target.right;
            }

        }

    }

    private int deleteMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        delete(node.value);
        return node.value;
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }
}

demo11.util.Node.java

public class Node {
    public int value;
    Node left, right;

    public Node(int value) {
        this.value = value;
    }

    public void add(Node node) {
        if (node == null) return;

        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                right.add(node);
            }
        }
    }

    public void preorderTraversal() {
        if(left != null) left.preorderTraversal();
        System.out.println(this.value);
        if(right != null) right.preorderTraversal();

    }

    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) return null;
            return left.search(value);
        }else {
            if (right == null) return null;
            return right.search(value);
        }
    }

    public Node searchParent(int value) {
        if ((left != null && left.value == value) || (right != null && right.value == value)) {
            return this;
        } else if (value < this.value) {
            if (left == null) return null;
            return left.searchParent(value);
        }else {
            if (right == null) return null;
            return right.searchParent(value);
        }
    }
}

平衡二叉树

二叉排序树的问题

以数组 [1, 2, 3, 4, 5, 6, 7, 8] 来构建一棵平衡二叉树时：

可以看到该二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。

基本概述

• 平衡二叉树又名平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树，可以保证查询效率较高。
• 一棵空树或一棵左右两个子树的高度差的绝对值不超过 1 且左右两个子树都是一棵平衡二叉树的二叉排序树。

二叉排序树转换平衡二叉树

单旋转

左旋转

当前节点左子树高度比右子树高度要高于 1 时对当前节点进行左旋转

具体步骤

1. 创建一个新节点，值等于当前节点的值
   • 
2. 把新节点的右子树设置为当前节点的右子树
   • 
3. 把新节点的左子树设置为当前节点的左子树的右子树
   • 
4. 把当前节点的值改为左子节点的值
   • 
5. 把当前节点的左子树改为左子树的左子树
   • 
6. 把当前节点的右子树设置为新节点
   • 

右旋转

当前节点左子树高度比右子树高度要低于 1 时对当前节点进行右旋转

具体步骤 : 和左旋转步骤相同，每一步镜像相反

双旋转

如图，以下情况需要双旋转

1. 需要对当前节点进行左旋转的前提下，如下图，当前节点的左子树的左子树(1)高度小于左子树的右子树(3→4)高度
2. 需要对当前节点进行右旋转的前提下，当前节点的右子树的左子树高度大于右子树的右子树高度

先对根节点的左节点进行左旋转

再对根节点进行右旋转

代码实现

demo12.util.BinarySortTree.java 同上 demo11.util.BinarySortTree.java

demo12.util.Node.java

public class Node {
    public int value;
    public Node left, right;

    public Node(int value) {
        this.value = value;
    }

    // 获取当前节点高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    // 获取左子树的高度
    public int leftHeight () {
        return left == null ? 0 : left.height();
    }

    // 获取右子树的高度
    public int rightHeight () {
        return right == null ? 0 : right.height();
    }

    public void add(Node node) {
        if (node == null) return;

        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                right.add(node);
            }
        }

        // 检查是否平衡
        if(leftHeight() - rightHeight() > 1) {
            // 双旋转
            if (left != null && left.leftHeight() < left.rightHeight()) {
                left.leftRotate();
            }
            // 单旋转
            rightRotate();
        }
        if (leftHeight() - rightHeight() < -1) {
            if (right != null && right.leftHeight() > right.rightHeight()) {
                right.rightRotate();
            }
            leftRotate();
        }

    }

    // 右旋转
    private void rightRotate() {
        // 创建一个新节点，值等于当前节点的值
        Node newRight = new Node(value);
        // 把新节点的右子树设置为当前节点的右子树
        newRight.right = right;
        // 把新节点的左子树设置为当前节点的左子树的右子树
        newRight.left = left.right;
        // 把当前节点的值改为左子节点的值
        value = left.value;
        // 把当前节点的左子树改为左子树的左子树
        left = left.left;
        // 把当前节点的右子树设置为新节点
        right = newRight;
    }

    // 左旋转
    private void leftRotate() {
        Node newLeft = new Node(value);
        newLeft.left = left;
        newLeft.right = right.left;
        value = right.value;
        right = right.right;
        left = newLeft;
    }

    public void preorderTraversal() {
        if (left != null) left.preorderTraversal();
        System.out.println(this.value);
        if (right != null) right.preorderTraversal();

    }

    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) return null;
            return left.search(value);
        } else {
            if (right == null) return null;
            return right.search(value);
        }
    }

    public Node searchParent(int value) {
        if ((left != null && left.value == value) || (right != null && right.value == value)) {
            return this;
        } else if (value < this.value) {
            if (left == null) return null;
            return left.searchParent(value);
        } else {
            if (right == null) return null;
            return right.searchParent(value);
        }
    }
}

n 叉树

基本概念

​ 二叉树中每个节点有一个数据项,最多有两个子节点,如果允许树的每个节点可以有两个以上的子节点,那么这个树就称为 n 阶的多叉树，或者称为 n 叉树（n-ary tree）。

性质

• 每个节点有m个子节点和m-1个键值。
• 每个节点中的键值按升序排列。
• 前i个子节点中的键值都小于第i个键值。
• 后m-1个子节点中的键值都大于第i个键值。

优点

多叉树通过重新组织节点，可以减少树的高度，能对二叉树进行优化。

2-3 树

2-3 树是最简单的B树结构（3阶的B树）。

基本概述

• 2-3树的所有叶子节点都在同一层（只要是B树都满足这个条件）。
• 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。
• 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。
• 2-3树是由二节点和三节点构成的树。

插入规则

• 所有叶子节点都在同一层。
• 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。
• 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。
• 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面 3个条件。
• 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则。
  • 左边的子树值小于父节点的值。
  • 中间的子树值在父节点的值之间。
  • 右边子树的值大于父节点的值。

B树和B+树

B树

• B树的阶：节点的最多子节点个数。比如：2-3树的阶是3，2-3-4树的阶是4。

B+树

• 非叶子节点只存储索引信息，不存储数据
• 叶子节点最右边的指针指向下一个相邻的叶子节点
• 所有的叶子节点组成了一个有序链表

哈希表

基本概述

​ 哈希表(Hash table)又名散列表，是根据关键码值(key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

(散列函数使用取余法, 处理散列冲突使用链地址法)

散列函数

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

常用的设计散列函数的方法：

• 直接定址法
• 数字分析法
• 平方取中法
• 取余法
• 随机数法

处理散列冲突

开放地址法

• 线性探测法
• 二次探测法
• 再哈希法

链地址法

图结构

图结构概述

​ 图(Graph)是一种数据结构，其中顶点(Vertex)可以具有零个或多个相邻元素。两个顶点之间的连接称为边(Edge)。

表示方法

邻接矩阵

• 邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于 n 个顶点的图而言，矩阵是的 row 和 col表示的是1…n 个点。

上图用邻接矩阵表示为：

1 1 1 0 0
1 1 1 1 1
1 1 1 0 0
0 1 0 1 0
0 1 0 0 1

邻接表

• 邻接矩阵需要为每个顶点都分配 n个边的空间，其实有很多边都是不存在,会造成空间的一定损失

• 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，

  邻接表由数组+链表组成

  • 数组的索引代表顶点
  • 链表中元素的值代表与该顶点相连的顶点的值

上图用邻接表表示为：

图的遍历

深度优先遍历(DFS)

• 深度优先遍历，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，访问它的第一个邻接节点，可以这样理解：每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。
• 这样的访问策略是优先往纵向挖掘深入
• 深度优先搜索是一个递归的过程

思路

• 访问初始节点v，并标记节点v为已访问
• 查找节点v的第一个邻接节点w
• 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个节点继续
• 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）
• 查找节点v的w邻接节点的下一个邻接节点，转到步骤 3

广度优先遍历(BFS)

• 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

思路

• 访问初始结点 v并标记结点 v为已访问
• 结点v入队列
• 当队列非空时，继续执行，否则算法结束
• 出队列，取得队头结点u
• 查找结点 u的第一个邻接结点 w。
• 若结点 u的邻接结点 w不存在，则转到步骤 3；否则循环执行以下三个步骤：
  • 若结点 w尚未被访问，则访问结点 w并标记为已访问
  • 结点 w入队列
  • 查找结点 u的继 w邻接结点后的下一个邻接结点 w，转到步骤6

代码实现

demo14.util.Graph.java

import demo02.util.MyStack;

public class Graph {
    private Vertex[] vertices; // 顶点数组
    private int currentSize; // 图的大小
    public int[][] adjMat; // 图的邻接矩阵

    public Graph(int size) {
        this.vertices = new Vertex[size];;
        this.adjMat = new int[size][size];
    }

    // 加入顶点
    public void addVertex(Vertex v) {
        if (currentSize >= vertices.length) return;
        adjMat[currentSize][currentSize] = 1;
        vertices[currentSize++] = v;
    }

    // 加入边
    public void addEdge(String vertexVal1, String vertexVal2) {
        int idx1 = -1, idx2 = -1;
        for (int i = 0; i < currentSize; i++) {
            if (vertices[i].getValue().equals(vertexVal1)) {
                idx1 = i;
            }
            if (vertices[i].getValue().equals(vertexVal2)) {
                idx2 = i;
            }
            if (idx1 != -1 && idx2 != -1) {
                break;
            }
        }
        if (idx1 == -1 || idx2 == -1) return;

        adjMat[idx1][idx2] = 1;
        adjMat[idx2][idx1] = 1;
    }

    // 深度优先搜索算法
    public void dfs() {
        // 栈用来存放当前遍历到的索引
        MyStack myStack = new MyStack();
        // 当前遍历到的索引，用来存栈顶元素
        int currIdx = 0;
        // 第一次栈中没存值，所以用do...while循环先运行第一次
        do {
            // 对在顶点数组中当前顶点之后的元素进行遍历
            for (int i = currIdx; i < currentSize; i++) {
                // 如果和下一个遍历的顶点邻接且下一个遍历的顶点未被遍历出来过
                if (adjMat[currIdx][i] == 1 && !vertices[i].visited) {
                    // 输出
                    System.out.println(vertices[currIdx].getValue() + "->" + vertices[i].getValue());
                    // 把当前索引设置为下一个遍历的顶点的索引
                    currIdx = i;
                    // 把下一个遍历的顶点的索引压入栈中
                    myStack.push(currIdx);
                    // 设置下一个遍历的顶点为已访问状态
                    vertices[currIdx].visited = true;
                }
            }
            // 弹出栈顶元素
            myStack.pop();
            if (!myStack.isEmpty()) {
                // 设置当前指针为栈顶存的索引
                currIdx = (int)myStack.peek();
            }
            // 栈不为空时进行循环
        } while (!myStack.isEmpty());
    }
}

demo14.util.Vertex.java

/**
 * 顶点类
 */
public class Vertex {
    private String value;
    public boolean visited;

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public Vertex(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value;
    }
}

有向图

带权图