夯实基础，常考的数据结构 5 类经典算法

---

常见的算法

算法，通俗来讲，它是计算机通过一个固定的运算过程，将各类数据结构进行运算操作，得值的一种方法。算法也是程序员一定不能忽视的技能点。

这里将引入一些著名的算法进行介绍，每一个都是经典，值得收藏。

排序算法（数组）

排序算法可能是最基础、最适合算法入门的经典算法，在面试中经常会问到排序算法及其相关的问题。有时会要求现场手写基本的排序算法。熟练掌握排序算法思想及其特点并能够熟练地手写代码至关重要。

我们经常会看到这样的文章标题，诸如：《十大经典排序算法详解》、《八大排序算法总结》，的确，排序算法有很多：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序。

很明显这里不打算一一陈述，只讲其中最重点的 2 种排序方法，也是面试种被问过最多次的，它们是：冒泡排序和快速排序。

• 冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法描述为：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复上述步骤，直到排序完成。

java 实现：

public static void bubbleSort(int[] arr) {
    int temp = 0;
    for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度
        for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }//loop j
    }//loop i
}// method bubbleSort

• 快速排序

快速排序是一个知名度极高的排序算法，其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。

算法描述为：从数列中挑出一个元素，称为"基准"，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作。然后再递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

java 实现：

public static void quickSort(int[] arr){
    qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
    if (low >= high)
        return;
    int pivot = partition(arr, low, high);        //将数组分为两部分
    qsort(arr, low, pivot-1);                   //递归排序左子数组
    qsort(arr, pivot+1, high);                  //递归排序右子数组
}
private static int partition(int[] arr, int low, int high){
    int pivot = arr[low];     //基准
    while (low < high){
        while (low < high && arr[high] >= pivot) --high;
        arr[low]=arr[high];             //交换比基准大的记录到左端
        while (low < high && arr[low] <= pivot) ++low;
        arr[high] = arr[low];           //交换比基准小的记录到右端
    }
    //扫描完成，基准到位
    arr[low] = pivot;
    //返回的是基准的位置
    return low;
}

快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。

二分查找（数组）

除了排序算法，二分查找也是算法中的基础经典面试题。它是一种查找算法，适用于在已经排好序的数组中找到一个特定的值。

算法思路是：找到数组的中间元素坐标并记录，将需要查找的元素跟中间元素进行比较，如果大于中间元素，则截取中间元素以后的所有元素作为新的数组，将中间元素设为新数组的起始元素，如果小于中间元素，则截取中间元素以前的所有元素作为新的数组。

然后再在新的数组中找到中间元素，继续进行比较，如果中间元素等于目标值则返回输出。

java 实现：

public static int binarySearch(int[] arr, int value) {
        int min = 0;
        int max = arr.length - 1;
        while (min <= max) {
            int mid = (max + min) >>1;
            if (arr[mid] == value) {
                return mid;
            }
            if (value < arr[mid]) {
                max = mid - 1;
            }
            if (value > arr[mid]) {
                min = mid + 1;
            }
        }
        return -1;
    }

二分法的效率高，而且也比较便捷，用起来更方便~

DFS 和 BFS（树/图）

深度优先遍历（简称 DFS）与广度优先遍历（简称 BFS）是图论中两种非常重要的算法，生产上广泛用于拓扑排序，寻路（走迷宫），搜索引擎，爬虫等，也频繁出现在 leetcode，高频面试题中。

也广泛应用在树这类数据结构的遍历场景，从根本上来讲，树也是一种特殊的图，连通无环的图就是树。

• 深度优先遍历

深度优先遍历主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底，不断递归重复此过程，直到所有的顶点都遍历完 成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

在上图中，遍历过程将是：第一次遍历（节点 1、2、5、9） 第二次遍历（3、6、10）、第三次遍历（7）、第四次遍历（4、8）

深度优先遍历有递归和非递归两种方式，此处给出递归的 java 代码示例：

public class Solution {
    private static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    public static void dfs(Node treeNode) {
        if (treeNode == null) {
            return;
        }
        // 遍历节点
        process(treeNode)
        // 遍历左节点
        dfs(treeNode.left);
        // 遍历右节点
        dfs(treeNode.right);
    }
}

递归的表达性很好，也很容易理解，不过如果层级过深，很容易导致栈溢出。

思考：你知道非递归的怎么写吗？提示是用栈实现。

• 广度优先遍历

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。

广度优先遍历也叫层序遍历，同样的，在上图所示的树中，先遍历第一层（节点 1），再遍历第二层（节点 2、3、4），第三层（5、6、7、8），第四层（9、10）。

广度优先遍历可以用队列实现，java 代码如下：

/**
 * 使用队列实现 bfs
 * @param root
 */
private static void bfs(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> stack = new LinkedList<>();
    stack.add(root);

    while (!stack.isEmpty()) {
        Node node = stack.poll();
        System.out.println("value = " + node.value);
        Node left = node.left;
        if (left != null) {
            stack.add(left);
        }
        Node right = node.right;
        if (right != null) {
            stack.add(right);
        }
    }
}

小结：DFS 和 BFS 是非常重要的两种算法，大家一定要掌握，本文为了方便讲解，只对树做了 DFS，BFS，大家可以试试如果用图的话该怎么写代码，原理其实也是一样，只不过图和树两者的表示形式不同而已，DFS 一般是解决连通性问题，而 BFS 一般是解决最短路径问题。

狄克斯特拉算法（图）

狄克斯特拉（Dijkstra）算法是非常著名的算法，是改变世界的十大算法之一，是典型最短路径算法，计算一个起始节点到路径中其他所有节点的最短路径的算法和思想。在一些专业课程中如数据结构，图论，运筹学等都有介绍。其思想是一种基础的求最短路径的算法，通过基础思想的变化可以解决很多复杂问题，如导航线路，动态规划等。

举个例子：在下图中，以 A 点为顶点，求到其他点的最短路径。

思路是：每次从“未求出最短路径”的点中 取出“距离距离起点”最小路径的点，以这个点为桥梁刷新“求出最短路径的点”的距离。

比如 A 点到 B 点距离为 2，A 点到 D 点的距离为 6，A 点到 C 点的距离未知，所以以 B 点为桥梁，再去计算刷新距离。

B 点到 C 点，距离为3；B 到 D 点距离为 2 ，通过计算 A 以 B 为桥梁，A 到 B 再到 D 的距离为 4 ，比 A 直接到 D 的距离 6 更短，刷新原有值；

同时，更新桥梁点 D 点，因为 B 到 D 比 B 到 C 要更近，依次经过 A、B、D、C 距离为 6 ，大于原来依次经过的 A、B、C 的距离 5，不用刷新原值，即 A 到 C 最近为 5；

以上即全部思路：最终结果 A 到 B 最近为 2；A 到 D 最近为 4；A 到 C 最近为 5；

java 代码实现：

public class Dijkstra {
    public static int[] dijkstra(int[][] graph,int startVertex){
        //初始化 以求出最短路径的点 result[]
        int length = graph.length;
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = -1;
        }
        result[startVertex] = 0 ;
        // 初始化 未求出最短路径的点 notFound[]
        int[] notFound = new int[length];
        for (int i = 0; i < length; i++) {
            notFound[i] = graph[startVertex][i];
        }
        notFound[startVertex] = -1;
        // 开始 Dijkstra 算法
        for (int i = 1; i < length; i++) {
            //1. 从「未求出最短路径的点」notFound 中取出 最短路径的点
            //1.1 找到最短距离的点
            int min = Integer.MAX_VALUE;
            int minIndex = 0;
            for (int j = 0; j < length; j++) {
                if (notFound[j] > 0 && notFound[j] < min){
                    min = notFound[j];
                    minIndex = j;
                }
            }
            //1.2 将最短距离的点 取出 放入结果中
            result[minIndex] = min;
            notFound[minIndex] = -1;
            //2. 刷新 「未求出最短距离的点」 notFound[] 中的距离
            //2.1 遍历刚刚找到最短距离的点 (B) 的出度 (BA、BB、BC、BD)
            for (int j = 0; j < length; j++) {
                // 出度可通行(例如 BD:graph[1][3]  > 0)
                // 出度点不能已经在结果集 result中(例如 D: result[3] == -1)
                if (graph[minIndex][j] > 0
                && result[j] == -1){
                    int newDistance = result[minIndex] + graph[minIndex][j];
                    //通过 B 为桥梁，刷新距离
                    //（比如`AD = 6 < AB + BD = 4` 就刷新距离）（ -1 代表无限大）
                    if (newDistance < notFound[j] || notFound[j]==-1){
                        notFound[j] = newDistance;
                    }
                }
            }

        }
        return result;
    }

狄克斯特拉算法值得每个关注数据结构算法的程序员重点关注。

LRU（哈希）

LRU 算法是一种缓存淘汰算法，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”，所以将其保存。反之就意味着，如果数据最近最少被访问，就优先被清除。

一般来讲，LRU 将访问数据的顺序或时间和数据本身维护在一个容器当中。

当访问一个数据时：该数据不在容器当中，则设置该数据的优先级为最高并放入容器中。该数据在容器当中，则更新该数据的优先级至最高。当数据的总量达到上限后，则移除容器中优先级最低的数据。

在 java 中可以直接根据 JDK 给我们提供的 LinkedHashMap 直接实现 LRU。有兴趣自行了解 LinkedHashMap 底层原理。

public class LRUCache extends LinkedHashMap {
    private int capacity;
    public LRUCache(int capacity) {
        // accessOrder 设为 true
        super(16, 0.75f, true); 
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return super.size() >= capacity;
    }
}

虽然上面这些算法有些看来略显晦涩，但是实实在在应用在我们程序世界的每一处，每一个起到了独当一面的作用。值得我们在学习数据结构中，关注这些经典算法。

---