算法与数据结构 | Khaos‘s Blog

type

status

date

slug

summary

📝 主旨内容

算法

排序

冒泡排序（O(n^2)）：通过重复地交换相邻的元素来进行排序，较慢且稳定。

插入排序（O(n^2)）：通过构建有序序列，对未排序数据在已排序序列中进行比较并插入，较快但对初始状态依赖较大。

选择排序（O(n^2)）：每次从未排序的数据中选择最小值放到已排序的末尾，较慢但简单。

希尔排序（O(n log n) ~ O(n^2)）：将整个待排元素序列分割成若干子序列分别进行直接插入排序，具有优异的性能表现。

快速排序（O(n log n)）：通过选取一个基准点将序列拆分成两部分，在递归过程中对子序列进行同样的操作，快速且通用。

归并排序（O(n log n)）：采用分治思想，将序列分为若干个子序列进行排序，再将子序列合并到一起，稳定。

堆排序（O(n log n)）：通过将待排序序列构造成一个小顶堆，然后每次取出堆顶元素，重新调整堆，最终得到有序序列。

计数排序（O(n + k)）：不是基于比较的排序算法，而是根据待排序序列中每个元素出现的次数进行排序。

桶排序（O(n + k)）：将元素划分到若干个桶中，对每个桶内的元素进行排序后再合并，适用于元素分布均匀的情况。

堆排和快排的区别

堆排序 1.原理：利用最大（小）堆进行排序。 2.步骤： ①首先最大（小）堆； ②把堆顶跟完全二叉树的最后一个子叶进行交换，再把最后一个子叶放在数组的最后一位； ③重复以上①②。 3.适用场景：性能好，不稳定。适用于只求最大（小）M个数。

与快速排序不同的地方： 1.原理不同，堆排序是利用最大（小）堆进行排序，而快速排序是在冒泡排序法上进行改进的一种递归排序（从上到下）。 2.适用场景不同：快排不适用于基本有序或者逆序，也就是说适用于无序。但是堆排序对有序无要求。并且堆排序的性能稍微比快排好。快排平均时间复杂度是O(nlogn)，最好也是O（nlogn），但是最坏是O（n2）。而堆排序最好最坏都是O（nlogn）。

数据结构

树

红黑树

有高度差的

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 [2]

红黑树是一种特殊的二叉查找树，它用于维护有序的数据集合。它的特征是每个节点都具有颜色属性（红色或黑色），且红黑树的任何一个节点的左右子树也必须是红黑树。红黑树的优势在于它可以在O(log n)的时间内完成查找、插入和删除操作，而普通的二叉查找树需要O(n)的时间。因此，红黑树也是一种非常有效的数据结构，可以用来存储有序数据集合。

平衡树

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。

二叉平衡树的插入和删除过程都需要进行平衡调整，以保证树的平衡性。以下是二叉平衡树的插入和删除过程：

插入操作：

首先按照二叉搜索树的规则将新元素插入到树中的合适位置上。

然后从插入节点向上遍历，依次检查每个祖先节点是否平衡。如果某个祖先节点不平衡，则需要通过旋转操作使其重新平衡，直到整棵树恢复平衡为止。

删除操作：

首先按照二叉搜索树的规则找到要删除的节点，并将其删除。如果被删除节点有两个子节点，则需要将其右子树中最小的节点移动到被删除节点的位置上，以保持树的有序性。

然后从被删除节点的父节点开始向上遍历，依次检查每个祖先节点是否平衡。如果某个祖先节点不平衡，则需要通过旋转操作使其重新平衡，直到整棵树恢复平衡为止。

在平衡调整过程中，可能需要进行左旋、右旋、左右旋、右左旋等操作，以确保树的平衡性。

旋转：

搜索树的旋转是一种基本的操作，它可以使得树的结构更加平衡，提高搜索效率。搜索树的旋转包括左旋和右旋两种操作。

左旋

左旋操作可以将一个节点的右子树变为该节点的父节点，同时将该节点作为其左子树的根节点。具体来说，假设有一个节点x，它的右子树为y，y的左子树为z（可能为空）。左旋的过程如下：

(1) 将节点x的右子树y的左子树z赋值给x的右子树，同时让y成为x的父节点；

(2) 如果x原来是其父节点p的左子树，则将y设置为p的左子树；如果x原来是其父节点的右子树，则将y设置为p的右子树。

右旋

右旋操作可以将一个节点的左子树变为该节点的父节点，同时将该节点作为其右子树的根节点。具体来说，假设有一个节点x，它的左子树为y，y的右子树为z（可能为空）。右旋的过程如下：

(1) 将节点x的左子树y的右子树z赋值给x的左子树，同时让y成为x的父节点；

(2) 如果x原来是其父节点p的左子树，则将y设置为p的左子树；如果x原来是其父节点的右子树，则将y设置为p的右子树。

通过左旋和右旋操作，可以使得搜索树的结构更加平衡，并且保持搜索树的有序性质不变。

二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一种常用的数据结构，它可以支持快速的查找、插入和删除操作，并且具有较好的平均性能。下面是二叉搜索树适合的一些场景：

数据库索引

数据库中的索引通常采用B+树等平衡树结构来实现，而B+树是在二叉搜索树基础上做了优化。因此，在理解B+树之前，我们需要先掌握二叉搜索树。

缓存实现

在缓存中，经常需要将经常访问的数据保存到内存中，以提高数据访问速度。而二叉搜索树可以快速地定位到指定的数据，如果按照访问频率排序，那么被频繁使用的数据就会在二叉搜索树的顶部，从而提高了缓存的效率。

排序算法

二叉搜索树也可以作为一种排序算法来使用。利用二叉搜索树的特点，我们可以将一个无序的数据集合转换成有序的数据序列。具体实现方式是先将所有数据插入到二叉搜索树中，然后进行中序遍历，得到有序的数据序列。

符号表

在计算机科学中，符号表指的是一种存储键值对的数据结构，类似于字典或者映射。例如，在编译器中，符号表用于保存变量名、类型等信息。二叉搜索树可以作为一种实现方式，其键值对就对应着符号表中的变量名和类型等信息。

总的来说，二叉搜索树适合作为内存数据结构，可以提供比较快的数据访问速度和查询效率。但是，由于二叉搜索树的平衡状态需要手动维护，并且存在退化情况，因此在实际应用中需要根据具体情况选择更加适合的数据结构。

哈希表

通常用于数据存储，主要用于查找，插入和删除操作时间复杂度为O(1)；

树通常用于特定的存储任务，比如拓扑排序，表达式解析和最优搜索等。

🤗 总结归纳

以上均为一些算法和数据结构的特点