数据结构与基础算法

前言

　本篇文章涵盖内容比较多，包括数组、链表、栈、队列、树（二叉树，平衡二叉树，红黑树，B/B+树）、堆、图论、字符串等数据结构及其相关的基础算法。初学者可以慢慢渗入，进行系统性学习，已经学过的也可以用来回顾一遍。

1. 数据结构

​ 数据结构（data structure）可分为三部分内容：

• 逻辑结构
• 存储结构
• 数据运算

逻辑结构

​ 指反映数据元素之间逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后关系，与他们在计算机中的存储位置无关。逻辑结构有四种：

1. 集合结构：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
2. 线性结构：数据结构中的元素存在一对一的相互关系。
3. 树形结构：数据结构中的元素存在一对多的相互关系；
4. 图形结构：数据结构中的元素存在多对多的相互关系。

存储结构

​ 数据的逻辑结构在计算机存储空间（内存、磁盘）中的物理存放形式称为数据的存储结构。一般来说，一种数据结构的逻辑结构根据需要可以有多种存储结构。

​ 常用的存储结构有顺序存储，链式存储，散列存储，索引存储。

​ 逻辑结构是面向问题的，而物理结构是面向计算机的。

2. 算法

算法的定义：

​ 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

​ 算法定义中，提到了指令，指令能被人或机器等计算装置所执行。它可以是计算机指令，也可以是我们平时的语言文字。也就是说算法不是计算机领域特有的事物和名词，而是存在于数学中，不仅应用于计算机，还应用于其他领域。

特征

算法有五大基本特征：输入项，输出项，有穷性，确定性和可行性。

输入项：

​ 一个算法有0个或多个输入，以确定运算的初始情况。（0输入是指算法本身指定了默认条件）

输出项：

​ 一个算法有1个或多个输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的。

有穷性：

​ 算法必须能在有限个执行步骤之后终止。

确定性：

​ 算法的每一个计算步骤必须有确切的含义。不会出现二义性。

可行性：

​ 算法的每一个计算步骤都要在有限时间内完成。

设计要求

​ 同一个问题可用不同的算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

正确性

​ 算法的正确性是评价一个算法优劣最重要的标准。

健壮性

​ 健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。

时间复杂度

​ 算法的时间复杂度是指执行算法所需要的计算工作量。从宏观的角度分析，时间复杂度高的算法执行时间确实长，但时间复杂度分析的衡量标准却不是计算耗时，而是计算次数。

空间复杂度

​ 算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

可读性

​ 算法的可读性是指一个算法可供人们阅读的容易程度。

渐进分析

大O表示法：我们使用大O表示法来表示渐进时间复杂度。

使用大O表示法推导时间复杂度：

1. 如果运行时间是常数量级，用常数1表示。
2. 只保留时间函数中的最高阶项。
3. 如果最高阶项存在，则省去最高阶项前面的系数。

常见的时间复杂度

级别	时间复杂度	典型场景	举例
常数级	O（1）	数组查询元素	…
对数级	O（logn）	二分策略	二分查找
线性级	O（n）	单层循环	找出指定元素
常数对数级	O（n logn）	分治算法	归并排序
平方级	O（n^2^）	双层循环	检查所有元素对
立方级	O（n^3^）	三层循环	检查所有三元组
指数级	O（2^n^）	穷举查找	检查所有子集

另外还有阶乘级别 O（n!）和O（m*n）。

常用时间复杂度所消耗时间（函数的线性增长）从小到大依次是：

O（1）< O（logn）< O（n）< O（nlogn）< O（n^2^）< O（n^3^）< O（2^n^）<（n!）

​ 注意，前5种时间复杂度是最常用的，也是程序可以接受的一个正常范围。而像立方级O（n^3^），过大的n都会使得运行结果变得不现实，不能接受；同样指数级 O（2^n^）和阶乘级 O（n!），除非是很小的n值，否则哪怕 n 只是100，那都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度，一般我们都不去讨论它。

最坏情况与平均情况

​ 算法的最坏情况和平均情况是很重要的两个指标。

​ 最坏情况运行时间是一种保证，最坏也就这个样了，不可能再坏了。在应用中，这是一种最重要的需求。通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

​ 平均运行时间是所有情况中最有意义的。因为它是期望的运行时间，是最接近算法实际运行情况的一种描述。

原地算法

​ 在计算机科学中，原地算法（in-place algorithm）是不需要额外的数据结构就能变换输入数据的算法。不过，分配少量空间给部分辅助变量是被允许的。算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。

​ 不满足原地算法规则的就是非原地算法（out-place algorithm）。

算法设计思想

穷举法是最直接，最容易理解的算法，同样也是效率最低的算法。

迭代和递归属于解决问题的两种具体实现方式。

​ 在很多高校里，《算法设计与分析》被划分为一门单独的课程教授，因为算法的设计和分析其实不是简单的课程，内容也不少，本文不对算法设计与分析相关的内容做过多讲解。

3. 线性表

​ 线性表是最基本、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。

​ 线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

​ 注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点。

数组和链表

数组

顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。通常我们都是用数组来实现这一结构。

单向链表

顺序存储结构的查询操作可以在常数时间O（1）内完成，但是插入和删除操作却不方便，链式存储结构可以解决这一问题。

实现链表的第一步就是定义节点：(下面为单向链表的节点)

private static class Node<E>{
      E element;
      Node next;

      public Node() {
          
      }
      public Node(E element, Node next) {
          this.element = element;
          this.next = next;
      }
  }

双向链表

​ 如果要找某结点的前驱结点，单链表只能是遍历整个链表，时间复杂度高，效率低。为解决这类问题，在单链表的基础上，给各节点额外增加一个指向前驱节点的指针，这就是双向链表。

private static class Node<E>{
        E element;
        Node prev;
        Node next;

        public Node() {

        }
        public Node(Node prev,E element, Node next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
    }

java.util中的LinkedList 就是双向链表的实现。

循环链表

​ 循环链表分为单循环链表和双循环链表。

​ 以单循环链表为例，单循环链表比单向链表多了一个头结点，循环链表的尾节点的指针指向头结点，头结点的指针指向第一个数据节点，整个链表形成一个环。

头结点

​ 数据结构中，在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点。头结点是链表中的第一个结点，他的数据域可以不存放任何信息，他的指针区域存放的是链表中第一个数据元素的结点的地址。

例题：在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p→next→next=head,则：指针P的直接后继是尾结点。

证明指针的直接后继是尾结点：

• 已知 p→next→next=head。在单循环链表中，尾结点的特点是其下一个结点是头结点。
• 因为 p→next→next=head，这就表明 p→next 这个结点的下一个结点是头结点，符合尾结点的定义。
• 所以可以得出结论：指针的直接后继是尾结点。

静态链表

​ 链表可以分为静态链表和动态链表。静态链表是一种在程序中预先定义所有节点的链表。这些节点不是在程序运行时动态创建的，而是在程序编译时就已经确定。静态链表的特点如下：

1. 顺序存储：静态链表的节点在物理地址上是连续的，类似于数组的存储方式。
2. 空间固定：静态链表的长度通常是固定的，因为需要在编译时预先分配地址空间。
3. 插入和删除操作简便：在静态链表中插入和删除节点时，不需要移动其他节点，只需修改指针即可。
4. 适用场景：静态链表适用于元素数量已知且不经常变动的场景。

栈和队列

栈和队列是计算机科学中应用非常广泛的两种数据结构 。

栈和队列都是运算受限的线性表。栈和队列的共同点是只允许在端点处插入和删除元素。

栈和队列都可以用数组和链表分别实现。

栈 Stack

数据的新增和删除运算被限定在表的某一端，这一端叫栈顶，另一端叫栈底， 栈是后进先出的数据结构。

抽象数据类型

行为	描述
Sotck();	初始化一个空栈
void push(E element);	入栈
E pop();	出栈并返回栈顶元素
E getTop();	仅返回栈顶元素
int size();	返回元素数量
boolean isEmpty();	是否为空
void clearStock();	清空栈

具体实现

public class MyStock<E> {

    private Node frist;
    private int size;

    /**
     * 压栈
     * @param element
     */
    public void push(E element){
        Node oldNode = frist;
        frist = new Node(element,oldNode);
        size++;
    }

    /**
     * 出栈
     * @return
     */
    public E pop(){
        if (size==0) return null;
        Node oldNode = frist;
        frist = frist.next;
        size--;
        return oldNode.element;
    }

    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return frist == null;
    }
}

应用

​ 栈和递归都具有回溯的特性，函数的嵌套调用和程序的递归处理都是用栈来实现的。

队列 Queue

数据的添加和删除操作分别限制在两端，只能在队尾添加元素（入队），在队首删除元素（出队）。

队列是先进先出的数据结构（First In First Out，FIFO）。

实现方式

队列有两种实现方式：

• 基于链表实现
• 基于数组实现

基于数组实现队列

​ 在数组中删除首元素的时间复杂度为 𝑂(𝑛) ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方 法来避免这个问题。 我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

​ 基于此设计，数组中包含元素的有效区间为 [front, rear - 1]，各种操作的实现方法如图 5‑6 所示。 ‧

• 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。 ‧
• 出队操作：只需将 front 增加 1 ，并将 size 减少 1 。

可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 𝑂(1) 。

​ 你可能会发现一个问题：在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾 部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。 对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律 可以通过“取余操作”来实现，代码如下所示：

/* 基于环形数组实现的队列 */
class ArrayQueue {
    private int[] nums; // 用于存储队列元素的数组
    private int front; // 队首指针，指向队首元素
    private int queSize; // 队列长度

    public ArrayQueue(int capacity) {
        nums = new int[capacity];
        front = queSize = 0;
    }

    /* 入队 */
    public void push(int num) {
        if (queSize == capacity()) {
            System.out.println(" 队列已满");
            return;
        }
        // 计算队尾指针，指向队尾索引 + 1
        // 通过取余操作实现 rear 越过数组尾部后回到头部
        int rear = (front + queSize) % capacity();
        // 将 num 添加至队尾
        nums[rear] = num;
        queSize++;
    }

    /* 出队 */
    public int pop() {
        int num = peek();
        // 队首指针向后移动一位，若越过尾部，则返回到数组头部
        front = (front + 1) % capacity();
        queSize--;
        return num;
    }

    /* 获取队列的容量 */
    public int capacity() {  return nums.length; }

    /* 获取队列的长度 */
    public int size() {return queSize; }

    /* 判断队列是否为空 */
    public boolean isEmpty() { return queSize == 0;}
    
    /* 访问队首元素 */
    public int peek() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return nums[front];
    }

    /* 返回数组 */
    public int[] toArray() {
        // 仅转换有效长度范围内的列表元素
        int[] res = new int[queSize];
        for (int i = 0, j = front; i < queSize; i++, j++) {
            res[i] = nums[j % capacity()];
        }
        return res;
    }
}

例题：

​ 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为：front = (front + 1) % m 。

普通队列

只能在队尾添加元素（入队），在队首删除元素（出队）。

基于链表的具体实现

public class MyQueue<E> {

    private Node frist;
    private Node last;
    private int size;

     /**
     * 入队
     * @param element
     */
    public void enqueue(E element){
        Node oldNode = last;
        last = new Node(element,null);
        if (isEmpty()){
            frist = last;
        }else{
            oldNode.next = last;
        }
        size++;
    }

    /**
     * 出队
     * @return
     */
    public E dequeue(){
        if (size==0) return null;
        Node oldNode = frist;
        frist = frist.next;
        if (isEmpty()) last = null;
        size--;
        return oldNode.element;
    }

    public E getTop(){
        return frist!=null?frist.element:null;
    }

    public E getTail(){
        return last!=null?last.element:null;
    }

    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return frist == null;
    }
}

双端队列

支持同时在两端添加或删除元素。

循环队列

4. 排序

关于排序的术语：

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
• 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
• 内排序：所有排序操作都在内存中完成；
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

排序可分为比较类排序和非比较类排序两类。

极力推荐网站：旧金山大学可视化算法演示 ，上面这些算法都有可视化动画，非常方便理解。

名词解释：

• n: 数据规模
• k: “桶”的个数
• In-place: 原地算法：不占用额外内存（或占用少量常数内存）
• Out-place: 非原地算法：占用额外内存

性能不受输入数据的影响：

• 选择排序
• 归并排序

选择排序

思路

​ 选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

动画演示

代码实现

public static int[] selectionSort(int[] array) {
    if (array.length == 0)
        return array;
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i; j < array.length; j++) {
            if (array[j] < array[minIndex]) //找到最小的数
                minIndex = j; //将最小数的索引保存
        }
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
    return array;
}

算法分析

• 最佳情况：T(n) = O(n^2^)
• 最差情况：T(n) = O(n^2^)
• 平均情况：T(n) = O(n^2^)
• 不稳定

注：在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的就是直接选择排序。

插入排序

思路

​ 插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排过序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

动画演示

代码实现

public static int[] insertionSort(int[] array) {
    if (array.length == 0)
        return array;
    int current;
    for (int i = 0; i < array.length - 1; i++) {
        current = array[i + 1];
        int preIndex = i;
        while (preIndex >= 0 && current < array[preIndex]) {
            array[preIndex + 1] = array[preIndex];
            preIndex--;
        }
        array[preIndex + 1] = current;
    }
    return array;
}

算法分析

• 最差情况：T(n) = O(n^2^)
• 平均情况：T(n) = O(n^2^)
• 最佳情况：T(n) = O(n)
• 稳定

希尔排序

思路

​ 希尔排序是希尔（Shell Sort）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2^）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

​ 希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰被分成一组，算法便终止。

基本步骤

​ 首先我们选择第一个增量 gap = length/2，后面缩小增量继续以 gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

动画演示

代码实现

public static int[] ShellSort(int[] array) {
    int len = array.length;
    int temp, gap = len / 2;   //声明第一个增量gap
    while (gap > 0) {
        for (int i = gap; i < len; i++) {
            temp = array[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > temp) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = temp;
        } 
        gap /= 2;  //每次增量进行递减
    }
    return array;
}

算法分析

• 最差情况：T(n) = O(n logn)
• 平均情况：T(n) = O(n logn)
• 最佳情况：T(n) = O(n logn)
• 不稳定

冒泡排序

​ 冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

思路

每循环一次，找出最大的一个元素，相邻的两个元素进行比较。

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

动画演示

代码实现

public static int[] bubbleSort(int[] array) {
    if (array.length == 0)
        return array;
    for (int i = 0; i < array.length; i++)
        for (int j = 0; j < array.length - 1 - i; j++) //最后的是最大的，不需要再遍历
            if (array[j + 1] < array[j]) { //如果顺序不对就交换
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
    return array;
}

算法分析

• 最差情况：T(n) = O(n^2^)
• 平均情况：T(n) = O(n^2^)
• 最佳情况：T(n) = O(n)
• 稳定

归并排序

​ 和选择排序一样，归并排序（Merge Sort）的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n logn）的时间复杂度。代价是需要额外的内存空间。

​ 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

思路

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

动画演示

代码实现

public static int[] MergeSort(int[] array) {
    if (array.length < 2) return array;
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    return merge(MergeSort(left), MergeSort(right));
}
/**
 * 合并：将两个排序好的数组合并成一个有序数组
 */
public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    for (int index = 0, i = 0, j = 0; index < result.length; index++) {
        if (i >= left.length)
            result[index] = right[j++];
        else if (j >= right.length)
            result[index] = left[i++];
        else if (left[i] > right[j])
            result[index] = right[j++];
        else
            result[index] = left[i++];
    }
    return result;
}

算法分析

• 最差情况：T(n) = O(n logn)
• 平均情况：T(n) = O(n logn)
• 最佳情况：T(n) = O(n)
• 稳定

快速排序

快速排序（Quick Sort）是一种分而治之思想在排序算法上的典型应用。

思路

步骤：

1. 第一次循环开始，选择一个基准元素，理论上可以选任意一个
2. 声明左右两个指针，右指针从右往左开始遍历每个元素，右指针指向的元素应该大于基准元素，如果一直符合预期，右指针应该一直往中间移动；直到不符合预期的情况出现，此时右指针停止移动，开始移动左指针；
3. 左指针从左往右开始遍历每个元素，左指针指向的元素应该小于基准元素，如果一直符合预期，左指针应该一直往中间移动；直到不符合预期的情况出现，此时左指针停止移动；
4. 在左右指针并没有重合的情况下，左右两个指针的元素进行互换，保证小元素在左边，大元素在右边。
5. 如果左右指针重合，将基准元素与重合指针指向的元素互换位置（此时基准元素的最终该位置就确定了），并返回重合的位置下标，本次循环结束。
6. 使用分治法重复步骤1~5；

动画演示

如下图，选择第一个元素为基准pivot，i 和 j分别表示左指针和右指针，两个指针分别往中间移动，直到重合，本次循环结束。

代码实现

public static void quickSort(int[] arr,int left,int right){
       if (left >= right) return;
       int index = partition(arr,left,right);
       quickSort(arr,left,index-1);
       quickSort(arr,index+1,right);
   }
/**
    * 分治(双边循环)
       返回左右指针重合的位置下标
    */
   private static int partition(int[] arr,int startIndex,int endIndex){
       int pivot = arr[startIndex]; //选择基准元素
       int left = startIndex;   //声明左右两个指针，分别向中间靠拢
       int right = endIndex;
       while (left < right){
           while (left < right && arr[right]>pivot) right--;
           while (left < right && arr[left] <= pivot) left++;
           if (left < right) {  //交换数组内两个元素
               int p = arr[right];
               arr[right] = arr[left];
               arr[left] = p;
           }
       }
       arr[startIndex] = arr[left];
       arr[left] = pivot;
       return left;
   }

算法分析

• 最差情况：T(n) = O(n^2^)
• 平均情况：T(n) = O(n logn)
• 最佳情况：T(n) = O(n logn)
• 不稳定

​ 在分治法的思想下，原数组每一轮都会被拆成两部分，每一部分在下一轮有被拆成两部分，直到不可分为止。所以外循环要循环 logn次；而里面的循环需要比较N 次，所以快速排序的平均时间复杂度是**O(N logn)**，

​ 快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平均期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

堆排序

​ 堆排序（Heap sort）是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

代码实现

算法分析

• 最差情况：T(n) = O(n^2^)
• 平均情况：T(n) = O(n logn)
• 最佳情况：T(n) = O(n logn)
• 不稳定

计数排序

​ 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

​ 计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

桶排序

​ 桶排序（Bucket sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

​ 桶排序工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。

基数排序

基数排序有两种思路：

• 低位优先排序（推荐，常用）
• 高位优先排序

5. 查找

符号表

​ 符号表也叫字典，符号表最主要的目的就是将一个键（Key）和一个值（Value）对应联系起来。

​ 符号表是一种存储键值对的数据结构。从符号表的所有键值对中可以根据键直接找到对应的值。

应用

应用	查找的目的	键
字典	查询单词释义	单词
图书索引	找出相关的页码	术语
编译器	找出符号的类型和值	变量名

要求

1. 每个键只对应一个值（不允许存在重复的键）；
2. 当存入重复的键时，新值会替代旧值；

API

一种简单的泛型符号表API

/**
 * 简单泛型符号表API
 */
public class SymbolTable<K,V> {

    SymbolTable();

    void put(K key,V value);

    V get(K key);

    void delete(K key);

    boolean contains(K key);

    boolean isEmpty(K key);

    int size();					//表中键值对的数量

    Iterable<K> keys();			//表中所有键的集合
}

一种有序泛型符号表的API

/**
 * 有序泛型符号表API
 */
public class SymbolTable<K extends Comparable<K>,V> {

    SymbolTable();

    void put(K key,V value);

    V get(K key);

    void delete(K key);

    boolean contains(K key);

    boolean isEmpty(K key);

    int size();

    Iterable<K> keys();		//表中所有键的集合(已排序)
    
    K minKey();			//最小键
    
    K maxKey();			//最大键
    
    K floor(K key);		//小于等于key的最大键
    
    K ceiling(K key);	//大于等于key的最小键
    
    int rank(K key);	//排名(即小于key的数量)
    
    K select(int rank);	//排名为k的键
    
    Iterable<K> keys(Key low,Key high);		//[low,high]范围的所有键(已排序)
    
    int size(Key low,Key high);				//[low,high]范围的所有键的数量
    
}

​ 有序泛型符合表的API相比简单符号表的API，多了有序性相关的操作，如取最大键，最小键，向下取最大值，向上取最小值，排名和选择，范围查找。

实现

符号表的实现有多种，可以是链表，数组，树，散列表，可以无序的，也可以是有序的。

符号表各种实现的优缺点

数据结构	优点	缺点
链表	适用于小型问题	中大型数据量不适用，插入、删除和查找效率低。
有序数组	查找效率高（二分查找） 能够进行有序性相关的操作	插入、删除效率低
二叉查找树	实现简单 能够进行有序性相关的操作	没有性能上界的保证 链接需要额外的空间
平衡二叉查找树	最优的查找和插入效率 能够进行有序性相关的操作	保持平衡需要额外运算，平衡度越高越耗时 链接需要额外的空间
散列表	能够快速插入和查找	需要计算数据的hash值 无法进行有序性相关的操作 链接需要额外的空间

下面将会依次详解符号表的几种实现。

无序链表的顺序查找

符号表中使用的数据结构，一个简单的选择是链表。每个节点存储一个键值对。

//定义包含键值对的链表节点
 private class Node{
        K key;
        V value;
        Node next;

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

​ 符号表的实现使用了一个私有内部 Node 类来在链表中保存键值对。get() 的实现会顺序遍历链表中所有的节点，时间复杂度为O（n）；put() 的实现也会顺序遍历链表中所有的节点，如果找到则更新相关联的值，否则新增节点保存键值对，时间复杂度为O（n），delete() 方法也是同样的道理。

总结：基于链表的实现以及顺序查找是非常低效的。

有序数组的二分查找

​ 基于有序数组实现的符号表，用两个数组保存键和值。因为是有序数组，所以可以使用二分查找算法，查询效率是对数级别，非常优秀。但是插入和删除操作的效率不尽人意，需要后面的数组元素全部依次后移一位。

​ 使用二分查找的前提必须是有序的数组。

/**
 * 有序数组的二分查找算法
 */
public class BinarySearch<K extends Comparable<K>,V> {

    private K [] keys;
    private V [] values;
    private int N;

    public BinarySearch(int capacity) {
        keys = (K [])new Comparable [capacity];
        values = (V [])new Object [capacity];
    }

    public V get(K key){
        if (isEmpty()) return null;
        int rank = rank(key);
        if (rank<N && keys[rank].compareTo(key)==0){
            return values[rank];
        }else{
            return null;
        }
    }

    public int rank(K key){

        int low=0;
        int high=N-1;
        int mid;
        while (low<=high){
            mid=low+(high-low)/2;
            int i = keys[mid].compareTo(key);
            if (i<0) high=mid-1;
            else if(i>0) low=mid+1;
            else return mid;
        }
        return low;
    }

    public void put(K key,V value){

        int rank = rank(key);
        if (rank<N && keys[rank].compareTo(key)==0){
            values[rank] = value;
            return;
        }
        if(N==keys.length-1){
            growArrayCapacity();
        }
        for (int i = N; i > rank ; i--) {
            keys[i] = keys[i-1];
            values[i] = values[i-1];
        }
        keys[rank] = key;
        values[rank] = value;
        N++;
    }
    public int size(){
        return N;
    }
    public boolean isEmpty(){
        return N==0;
    }

    /**
     * 拓展数组容量
     */
    public void growArrayCapacity(){
        //拓展策略可以是增长100%,也可以是增长50%的容量;
    }
}

例题：

有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时，( 4 )次比较后查找成功。

解析：

第一次比较时，M = L + (H-L)/2 = 0+ (12-0)/2 = 6 ; 下标为6 的目标元素为 T= 45 ；L = M+1 = 7；H = 12；

第二次比较时，M = 8，T = 75，L = 9，H =12；

第三次比较时，M = 9，T = 77，L = 10，H =12；

第四次比较时，M = 10，T = 82；此时命中。所以需要4 次比较；

​ 对数级别的算法和数据结构还是非常吸引人的，但是上面两种实现方式，都不能保证查询和插入都保持在对数级别，那到底有没有这样的算法和数据结构可以办到呢？答案是有的！二叉查找树就可以办到。

二叉查找树

二叉查找树是一种将链表插入的灵活性和有序数组查找的高效性结合起来的数据结构。

二叉树

​ 在二叉树中，每个节点只能有一个父节点（根节点除外），和最多两个子节点（左子节点和右子节点）。

二叉查找树

​ 一棵二叉查找树（BST）是一棵二叉树，其中每个节点都含有一个Comparable的键（以及关联的值），且每个节点的键都大于左子节点，小于右子节点。一棵二叉查找树代表了一组键值对的集合。

定义二叉查找树

/**
 * 二叉查找树
 */
public class BST<K extends Comparable<K>,V> {

    private Node root;

    private class Node{
        K key;
        V value;
        Node left,right;
        int N;

        public Node(K key, V value, int n) {
            this.key = key;
            this.value = value;
            N = n;
        }
    }
    public int size(){
        return size(root);
    }
    private int size(Node node){
        if (node==null) return 0;
        else return node.N;
    }
}

​ 树由Node对象组成。每个对象都含有一对键值，两条链接和一个节点计数器N。

​ 每个Node对象都是一棵含有N个节点的子树的根节点。它的左链接指向一棵由小于该节点的所有键组成的二叉查找树，右链接指向一棵由大于该节点的所有键组成的二叉查找树。root变量指向二叉查找树的根节点。

查找

public V get(K key){
    return get(root,key);
}
/**
 * 从该节点往下查找Key
 */
private V get(Node node,K key){
    if (node==null) return null;
    int i = node.key.compareTo(key);
    if (i<0)  return get(node.left,key);
    else if (i>0) return get(node.right,key);
    else return node.value;
}

插入

public void put(K key,V value){
     if (key==null)  throw new IllegalArgumentException("key can't be null!");
     root = put(root,key,value);
 }

 private Node put(Node node,K key,V value){
     if (node==null) return new Node(key,value,1);
     int i = key.compareTo(node.key);
     if (i<0)  node.left = put(node.left,key,value);
     else if (i>0) node.right = put(node.right,key,value);
     else  node.value = value;
     node.N = size(node.left)+size(node.right) + 1;
     return node;
 }

查找和插入操作均使用递归来实现的。

有序性相关的操作

​ 最大键，最小键，向下取最大值，向上取最小值，排名和选择，范围查找。

删除

​ 二叉查找树中最难实现的就是删除delete()操作了。

​

平衡查找树

AVL树

​ 在计算机科学中，AVL树是最先发明的自平衡二叉查找树。AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要一次或多次旋转来重新平衡这个树。

​ AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文中发表了它。

旋转

高度平衡的劣势：

​ 虽然高度平衡的二叉查找树可以提供非常优秀的对数级别的运行时间，但在动态插入中保持树的完整平衡状态的代价太高了，维护这种高度平衡所付出的代价比从中获得的效率收益还大，所以高度平衡的AVL树的应用场景并不是很多，它适用于一旦初始化数据后插入删除的操作很少而查询很多的应用场景。

2-3树

红黑树

红黑树是一棵平衡二叉查找树。

2-3树种，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。

散列表

散列表也叫哈希表，这种数据结构提供了 Key-Value (键值对)的映射关系，并保证很好的读写效率。

Hash算法

​ 说到散列表必须先说一下Hash算法，这是实现散列表的核心。Hash算法是将一个数据转换为一个信息摘要，这个信息摘要和源数据的每一个字节都有十分紧密的关系。

​ Hash算法是一个广义的算法，也可以认为是一种思想，Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。

特点

1. Hash 散列算法，顾名思义，对于不同的key值，计算出来的hash值要尽可能散列开来，理想状态下不同的Key值计算出来的hash值不相同。
2. 如果Key 值相同，那么计算出来的hash值一定是相同的。
3. 不同的Key 值，也可能会计算出相同的hash值 （哈希冲突不可避免）。
4. Hash算法还具有一个特点–单向性，就是很难找到逆向规律。

应用

1. 使用Hash算法可以提高存储空间的利用率。
2. 可以提高数据的查询效率。
3. 可以做数字签名来保障数据传递的安全性。

常用Hash算法

MD5

​ 信息摘要算法（Message-Digest Algorithm）

​ 该算法于1992年公开，是对MD4算法的改进版本。可以生成一个128位（16字节）的散列值。

​ 2004年，MD5算法被证实无法防止碰撞攻击，因此不适用于安全性认证。专家一般建议改用其他算法，如SHA-2。

SHA1

​ SHA1（安全散列算法1），美国国家安全局设计，1995年发布。

​ SHA-1可以生成一个160位（20字节）的散列值，散列值通常的呈现形式为40个十六进制数。

​ 2005年，王小云教授等人发表了对完整版SHA-1的碰撞攻击（生日攻击法），谷歌，微软等公司现已放弃对SHA1的支持。

SHA256

​ SHA256（安全散列算法2）是SHA-2下细分出的一种算法。

​ SHA-2，一种密码散列函数算法标准，由美国国家安全局研发，属于SHA算法之一，是SHA-1的后继者。

SHA-2下又可再分为六个不同的算法标准：

​ SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。

这些变体除了生成摘要的长度 、循环运行的次数等一些微小差异外，算法的基本结构是一致的。

​ SHA-256算法的输入是最大长度小于2^64位的消息，输出是256位的消息摘要，输入消息以512位的分组为单位进行处理。

散列表

​ 散列表是散列函数的一个主要应用，使用散列表能够快速的按照关键字Key查找到Value。

​ 在基础的数据结构中，查询效率最高的无疑是数组了， 数组可以在O(1) 时间内查询元素。但是数组只能通过下标来访问 ，像a[0] ，a[1] ，a[2] 这样。
散列表的Key则是以字符串类型为主的数据结构。 散列表底层存储数据的结构还是用数组来实现，把Key 转换成数组下标的”中转站” 就是 哈希函数。

 在散列表中，Hash函数将任意类型的键转换为对应的数组下标。  我们只需要调整散列算法的参数, 就可以在空间和时间之间做出取舍。

​ 哈希冲突是不可避免的, 只能想办法解决冲突. 最常用的方法有两种: 链表法和开放地址法 。

1. 链表法：
   如果出现Hash冲突， 那么就在此数组下标这生成一个链表，存储hash值相同的元素。 此方法也是Java中 HashMap中的解决方法。
2. 开放地址法：
   开放地址法的思路很简单，就是如果出现哈希冲突，算出了相同的hash值， 那么就 “另谋高就” ，再算一个不一样的hash值。 Java中的ThreadLocal 使用的就是 开放地址法。

总结:

1. 散列表可以在接近O(1) 的时间内进行 读操作和写操作。
2. 散列表通过hash函数实现Key和数组下标的转换。
3. 通过开放地址法和链表法解决hash冲突。

经典实现

​ 各语言的函数库中匀有散列表的实现，如java.util工具包中的 HashTable 和 HashMap 。

​ HashTable 就是哈希表的直译，HashTable 继承自Dictionary字典类，这更加直观的说明了哈希表就是一个字典，主要提供键值对之间的映射关系。

HashTable 和 HashMap 又有区别，区别如下：

1. Hashtable是JDK1.1中提供的接口，HashMap是JDK1.2中提供的接口。
2. Hashtable线程安全，HashMap线程非安全。
3. Hashtable不允许键为null值，HashMap允许键为null值。

生日悖论

这里插一个好玩的结论，也是悖论——生日悖论。

首先看一看悖论的定义：

​ 悖论是一种导致矛盾的命题。如果承认它是真的，经过一系列正确的推理，却又得出它是假的；如果承认它是假的，经过一系列正确的推理，却又得出它是真的。

生日悖论

​ 23 个人中至少有两人生日相同的概率大于 50%。 60 个人中，这种概率大于 99%。（详细解法请自行谷歌）

生日悖论的应用

​ 生日悖论普遍的应用于检测哈希函数：N 位长度的哈希表可能发生碰撞测试次数不是 2N 次而是只有 2N/2 次。这一结论被应用到破解密码哈希函数的 “生日攻击” 中。

6. 树

​ 树是 n （n>=0）个结点的有限集。n=0 时称为空树；在任意一棵非空树中，有且只有一个根结点（Root）；线性表是一对一的关系，而树则是一对多的数据关系。

树的相关概念

• 结点拥有的子树个数称为结点的度；

• 度为0的结点称为叶子节点；

• 度不为0的结点称为非叶子节点或分支结点；

二叉树

特点

• 每个结点最多有两个子树。
• 左子树和右子树是有顺序的，次序不能颠倒。

性质

1. 二叉树的第 i 层最多有2^(i-1)^个结点（i>=1）。
2. 深度为k的二叉树最多共有 2^k^ - 1个结点（k>=1）。
3. 对于任意一棵二叉树，如果叶子节点（度为0）个数为n0，则度为2的节点数为 n0-1。
4. 具有n个结点的完全二叉树的深度为 [log2N] +1。

特殊二叉树

满二叉树

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这棵树就是满二叉树。

深度为k的满二叉树共有 2^i^ - 1个结点，如果深度为3，共有7个节点；如果深度为4，共有15个节点；

完全二叉树

​ 完全二叉树是由满二叉树引出来的。对于深度为K，有N个结点的二叉树，当且仅当其一个节点都与深度为K的满二叉树中编号从1~N的结点一一对应时，称之为完全二叉树。

​ 相比满二叉树，完全二叉树的定义稍微有点绕（你品，你细品……多品几次就通透了），如上图，该二叉树的编号从根节点，按照层序遍历的顺序依次编号，为1~12，深度为4，它和深度为4的满二叉树，编号为1-12的结点都一一对应，所以该二叉树为完全二叉树。

完全二叉树特点：

1. 叶子结点只可能出现在最下面的两层；
2. 度为1的点只有0个或1个；

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

二叉树的遍历

从节点之间的位置关系的角度来看，二叉树的遍历分为4种：

1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 层序遍历

从更宏观的角度来看，二叉树的遍历分为2大类：

1. 深度优先遍历（前序遍历、中序遍历、后序遍历）
2. 广度优先遍历（层序遍历）

深度优先遍历

前序遍历：

​ 输出顺序是 根节点、左子树、右子树。

中序遍历：

​ 输出顺序是 左子树、根节点、右子树。

后序遍历：

​ 输出顺序是 左子树、右子树、根节点。

上图的遍历结果：

• 前序遍历：1 -> 2 -> 4 -> 5 -> 3 -> 6

• 中序遍历：4 -> 2 -> 5 -> 1 -> 3 -> 6

• 后序遍历：4 -> 5 -> 2 -> 6 -> 3 -> 1

实现（递归）

public class BinaryTree{
    
    TreeNode root;
    
    /**结点 */
    private static class TreeNode{
        int data;
        TreeNode leftChild;
        TreeNode rightChild;
    }
     /**前序遍历 */
    public static void preOrderTraveral(TreeNode node){
        if(node == null) return;
        System.out.print(node.data);		// 访问根节点
        preOrderTraveral(node.leftChild);	// 前序遍历左子树
        preOrderTraveral(node.rightChild);	// 前序遍历右子树
    }
     /**中序遍历 */
    public static void preOrderTraveral(TreeNode node){
        if(node == null) return;
        preOrderTraveral(node.leftChild);
        System.out.print(node.data);
        preOrderTraveral(node.rightChild);
    }
     /**后序遍历 */
    public static void preOrderTraveral(TreeNode node){
        if(node == null) return;
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
        System.out.print(node.data);
    }
}

​ 二叉树用递归的方式来实现前序、中序、后序遍历，是最为自然的方式，代码也最简洁。这3中遍历方式的区别，仅仅在于输出的执行位置不同：前序遍历输出在前，中序遍历输出在中间，后续遍历输出在最后。

​ 绝大多数可以用递归解决的问题，其实都可以用栈来解决。因为递归本身就是函数的嵌套调用，底层是基于栈来实现的。递归和栈都具有回溯的特性。

广度优先遍历

层序遍历：按照层级依次输出每个结点的数据。

实现：借助队列来实现二叉树的层序遍历。

public static void levelOrderTraveral(TreeNode node){
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(node);
    while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        System.out.print(node.data);	//输出节点的值
        if(node.leftChild != null)  queue.offer(leftChild);
        if(node.rightChild != null)  queue.offer(rightChild);
    }
}

二叉查找树

见本文 【查找】 –>【二叉查找树】部分。

平衡查找树

AVL树

​ 见本文 【查找】 –>【平衡查找树】–>【AVL树】部分。

2-3树

​ 见本文 【查找】 –>【平衡查找树】–>【2-3树】部分。

红黑树

​ 见本文 【查找】 –>【平衡查找树】–>【红黑树】部分。

B树

​ 二叉查找树和平衡二叉查找树都是用作内查找的数据结构，即查找的数据量不大，可以放在内存中操作。而对于无法全部放到内存的大数据，上面两种数据结构是不适用的。B树和B+树是用作外查找的数据结构，其数据放到外部存储中。

​ B树是一种自平衡的树，能够保持数据有序，数据的插入、删除、访问操作都可以在对数时间内O(log n)完成。

​ 在B树中，内部（非叶子）节点可以拥有可变数量的子节点。B树中每一个内部节点会包含一定数量的键，键将节点的子树分开。例如，如果一个内部节点有3个子节点（子树），那么它就必须有两个键： a1 和 a2 。左边子树的所有值都必须小于 a1 ，中间子树的所有值都必须在 a1 和a2 之间，右边子树的所有值都必须大于 a2 。

​

创建一棵5阶B树的过程：

B+树

​ B+树是B树的一种变形，比B树具有更广泛的应用。通常用于数据库和操作系统的文件系统中。B+树元素自底向上插入，这与二叉树恰好相反。

​ B+树内部节点可以有在预定范围内的可变数目的子节点。因此，B+树不需要像其他自平衡二叉查找树那样经常的重新平衡。

​ 在B+树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的阶数是m，则除了根之外的每个节点都包含最少 m/2 个元素最多 m-1 个元素，对于任意的结点有最多 m 个子指针。对于所有内部节点，子指针的数目总是比元素的数目多一个。所有叶子都在相同的高度上，叶结点本身按关键字大小从小到大链接。

​ 旧金山大学官网的数据结构的动画演示网址：（极力推荐）

B树：

​ 多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：

​ 在B树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。

优先队列

​ 优先队列是一个抽象的数据类型，它表示了一组值和对这些值的操作。优先队列最重要的操作就是删除最大元素 delMax() 和插入元素 insert() 。

/** 泛型优先队列的API */
public class MaxPQ<Key extends Comparable<Key>>{
    
    /** 创建一个优先队列 */
    MaxPQ();
    /** 创建一个初始容量为capacity的优先队列 */
    MaxPQ(int capacity);
    /** 用a数组中的元素创建一个优先队列 */
    MaxPQ(Key[] a);
    /** 插入元素 */
    void insert(Key k);
    /** 返回最大元素 */
    Key max();
    /** 删除并返回最大元素 */
    Key delMax();
    /** 队列是否为空 */
    boolean isEmpty();
    /** 队列中的元素个数 */
    int size();
}

考虑如下问题：

​ 输入N个字符串，每个字符串都对应着一个整数，你的任务是从中找出最大的（或是最小的）M个整数及其相关联的值。

​ 在某些应用场景中，输入量可能是非常巨大的，甚至可以认为输入是无限的。那么这种情况下，把N个数据都放到内存中排序肯定是不现实的，因为代价太大，或者说内存根本放不下这么大的数据量，无法实现。

​ 此时，二叉堆这种数据结构可以解决这个问题。

堆

​ 数据结构二叉堆能很好的实现优先队列的基本操作。

堆有序

​ 当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。

​ 在最大堆中，根结点是最大的元素；在最小堆中，根节点是最小的元素。

表示

​ 如果我们使用链表方式来实现二叉堆，那么每个结点都需要有三个指针（父结点和两个子结点各需要一个）；但如果我们使用一棵完全二叉树，表示就会特别方便，从根结点开始，然后一层一层由上往下，由左往右，把1~N个结点存到数组中而不需要指针就可以表示。

定义

​ 二叉堆是一棵满足堆有序的完全二叉树，并在数组中按照层级存储。

​ 在一个堆中，位置k的结点的父结点的位置为【k/2】，而它的两个子结点的位置分别是2k 和 2k + 1；在不使用指针的情况下，可以通过计算数组的索引下标实现在树中上下移动：从a[k] 向上层就使 k 等于 k/2，向下层就使 k 等于 2k 或 2k + 1。

性质

• 父节点下标为k，左子节点的下标为2k+1，右子节点的下标为2k+2 ；
• 最后一个非叶子节点的下标为 length / 2 -1;
• 当N达到2的幂时，完全二叉树的高度就会加1。（N=2^m^时，树的高度为 m+1）
• 一棵大小为N的完全二叉树的高度为log2^N。

​ 利用在数组中而无需指针即可实现在树中上下移动的遍历和以上性质，我们能够实现在对数级别完成对堆的插入和删除操作。

堆的算法

​ 关于堆，最重要的两个操作是插入和删除，插入新元素或删除最大元素都需要重新使堆有序化。

插入新元素（上浮）

​ 我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置。

删除最大元素（下沉）

​ 我们从数组的顶端删除最大元素，并让数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置。

实现

先把上浮和下沉的堆有序化逻辑实现:

/** 上浮: 新增元素至数组末尾并通过上浮使堆有序化 */
private void floating(int k){
    while(k>1 && less(k/2,k)){
        exch(k/2,k);
        k = k/2;
    }
}
/** 下沉: 删除最大元素,并把数组末尾元素放到顶端通过下沉使堆有序化 */
private void sink(int k){
    while(2*k < N){
        if(less(k,2*k)){
            exch(k,2*k);
            k = 2*k;
        }else if(less(k,2*k+1)){
            exch(k,2*k+1);
            k = 2*k+1;
        }else{
            return;
        }
    }
}

/** 第一个位置的元素是否比第二个小*/
private boolean less(int i,int j){
    return pq[i].compareTo(pq[j]) < 0;
}
/** 交换位置*/
private void exch(int i,int j){
    key k = pq[i];
    pq[i] = pq[j];
    pq[j] = k;
}

/** 基于堆实现的优先队列*/
public class MaxPQ<Key extends Comparable<Key>>{
    
    private Key[] pq;		
    private int N;			//存储于pq[1...N]中,pq[0]不使用;
    
    public MaxPQ(int capacity){
        pq = (Key[])new Comparable[capacity+1];
    }
    
    public void insert(Key k){
        pq[++N] = k;
        floating(N);	//上浮使堆有序化
    }
    
    public Key delMax(){
        Key max = pq[1];
        exch(1,N);
        pq[N] = null;
        N-=1;
        sink(1);	//下沉使堆有序化
        return max;
    } 
    public boolean isEmpty(){ return N == 0; }
    public int size(){ return N; }
}

堆排序

哈夫曼树

​ 哈夫曼树又叫最优二叉树，哈夫曼树是带权路径长度最短的树，权值较大的节点离根较近。

概念

路径

路径长度

​ 根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

带权路径长度

哈夫曼编码

跳跃表

skipList

并查集算法

​ 并查集（Union-Find ），是一种树形的数据结构，用于处理一些不相交集合的合并和查询问题，常常使用森林来表示。并查集是一个非常实用的算法。

主要操作

初始化

​ 初始状态下，并查集中的元素之间是没有联系的，即每个点所在的组就是其自身；

​ 初始化操作的时间复杂度总是O(N)；

查找

​ 查找元素所在的组，即根节点；

合并

​ 将两个元素所在的组合并为一个组；通常在合并之前判断两个元素是否在同一个组，即查找操作；

API

并查集优化

https://blog.csdn.net/yjw123456/article/details/78929640

算法	初始化	合并	查询
quick-find	N	N	1
quick-union	N	N+	N
Weighted quick-union	N	lgN+	lgN

思路

​ 每次查找的时候，如果路径较长，则修改结构，以便下次查找的速度更快。

路径压缩

使用场景：

​ 并查集可用于在无向连通图中检测环，

7. 图

​ 图（Graph）由顶点（Vertex）和边（Edge）组成。图的主要内容是对象及其连接，连接可能有方向和权重。利用图可以为很多重要而复杂的问题建模。对象及其连接映射到数学模型中，是顶点和边。

四种图模型

4种重要的图模型：

• 无向图 （连接无方向，最简单的图模型）
• 有向图 （连接有方向）
• 无向加权图 （连接无方向，有权值）
• 有向加权图 （连接既有方向又有权值）

注：图的方向和权值，映射到数学中和矢量是一样。在数学中，矢量是有大小，有方向的量。而标量只有大小，没有方向。

图相关的术语

图相关的术语非常之多，其中大多数定义都很简单，多熟悉就OK了。

路径和环

在图中，路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。

环是一条至少含有一条边且起点和终点相同的路径。简单环是一条不含有重复顶点和边的环。（起点和终点必须相同除外）

大多数情况下研究的对象都是简单路径和简单环，所有通常会省略简单二字。

有向图的边也称弧，边的始点称为弧尾，终点称为弧头。（箭头位置是弧头，箭尾位置是弧尾）

度、出度入度

顶点的度数即为依附与它的边的总数。

对于有向图而言，度又分为出度和入度。

顶点的出度——以顶点v为弧尾的弧的数目；

顶点的入度——以顶点v为弧头的弧的数目；

子图是一幅图所有边以及它们所依附的所有顶点的一个子集。

连通图

连通图和非连通图

如果从图中任意一个顶点都存在一条路径达到另一个任意顶点，我们称这幅图是连通图。

一副非连通图由若干连通的部分组成，它们都是该图的极大连通子图。

极小连通子图与极大连通子图是在无向图中进行研究讨论的。

极大连通子图

极大连通子图存在于连通图或非连通图中

1. 连通图只有一个极大连通子图，就是它本身。（是唯一的）

2. 非连通图有多个极大连通子图。（非连通图的极大连通子图叫做连通分量，每个分量都是一个连通图）

极小连通子图

极小连通子图只存在于连通图中

1. 一个连通图的生成树是该连通图的的极小连通子图。（同一个连通图可以有不同的生成树，所以生成树不是唯一的）
2. 用边把极小连通子图中所有节点给连起来，若有n个节点，则有n-1条边。如下图生成树有6个节点，有5条边。
3. 之所以称为极小是因为此时如果删除一条边，就无法构成一棵树。
4. 如果在生成树上添加一条边，一定会构成一个环。

也就是说只要能连通图的所有顶点而又不产生回路的任何子图都是它的生成树。

总结来说：极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的。

强连通图

在有向图中，若对于每一对顶点Vi和Vj，都存在一条从Vi到Vj和从Vj到Vi的路径，则称此图为强连通图。（连通的有向图）

有n个顶点的强连通图：最少有n条边，最多有 n(n-1) 条边。

树和图

一幅含有V个节点的图G，当且仅当满足下列5个条件之一时，它就是一棵树：

• G有V-1条边且不含有环；
• G有V-1条边且是连通的；
• G是连通的，删除任意一条边都会使它不再连通；
• G是无环的，添加任意一条边都会产生一条环；
• G中的任意一对顶点之间仅存在一条简单路径；

树是一张无环的连通图。互不相连的树组成的集合称为森林。

连通图的生成树是它的一副子图，它含有图中所有的顶点且是一棵树。

图的生成树森林是它的所有连通子图的生成树的集合。

​ 如上图，树其实就是一张图，一张无环的连通图。只不过我们在单独研究树这种数据结构时，并不把他当做图来看待，毕竟图论比树更加复杂一些。

稀疏图和稠密图

​ 在稀疏图中，被连接的顶点对很少；而在稠密图中，只有少部分顶点对之间没有边连接；一般来说，在一幅图中，如果边的数量E是顶点个数V的一个小的整数倍以内，我们认为这幅图是稀疏的，否则是稠密的。

特殊的边

自环

​ 即弧头和弧尾连接一个顶点的边。

平行边

​ 连接同一对顶点的边称为平行边。

图的表示方法

我们在图处理时，所采用的数据结构应该满足以下两方面要求：

1. 图本身占用的内存越小越好，空间复杂度低。
2. 初始化图实例时，越快越好，时间复杂度低。

理论上有三种图的表示方法（但并不是每一种表示方法都是实用的）：

• 邻接矩阵
• 边的数组
• 邻接表数组（广泛）

邻接矩阵

​ 可以使用一个V 乘 V 的布尔矩阵。当顶点 v 和 w 之间有相连接的边时, 定义v 行 w 列的值为true，否则为false； 这种方法不符合第一个条件，即V 平方个布尔值所需要的空间是很大，而且是浪费的。另外，如果允许存在平行边的话，邻接矩阵是无法表示平行边的。

​ 对于一个具有N个顶点的图,若用邻接矩阵表示,则该矩阵的大小为 N^2^ 。

边的数组

​ 使用一个Edge类，它含有2个int实例变量来记录两个顶点。这种方法比较简单，可是想要查找和顶点v 相邻的所有顶点，需要遍历图中所有的边。不符合第二个条件，时间复杂度高。

邻接表数组

使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表。

​ 若无向图中有 N 个顶点，e 条边，则它的邻接表需要 n 个头结点，2e个表节点。

​ 若有向图中有 N 个顶点，e 条边，则它的邻接表需要 n 个头结点，e个表节点。

使用邻接表数组实现的Graph 性能有如下特点：

• 使用的空间和 V + E 成正比；
• 添加一条边所需的时间是常数；
• 遍历顶点v的所有相邻顶点所需时间和v的度数成正比；

图的遍历

对于图有两种遍历方式：深度优先遍历DFS 和广度优先遍历 WFS。

深度优先遍历

​ 深度优先遍历是一头扎到底的玩法。我们选择一条支路，尽可能不断深入，如果到底了就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入。以此类推。

​ 像这样先深入探索，走到头在回退的过程中寻找其他出路的遍历方式，就叫深度优先遍历。二叉树的前序、中序、后序遍历，本质上也是一种深度优先遍历。

广度优先遍历

​ 还有一种遍历方式，首先遍历与起点相邻的几个点，然后去遍历稍远一些（隔一层）的点，然后再去遍历距离更远（隔两层）的点，以此类推。

​ 像这样一层一层，由内而外的遍历方式，就叫做广度优先遍历。二叉树的层序遍历，本质上也是一种广度优先遍历。

实现

​ 深度优先搜索只会访问和起点连通的顶点。

连通分量

深度优先搜索的下一个直接应用就是找出一幅图的所有连通分量。(Connected Component)

连通分量的API

CC(Graph G);
boolean connected(int v,int w);		//v和w是否连通
int count();			//连通分量数
int id(int v);			//v所在连通分量的标识符

无向图

图是由一组顶点和一组能够将两个顶点相连的边组成的。无向图的边无大小，无方向，是最简单的图模型。

有向图

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。

解释：假设有向图中有 5 条边，无论从入度还是出度角度去统计，最终统计的总数都是基于这 5 条边产生的，所以入度之和与出度之和相等。

定义及表示

定义

​ 有向图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。

表示

​ 我们使用邻接表来表示有向图，v -> w 表示顶点 v 所对应的邻接链表中包含一个 w 的顶点。这种表示方法和无向图几乎相同，而且每条边都只会出现一次。

逆邻接表

​ 使用邻接表记录的是结点的出度邻接信息，而结点的入度邻接信息是没有记录的，为此，需要设计一个记录结点入度邻接信息的数据结构，那就是逆邻接表。

​ 逆邻接表与邻接表相反。图的邻接表，反映的是节点的出度邻接情况，图的逆邻接表反映的是节点的入度邻接情况。

十字链表

环与有向无环图

在和有向环相关的实际应用中，有向环特别的重要。

没有计算机的帮助，在一幅普通的有向图中找出有向环可能会很困难。

从原则上来说，一幅有向图可能含有大量的环；在实际应用中，我们一般只会关注其中一小部分，或者只想知道有向环是否存在。

有向无环图：

有向无环图就是一幅不含有向环的有向图。

有向环的检测

拓扑排序

​ 拓扑排序是对有向无环图的顶点的一种排序。它的目的是将图中的顶点排成一个线性序列，使得对于图中的任意一条有向边（v1 -> v2），排序后顶点v1 都排在顶点 v2 的前面。这个排序是基于有向图中顶点之间的先后关系来进行的。

只有有向图无环图，它才能进行拓扑排序。换句话说，如果一幅有向图含有有向环，就不能进行拓扑排序。

实现方式

使用深度优先搜索对有向无环图进行拓扑排序所需的时间和 V+E 成正比。

主要应用

拓扑排序主要是用于解决有向无环图中任务的先后顺序问题。

在实际应用中，拓扑排序和有向环的检测总会一起出现，因为有向环的检测是拓扑排序的前提。

例如在一个任务调度应用中，无论计划如何安排，其背后的有向图中包含的环意味着存在了一个必须纠正的严重错误，因此解决任务调度类应用需要以下3步：

1. 确定任务和优先级条件。
2. 不断检测并去除有向图中的所有环，以确保存在可行性方案。
3. 使用拓扑排序解决调度问题。

强连通性

​ 在有向图中，如果两个顶点 v 和 w 是互相可达的，则称它们是强连通的。

​ 也就是说，强连通的两个顶点，既存在一条从v 到 w 的有向路径，也存在一条从 w 到 v 的有向路径。如果一幅有向图中的任意两个顶点都是强连通的，则称这幅有向图为强连通图。

强连通分量

​ 有向图的极大强连通子图称作有向图的强连通分量。强连通分量是一个最大子集，子集内的所有顶点之间都是强连通的。

​ 上面的有向图含有5个强连通分量。

​ 一个含有V 个顶点的有向图含有 1 ~ V 个强连通分量；

​ 一个强连通图只含有1个强连通分量；

​ 一个有向无环图含有 V 个强连通分量；（强连通和有向环是互斥的）

​ 需要注意的是强连通分量的定义是基于顶点的，而非边。有些边连接的两个顶点都在同一个强连通分量中，而有些边连接的两个顶点则在不同的强连通分量中。

强连通分量的典型应用

应用	顶点	边
网络	网页	超链接
软件	模块	调用
教科书	话题	引用
食物链	五种	捕食关系

可达性

加权无向图

​ 加权图是一种为每条边关联一个权值或成本的图模型。需要注意的是，权重不一定只表示距离，也可能表示时间，费用或是其他完全不同的变量。也不一定会和距离成正比。

生成树

图的生成树是它的一棵包含有其所有顶点的无环连通子图。图的生成树不唯一，从不同的顶点出发进行遍历，可以得到不同的生成树。

最小生成树

一幅加权图的最小生成树是它的一棵权值最小（树的所有边的权值之和）的生成树。

研究对象

最小生成树的研究对象是加权无向连通图。 注意三个条件：加权、无向、连通，不符合任意一个条件的场景，该算法不再适用。

典型应用

最小生成树的应用领域非常之多：

应用	顶点	边
电路	元器件	导线
航空	机场	航线
电力分配	电站	输电线
图像分析	面部容貌	相似关系

最小生成树算法

计算最小生成树的两种经典算法 （最古老最知名的算法之一）：

• Prim 算法
• Kruskal 算法

原理 – 切分定理

前面在说图和树的关系时，研究出树有两条重要的性质：

1. 用一条边连接树中的任意两个顶点，都会产生一个环。
2. 从树中删去一条边将会得到两棵独立的树。

这两条性质可以证明出最小生成树的一条基本定理：切分定理。

切分定理

图的一种切分是将图的所有顶点切分为两个非空且不重叠的两个集合。横切边是一条连接两个属于不同集合的顶点的边。

Kruskal 算法

Kruskal (克鲁斯卡尔) 算法

​ Kruskal算法是基于贪心算法得到的。首先我们把所有的边取出并按权值从小到大排序；接着按顺序依次选取每条边，如果没有形成环，那么该边就是最小生成树的一个边，如果形成环，则丢弃；直到边的数量达到 V-1，最小生成树构造完成。

第一步：将无向连通图所有的边取出，并按权值从小到大排序。（使用优先队列存储）

第二步：从小到大依次取出边，回添到图中。并判断两个条件：1. 是否存在环； 2. 是否已经完成；

第三步：如果存在环，则丢弃该边，继续下一次判断。

第四步：当边数为 V-1 时，最小生成树构建完成。

​ 克鲁斯卡尔算法比较容易理解，实现也不困难，我们会使用一个优先队列将边按权重排序，然后使用并查集来识别会形成的环，以及一个队列来保存最小生成树的边。

• 优先队列

• Union-Find 并查集算法

• 队列

时间复杂度

Prim 算法

构造最小生成树的每一步都是向这棵树添加一条新的边（权值最小的横切边）。

分析

Prim 算法的运行效率只与连通图中的顶点数量有关，与边数无关，所以Prim 算法更适合边稠密的图；Prim 算法的时间复杂度为O(N^2^)。

如果是稀疏图，则建议使用Kruskal 算法求最小生成树。

加权有向图

最短路径算法 Dijkstra

​ 在一幅加权有向图中，从顶点s 到顶点t 的最短路径是所有从s 到 t 的路径中的权重最小者。换句话说，就是从一个顶点到达另一个顶点的成本最小的路径。

最短路径的典型应用

应用	顶点	边
地图	交叉路口	公路
网络	路由器	网络连接
任务调度	任务	优先级限制
套汇	货币	汇率

Dijkstra 算法

AOE网

​ AOE 网（Activity - On - Edge Network）即边表示活动的网，是一个带权有向无环图。其中，顶点表示事件，边表示活动，边上的权值表示活动的持续时间。例如，在一个工程项目的进度安排中，AOE 网可以用来直观地表示各个子项目（活动）之间的先后顺序以及每个子项目所需的时间。

事件（顶点）

​ 事件是一个瞬间的概念，它标志着某些活动的开始或结束。在 AOE 网中，一个事件的发生意味着以该事件为起点的活动可以开始，或者以该事件为终点的活动已经结束。例如，在建筑工程中，“基础工程完成” 就是一个事件，它的发生使得 “主体建筑施工” 等后续活动可以开始。

活动（边）

​ 活动是有一定持续时间的任务。活动之间存在先后顺序，这种顺序通过有向边来表示。例如，在软件开发项目中，“需求分析完成” 后才能进行 “软件设计”，这里 “软件设计” 就是一个活动，从 “需求分析完成” 这个事件指向 “软件设计完成” 这个事件。

权值（活动持续时间）

​ 权值代表活动持续的时间。例如，如果 “软件设计” 这个活动的预计持续时间是 30 天，那么在 AOE 网中表示该活动的边的权值就是 30。

应用场景

• AOE 网主要用于项目管理中的关键路径分析。通过计算事件的最早发生时间、最迟发生时间以及活动的最早开始时间、最迟开始时间等，可以确定项目的关键路径。关键路径是 AOE 网中从源点到汇点的最长路径，它决定了项目的最短工期。例如，在一个大型活动的策划中，通过构建 AOE 网来分析关键路径，可以帮助组织者合理安排资源、确定各个子任务的时间窗口，从而确保活动能够按时完成。

8. 字符串

串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。

存储结构

顺序存储和链式存储。

子串

子串：串中任意个连续的字符组成的子序列称为该串的子串。注意空串和字符串本身都属于子串。

串的长度：串中所含字符的个数。

结论：如果一个字符串中有n个字符，则该字符串中子串的个数是 n(n+1)/2+1 。

例题：

1. 若串S=‘software’，其子串的数目是 8乘9除以2 +1 = 37；
2. 串s=″Data Structure″中长度为3的子串的数目是 12 个；

模式匹配算法

我们设字符串文本中包含n个字符，要查找的子串包含m 个字符。一般情况下 n 要远大于 m .

暴力匹配

暴力匹配算法（Brute-Force），简称为 BF算法。简单，效率低的字符串匹配算法，查找时间复杂度是O(n * m)。

RK指纹匹配算法

​ RK算法全称 Rabin-Karp, 是由算法的两位发明者Rabin 和Karp 的名字来命名的.
​ RK 算法是基于BF 算法的一种改进，BF算法只是简单粗暴地对两个字符串的所有字符依次比较, 而RK算法比较的是两个字符串的哈希值。时间复杂度是O(n);

KMP算法

​ KMP算法是一种改进的字符串匹配算法，由 Knuth，Morris 和 Pratt 三个人提出，因此简称KMP算法。

​ KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

​ KMP算法的时间复杂度**O(n+m)**。

研究前的约定：

​ 我们把文本称为 T (Text), 关键字称为 K (Key)；

​ 文本指针 i，关键字指针 j。

​ 文本长度 n, 关键字长度 m 。

T：goodgoogle

K: google

上面这种场景，使用暴力匹配算法需要对比13次才能匹配成功。

​ 使用KMP算法，每次匹配成功都会将DFA带向下一个状态（向右推进关键字指针 j ）；每次匹配失败都会使DFA回到较早前的状态（向左回退关键字指针 j ）。

​ 正文指针 i 是从左向右前进（不回退）的，一次一个字符，但关键字指针 j 会在DFA的控制下左右移动。

T：abcdefgab

K: abcdex

BM算法

​ Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。 一般文本编辑器中的查找功能都是基于它实现的。它由 Bob Boyer和 J Strother Moore设计于1977年。此算法仅对搜索目标字符串（关键字）进行预处理，而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。

​ 通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。移动字符数是通过两条规则决定的：坏字符规则和好后缀规则。实际移动为通过这两条规则计算出的最大移动个数。

多维数组和广义表

多维数组

数组A [0…4，-1…-3，5…7] 中含有的元素个数是 45.

解析：本题考查多维数组元素个数的计算，我们可以根据每一维的长度来确定总的元素个数。

分析每一维的长度：那么第一维的长度为 4 -0+1 =5（计算下标的长度时，要用上界减去下界再加1）。第二维的长度为 3，第三维的长度为 3.

根据多维数组元素个数等于各维长度的乘积这一规则，该数组总的元素个数为这三维长度的乘积，即：5 *3 *3 = 45 。

设二维数组A[1…m,1…n]按行存储在数组B中，则二维数组元素A[i,j]在一维数组B中的下标为 n * (i-1) +j 。

广义表

考点一：求表头、表尾、长度、深度。

1. 取表头 Head(L) ：表头是非空广义表的第一个元素，是原子或广义表。
2. 取表尾 Tail(L) ：表尾是去除表头外，其余元素构成的表，是广义表。
3. 表的长度：所包含元素的个数；
4. 表的深度：括号的最大层数。（如果递归则是无穷深度）

习题：

1. 广义表L=(a,(b,c)) ，进行 Tail(L) 操作后的结果是 （D）
   A、c B、b,c C、(b,c) D、((b,c))
   解析：取表尾一定要带着深度，不要落下。
2. 广义表L=(a,b,(c,d),(e,(f,g))) ，进行 Head(Tail(Head(Tail(Tail(L))))) 操作后的结果是 （D）
   A、(g) B、(d) C、c D、d
3. 广义表((a,b,c,d)) 的表头是____（a,b,c,d），表尾是()____

稀疏矩阵

​ 稀疏矩阵是指矩阵中大多数元素为零的矩阵。在实际应用中，稀疏矩阵通常用于表示那些大部分元素为零的数据结构，如图像、信号、网络等。

矩阵存储

矩阵存储是指将矩阵存储在计算机内存中的一种方式。根据存储方式不同，矩阵存储可以分为

• 行优先存储
• 列优先存储
• 对角线优先存储

压缩存储

稀疏矩阵的压缩存储方式有：

• 三元组
• 十字链表

三元组

​ 稀疏矩阵中，非零元素的个数远远小于零元素的个数。三元组顺序表是将稀疏矩阵的非零元素用一个三元组（行标、列标、元素值）来表示，然后将这些三元组存储在一个顺序表中。

优缺点

• 优点是简单直观，实现起来比较容易，能够有效地存储稀疏矩阵的非零元素信息。
• 缺点是当需要对矩阵进行一些操作（如矩阵转置）时，可能需要花费较多的时间来重新排列三元组的顺序。

十字链表

​ 十字链表是一种链式存储结构，用于存储稀疏矩阵。它为矩阵的每一行和每一列分别设置一个链表。每个非零元素既是行链表中的一个节点，也是列链表中的一个节点。节点结构通常包括五个域：行号、列号、元素值、指向同一行下一个非零元素的指针（用于行链表）和指向同一列下一个非零元素的指针（用于列链表）。

优缺点

• 优点是对于稀疏矩阵的插入和删除操作比较方便，因为它是链表结构，不需要移动大量元素。
• 缺点是存储结构相对复杂，需要更多的存储空间来存储指针，并且编程实现的难度相对较大。

README

作者：米开

版权声明：本文遵循知识共享许可协议3.0（CC 协议）： 署名-非商业性使用-相同方式共享 (by-nc-sa)

参考：

​ 《算法》第四版

​ 《大话数据结构》

​ 《漫画算法》

​ 旧金山大学算法可视化网站 (由于是国外网站，国内访问较慢，该网站提供源码下载，下载到本地使用更流畅)

​ 十大经典排序算法最强总结

修改记录：

2019-12-27 米开 第一次修订

2020-01-14 米开 增加图论算法内容

2020-02-01 米开 增加算法基础内容

2020-02-25 米开 增加堆和优先队列内容

2020-05-19 米开 增加并查集内容

2020-11-23 米开 字符串模式匹配算法

2024-12-17 米开 完善排序算法相关内容