树状数组

一、什么是树状数组

树状数组，其英文是 Binary Indexed Tree（简称 BIT），也称为 二叉索引树/二叉下标树。

• 树状数组虽然名称后缀是数组，但实际上是一棵由数组实现的树

最基本的树状数组支持 2 种操作：

• 单点修改：更新数组 nums 中任意单个元素值
• 区间查询：求数组 nums 中任意区间的元素和

并查集

一、什么是并查集？

并查集是一种简单的集合表示。

它支持以下 3 种操作：

• Initial(S)：将集合 S 中的所有元素初始化为一个个单元素集合
• Union(S, Root1, Root2)：把集合 S 中的子集合 Root2 并入子集合 Root1 中
• Find(S, x)：查找集合 S 中单元素 x 所在的子集合，并返回子集合的名字

排序算法的选择

一、算法汇总

希尔排序

一、什么是希尔排序？

• 希尔排序是一种基于插入排序进行了优化后的排序算法
• 希尔排序比普通插入排序更适用于大规模数组排序

二、为什么要用希尔排序？

散列表

一、什么是散列表？

1.1 定义

散列表（Hash Table），也称为哈希表，其定义如下：

• 散列表是一种能够根据关键字，直接访问到值的数据结构
• 散列表建立了关键字和存储地址之间的一种直接映射关系

其中，关键字称为 Key，对应的值称为 Value。

因此散列表也可以说是：

跳表

一、什么是跳表？

跳表，又叫做跳跃表、跳跃列表。

• 是一种对有序链式线性表的优化
• 在原始链表的基础上添加了多级索引链表
• 分为多层，从下往上分别是原始链表、一级索引、二级索引…
• 搜索时从上往下，实现了类似“二分查找”的功能

线段树

一、线段树是什么？

• 线段树本质上是一种缓存，它缓存的是区间值
• 线段树一棵平衡二叉树
• 线段树的节点表示的是一个区间，节点值表示区间值

二分查找

一、代码模板

常见的二分查找模板代码如下：

1
2
3
4
5
6
7
8
9
10

left = low, right = high;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (满足条件) {
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
return left; // 或 right

在二分查找中，有几个需要注意的地方：

基数排序

一、算法描述

1.1 核心思想

• 数据有高低位之分，位之间有递进关系
• 高位相等的情况下，才去对比低位大小
• 按照低位到高位的顺序，使用稳定排序算法对每一位排序

1.2 细节解释

桶排序

一、算法描述

1.1 核心思想

• 把不同范围的数据划分到不同的桶中
• 桶与桶之间是有序的，桶间无需排序
• 只需要对桶内的数据排序

1.2 细节解释