六种常见的排序算法 冒泡排序 BubbleSort基本原理在一趟扫描中，如果元素 array[i] 大于元素 array[i]，则交换二者位置，这样最大的元素就会移动到数组最后，然后开始下一趟扫描，扫描区间的长度减一 复杂度平均时间复杂度 $ O(N^2) $，最好可以到 $ O(N) $，如果已经有序，提前终止排序即可 代码实现123456789101112131415161718192021public clas 2022-07-21 算法 算法 排序
数据结构 B树 B 树基本概念B 树是一种平衡的多路搜索树，多用于文件系统、数据库系统的实现，B 树具有以下特点 与二叉树不同，一个节点可以存储超过 2 个元素，也可以拥有超过 2 个子树 平衡，每个节点的所有子树高度一致，整体高度较矮 也具有二叉搜索树的性质，例如对于任意元素，大于所有左子树上的元素而小于所有右子树（以及同节点内右侧的元素）上的元素 对于一棵 5 阶 B 树，每个节点最多可以有 5 个子树 2022-05-21 数据结构 Java 二叉树 数据结构
数据结构 AVL树 基本概念普通的二叉搜索树的缺陷对于普通的二叉搜索树，如果添加元素时，恰好按照元素的大小顺序进行添加，那么二叉搜索树就会退化为链表，同样的，删除元素时也可能导致二叉搜索树的退化，此时 BST 的添加、删除、查找的时间复杂度将上升至 $ O(N) $，例如对于如下 BST 删除 2，8，9，11 节点将导致 BST 的退化 平衡如何防止二叉搜索树退化成链表？让添加、删除、搜索的复杂度维持在 $ O 2022-05-20 数据结构 Java 二叉树 数据结构
数据结构 二叉树BinaryTree 树 Tree以下面的树为例子 节点 节点：图中 1、2、3 等都是这棵树的节点 根节点：1 父节点：例如 1 是 2、3、4、5、6 的父节点，2 是 21、22的父节点 子节点：与父节点相反，2、3、4、5、6 是 1 的子节点，21、22 是 2 的子节点 兄弟节点：同一个父节点下的子节点互为兄弟节点，例如 21 和 22 是兄弟节点 空树：一棵树没有任何节点，包括没有根节点 一棵树可以只有 2022-04-23 数据结构 Java 二叉树 数据结构
数据结构 队列Queue 队列 Queue 队列是一种特殊的线性表，只能在头尾两端操作 队尾（rear）: 只能从队尾添加元素，即 enQueue，入队 队头（front）: 只能从队头移除元素，即 deQueue，出队 队列遵循先进先出的原则，First In First Out，FIFO 实现队列 队列的内部实现可以使用动态数组或双向链表实现，但是优先使用双向链表 LinkedList，因为队列主要是操作头尾元素 2022-04-16 数据结构 Java 数据结构 队列
数据结构 栈Stack 栈 Stack 栈是一种特殊的线性表, 只能在一端（栈顶）进行操作 向栈中添加元素的操作，即 push，入栈，压栈 从栈中移除元素的操作(只能移除栈顶的元素)，即 pop，出栈，弹栈 栈遵循后进先出原则：Last In First Out，LIFO 实现栈 栈的内部实现可以使用动态数组或双向链表，因为栈的主要操作是在尾部添加或删除元素，所以入栈出栈复杂度都是 $ O(1) $（注意必须是双向链 2022-04-09 数据结构 Java 数据结构 栈
数据结构 循环链表CircleLinkedList 单向循环链表单向循环链表的尾节点的 next 指针不再是 null，而是指向链表的头节点，以形成环 实现单向循环链表相比单向链表，单向循环链表需要重写插入节点、删除节点两个方法 插入节点对于插入节点，需要特别关注插入头节点的情况，此时需要拿到尾节点，然后将其 next 指向新的头节点 123456789101112131415161718public void add(int index,E e 2022-04-07 数据结构 链表 Java 数据结构 链表
数据结构 双向链表LinkedList 双向链表 之前的单向链表只能通过 Node 中 next 属性从头遍历链表，完成搜索 双向链表中的 Node 增加 prev 属性，指向该节点上一个节点 双向链表查找元素可以从 first 或 last 两个方向开始查找，故而可以提高效率 Java 官方 LinkedList 就是双向链表 实现双向链表相比单向链表，双向链表需要重写查找节点、添加节点、删除节点、清空链表四个方法 1. 属性增加 2022-04-06 数据结构 链表 Java 数据结构 链表