选择

开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

1. 初始状态下，所有元素未排序，即未排序（索引）区间为 。
2. 选取区间 中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。
3. 选取区间 中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。
4. 以此类推。经过 轮选择与交换后，数组前 个元素已排序。
5. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

二分查找

基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

时间复杂度：。
空间复杂度：。

图

图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。

常见类型和术语

图的分类：

• 根据边是否具有方向：
  • 有向图
  • 无向图
• 根据所有定点是否连通：
  • 连通图：从某个顶点出发，可以到达其余任意顶点
  • 非连通图：从某个顶点出发，至少有一个顶点无法到达
• 边是否有权重：
  • 无权图
  • 有权图

堆

堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型：

• 小顶堆：任意节点的值 ≤ 其子节点的值。
• 大顶堆：任意节点的值 ≥ 其子节点的值。

哈希表

在哈希表中增删查改的时间复杂度都为 。

哈希表的简单实现

仅用一个数组来实现哈希表。数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。哈希函数的计算分为两步：

数组

访问元素

/* 随机访问元素 */
int randomAccess(int[] nums) {
    // 在区间 [0, nums.length) 中随机抽取一个数字
    int randomIndex = ThreadLocalRandom.current().nextInt(0, nums.length);
    // 获取并返回随机元素
    int randomNum = nums[randomIndex];
    return randomNum;
}

栈

先入后出。

常见操作：入栈push()、出栈pop()、访问栈顶元素peek()，时间复杂度都为 。

二叉树

根节点、叶节点、边、二叉树的高度、节点的深度、节点的高度：

它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。

迭代和递归

迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。