1整理一些不熟悉的常见数据结构和算法

数据结构

BST

二叉查找树（Binary Search Tree），也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（orted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；没有键值相等的节点

优点：有序缺点：极端条件下会退化成链表，降低查找效率

AVL

AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）,平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。

平衡二叉树也是一种特殊的二叉查找树，满足二叉查找树的特性

并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。 AVL树的查找稳定，查找、插入、删除的时间复杂度都为O（logN）但是由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。

优点：有序，解决了BST会退化成线性结构的问题缺点：进行插入和删除结点操作的时候，需要对结点进行频繁的旋转

红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，是一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性: （1）每个节点或者是黑色，或者是红色。（2）根节点是黑色。（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树在查找方面和AVL树操作几乎相同。但是在插入和删除操作上，AVL树每次插入删除会进行大量的平衡度计算，红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，在插入和删除中AVL树所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。

红黑树广泛用于TreeMap、TreeSet，以及jdk1.8后的HashMap。

虽然红黑树是一种已经被性能优化了的自平衡的二叉查找树，插入修改效率和查找销量得到了平衡，但他依然存在一些问题。

依旧在插入和删除时需要对节点进行旋转，频繁修改数据的场景影响效率。
红黑树毕竟是一种二叉树，当数据量很大时，树的高度会变得很大，查找时经过的节点过多，效率变低。
红黑树在内存中表现，但因为树的高度的问题，当使用磁盘等辅助存储设备读写数据时（如MySQL等数据库），会导致数据在磁盘中散布分散，并且IO次数过多，效率变低。
适合单个查询，对于数据查询中常见的范围查询场景，无法很好支持。

针对于上述问题，有了天生为磁盘存储而生的B树。

以上三种树都是基于二叉树

二叉树每一个节点只能存放一个元素，并且每个节点只有两个子节点。当进行查找时，就需要多次磁盘IO 在实际应用中，数据是存放在磁盘中的，每次查询是将磁盘中的一页数据加入内存，树的每一层节点存放在一页中，不同层数据存放在不同页。这样如果需要多层查询就需要多次磁盘IO。为了解决这个问题，就出现了B树

B-树

B树也是一种自平衡的树，在进行插入和删除操作时也需要对结点进行旋转等操作。但是与AVL树和红黑树相比每个节点包含的关键字增多了，从而减小了树的深度，可以相对减少磁盘IO的次数。特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度，因此B树被广泛用于文件系统及数据库中

弊端： B树的查找不稳定，最好的情况就是在根节点查到了，最坏的情况就是在叶子结点查到。 B树在遍历方面比较麻烦，由于需要进行中序遍历，所以也会进行一定数量的磁盘IO。

除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。

为了解决这些问题，出现了B+树。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B树的优势除了树高小，还有对访问局部性原理的利用。

所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。

在数据库应用中，B树的每个节点存储的数据量大约为4K, 这是因为考虑到磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次对磁盘进行IO数据读取时，同一个磁盘块的数据会被一次性读取出来，所以每一次磁盘IO都可以读取到B树中一个节点的全部数据。

对于顺数插入的数据，B树的结构优势可以使其在内存中顺序排列，存贮到同一个磁盘页中，顺序插入对磁盘的利用率和读取效率都非常友好。

场景：MySQL的InnbDB 索引。

B树虽然解决了磁盘存储的问题，但是在查询范围数据时依旧不够，比如你要查询1-5的数据，必须按照树的中顺遍历来访问各个节点。

对于这个问题，B+树对其进行了优化。

B+树

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。 2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树的优点：

B+树的层级更少：非叶子结点中存放的元素不存放数据，所以每一层可以容纳更多元素，比B-树更加“矮胖”，也就是磁盘中的每一页可以存放更多元素。这样在查找时，磁盘IO的次数也会减少
B+树查询速度更稳定：每次查找都必须匹配到叶子节点，因此每一次查找都是稳定的。B-树由于中间节点也携带数据，因此只需要匹配到要查找的元素即可，最好的情况是在根节点就结束查找，最坏的情况是在叶子节点结束查找，查找性能不稳定
B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在范围查询数据时候更方便，数据紧密性很高，缓存的命中率也会比B-树高。
B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描

数据结构	查找时间复杂度	插入时间复杂度	特点
BST	最好：O(1)（根节点）平均：O(log n) 最坏：O(n)（退化成链表）	最好：O(1) 平均：O(log n) 最坏：O(n)	不自动平衡，可能退化成链表
AVL树	最好/平均/最坏：O(log n)	最好/平均/最坏：O(log n)	严格平衡（左右子树高度差 ≤1），查找快但插入/删除需频繁旋转
红黑树	最好/平均/最坏：O(log n)	最好/平均/最坏：O(log n)	近似平衡（最长路径 ≤ 2倍最短路径），插入/删除比AVL树高效，适合频繁修改
B树	最好：O(1)（根节点命中）平均/最坏：O(log n)	最好/平均/最坏：O(log n)	多路平衡树，节点存储多个键，适合磁盘存储（减少I/O次数）
B+树	最好：O(1)（根节点命中）平均/最坏：O(log n)	最好/平均/最坏：O(log n)	非叶子节点仅存索引，叶子节点链表连接，范围查询高效，数据库索引常用

关键区别总结

平衡性：
- AVL树：最严格平衡，查找效率最高，但维护成本高。
- 红黑树：牺牲严格平衡换取插入/删除效率。
- B树/B+树：通过多路分支降低树高，适合外存（如数据库/文件系统）。
适用场景：
- 内存操作：红黑树（Java TreeMap）、AVL树（查找密集型）。
- 磁盘存储：B树（文件系统）、B+树（数据库索引）。
退化风险：
- 只有 BST 可能退化成 O(n)，其他均为平衡树。
范围查询：
- B+树 的叶子节点链表支持高效范围查询，优于B树。

堆

八大算法

记忆

稳定性

稳定：茶猫轨迹（插入——冒泡——归并——基数）
其余的都是不稳定的

空间复杂度

只有快排是O（logn），其余都是O（1）

1.插入排序

1.直接插入排序

2.希尔排序

2.选择排序

1.直接选择排序

2.堆排序

3.交换排序

1.冒泡排序

它重复地“遍历”要排序的数列，一次比较两个相邻元素，如果它们的顺序错误（例如，从小到大排序时，前一个比后一个大），就把它们交换过来。

算法核心思想：

比较相邻元素：从数组的第一个元素开始，比较相邻的两个元素。
交换位置：如果第一个元素比第二个大（对于升序排序），就交换它们的位置。
重复遍历：对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最大的元素就会“冒泡”到数组的末尾。
缩小范围：针对所有未排序的元素重复以上的步骤，除了最后一个（因为每一轮都会确定一个最大元素的位置）。
终止条件：直到没有任何一对数字需要比较，也就是说整个数组已经排序完成。

基础代码实现

public void test(int[] nums){
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {
        // 减去 i 是因为每过 i 轮，数组末尾的 i 个元素已经排好序，无需再比较
        for (int j = 0; j < n - i - 1; j++) {
            if(nums[j] > nums[j + 1]){
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

优化实现：

基础版本即使数组在中间某轮已经完全有序，它仍然会继续执行完所有的 n-1 轮循环。我们可以通过一个标志位来优化它。如果在一轮遍历中没有发生任何交换，就说明数组已经有序，可以提前终止排序。

public void test(int[] nums){
    int n = nums.length;
    boolean flag;	// 标志位，记录本轮是否发生了交换
    for (int i = 0; i < n - 1; i++) {
        flag = false;	// 每一轮开始前，重置标志位
        for (int j = 0; j < n - i - 1; j++) {
            if(nums[j] > nums[j + 1]){
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
                flag = true;	// 设置标志位为 true
            }
        }
        // 如果这一轮没有发生任何交换，说明数组已经有序，提前退出
        if(!flag)
            break;
    }
}

复杂度分析：

时间复杂度：
- 最坏情况：数组完全逆序，需要比较 (n-1) + (n-2) + ... + 1 = n(n-1)/2 次，即 **O(n²)**。
- 最好情况：数组已经有序。优化后的版本只需一轮遍历（n-1 次比较）即可退出，即 **O(n)**。而未优化的版本仍然是 O(n²)。
- 平均情况：**O(n²)**。
空间复杂度：由于只需要一个临时变量 temp，所以是 **O(1)**。

2.快速排序

快速排序的逻辑是，若要对nums[lo..hi]进行排序，我们先找一个**分界点p**，通过交换元素使得nums[lo..p-1]都小于等于nums[p]，且nums[p+1..hi]都大于nums[p]，然后递归地去nums[lo..p-1]和nums[p+1..hi]中寻找新的分界点，最后整个数组就被排序了。

算法核心思想：

选择基准：从数组中选择一个元素作为”基准”。
分区操作：重新排列数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数组的中间位置。这个称为分区操作。
递归排序：递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。

详细步骤说明：

选择中枢（Pivot）：这是起点。中枢的选择有多种方式（如第一个元素、最后一个元素、中间元素或随机元素），但目标都是希望它能将数组平均分成两部分。我们以选择第一个元素为例。
分区操作（Partitioning） - 最核心的一步：这是快速排序的灵魂。分区的目标是“以小划大，以大划小”，让中枢归位。通常使用两个指针（通常称为 i 和 j 或 left 和 right）从数组两端向中间扫描：
1. 初始化：将选定的中枢元素拿出来“保管好”。左指针指向序列起始位置，右指针指向序列末尾。
2. 右指针左移：让右指针 j 从右向左扫描，寻找第一个小于中枢的元素。
3. 左指针右移：让左指针 i 从左向右扫描（从第二个元素开始），寻找第一个大于等于中枢的元素。
4. 交换：如果此时左指针还在右指针的左边（i <= j），则交换这两个指针所指向的元素。然后重复步骤2和3，继续扫描和交换。
5. 中枢归位：当两个指针相遇或交叉（即 i > j）时，扫描停止。此时，右指针 j 的位置就是中枢元素的最终正确位置。将最开始保管的中枢元素与 j 指针位置的元素进行交换。
  - 至此，一趟分区完成。中枢左边的元素都小于等于它，右边的元素都大于等于它。中枢本身已经位于其在完全排序后应该处在的位置。
递归排序子序列：中枢归位后，数组被分成了两个独立的子数组：
- 左子数组：所有元素小于中枢。
- 右子数组：所有元素大于中枢。
对这两个子数组递归地（Recursively）重复第一步和第二步，进行快速的排序。
基准情况（Base Case）
递归必须有一个结束条件。当子数组的长度小于等于1时，它自然就是有序的，不需要再继续分解和排序。此时递归开始“返回”。

算法实现：

/**
 * 快速排序的主要方法
 * @param nums 待排序的数组
 * @param l 当前排序区间的左边界（包含）
 * @param r 当前排序区间的右边界（包含）
 */
private void quickSort(int[] nums, int l, int r){
    // 递归终止条件：当左边界小于右边界时才需要排序
    // 如果 l >= r，说明区间内只有一个元素或没有元素，已经有序
    if(l < r){
        // 调用分区函数，将数组分区并返回基准元素的最终位置
        int mid = partition(nums, l, r);
        // 递归排序基准元素左边的子数组
        quickSort(nums, l, mid - 1);
        // 递归排序基准元素右边的子数组
        quickSort(nums, mid + 1, r);
    }
}

// 随机数生成器实例，用于随机选择基准元素
private final Random rand = new Random();

/**
 * 分区函数：将数组重新排列，使得基准元素左边的元素都小于等于它，右边的元素都大于等于它
 * @param nums 待分区的数组
 * @param l 分区区间的左边界
 * @param r 分区区间的右边界
 * @return 基准元素的最终位置
 */
private int partition(int[] nums, int l, int r) {
    // 随机选择基准元素的位置，避免最坏情况
    // nextInt(r - l + 1) 生成 [0, r-l] 的随机数，加上 l 后得到 [l, r] 范围内的随机索引
    int pivotIndex = rand.nextInt(r - l + 1) + l;
    
    // 将随机选择的基准元素交换到数组最左边位置，便于后续处理
    swap(nums, pivotIndex, l);
    
    // 获取基准元素的值
    int pivot = nums[l];
    
    // 初始化双指针：
    // i 从左向右扫描，寻找第一个大于等于基准的元素
    // j 从右向左扫描，寻找第一个小于等于基准的元素
    int i = l + 1, j = r;
    
    // 双指针扫描循环，直到指针相遇或交叉
    while (i <= j){
        // 如果当前i指向的元素小于基准，符合要求，i向右移动
        if(nums[i] < pivot)
            i++;
        // 如果当前j指向的元素大于基准，符合要求，j向左移动
        else if (nums[j] > pivot) {
            j--;
        }
        // 否则，说明：
        // nums[i] >= pivot 且 nums[j] <= pivot
        // 即i指向了一个应该在右边的元素，j指向了一个应该在左边的元素
        else {
            // 交换这两个元素，使它们到正确的一侧
            swap(nums, i, j);
            // 交换后，移动两个指针继续扫描，防止死循环
            i++;
            j--;
        }
    }
    
    // 循环结束后，j指向最后一个小于等于基准的元素的位置
    // 将基准元素从最左边交换到j的位置，这样基准元素就到了最终的正确位置
    swap(nums, l, j);
    
    // 返回基准元素的最终位置，用于后续的递归分区
    return j;
}

/**
 * 交换数组中两个位置的元素
 * @param nums 数组
 * @param l 第一个位置的索引
 * @param r 第二个位置的索引
 */
private void swap(int[] nums, int l, int r) {
    // 临时变量用于存储第一个元素的值
    int temp = nums[l];
    // 将第二个元素的值赋给第一个位置
    nums[l] = nums[r];
    // 将临时变量中存储的第一个元素的值赋给第二个位置
    nums[r] = temp;
}

4.归并排序

5.基数排序

快速排序

流程说明：

**第二步：

**第四步

/* 快速排序主函数 */
void sort(int[] nums) {
    // 一般要在这用洗牌算法将 nums 数组打乱，
    // 以保证较高的效率，我们暂时省略这个细节
    sort(nums, 0, nums.length - 1);
}

/* 快速排序核心逻辑 */
void sort(int[] nums, int lo, int hi) {
    if (lo >= hi) return;
    // 通过交换元素构建分界点索引 p
    int p = partition(nums, lo, hi);
    // 现在 nums[lo..p-1] 都小于 nums[p]，
    // 且 nums[p+1..hi] 都大于 nums[p]
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

索引p左侧的元素都比nums[p]小，右侧的元素都比nums[p]大，意味着这个元素已经放到了正确的位置上，回顾快速排序的逻辑，递归调用会把nums[p]之外的元素也都放到正确的位置上，从而实现整个数组排序，这就是快速排序的核心逻辑。

Partition 函数的主要任务是：

选择一个”基准”（pivot）元素
重新排列数组，使得所有小于基准的元素都排在基准前面
所有大于基准的元素都排在基准后面
基准元素最终位于其正确的位置

int partition(int[] nums, int lo, int hi) {
    if (lo == hi) return lo;
    int pivot = nums[lo];	// 将 nums[lo] 作为默认分界点 pivot
    int i = lo, j = hi + 1;	// j = hi + 1 因为 while 中会先执行 --
    while (true) {
        // 保证 nums[lo..i] 都小于 pivot
        while (nums[++i] < pivot) {
            if (i == hi) break;
        }
        // 保证 nums[j..hi] 都大于 pivot
        while (nums[--j] > pivot) {
            if (j == lo) break;
        }
        if (i >= j) break;
        // 如果走到这里，一定有：
        // nums[i] > pivot && nums[j] < pivot
        // 所以需要交换 nums[i] 和 nums[j]，
        // 保证 nums[lo..i] < pivot < nums[j..hi]
        swap(nums, i, j);
    }
    // 将 pivot 值交换到正确的位置
    swap(nums, j, lo);
    // 现在 nums[lo..j-1] < nums[j] < nums[j+1..hi]
    return j;
}

// 交换数组中的两个元素
void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

快速选择

对于寻找第k大的元素，我们可以把p和k进行比较，如果p < k说明第k大的元素在nums[p+1..hi]中，如果p > k说明第k大的元素在nums[lo..p-1]中。

所以我们可以复用partition函数来实现这道题目

数据结构与算法