算法——》排序&&查找

推荐链接：
    总结——》【Java】
    总结——》【Mysql】
    总结——》【Redis】
    总结——》【Kafka】
    总结——》【Spring】
    总结——》【SpringBoot】
    总结——》【MyBatis、MyBatis-Plus】
    总结——》【Linux】
    总结——》【MongoDB】
    总结——》【Elasticsearch】

算法——》排序&&查找

一、排序算法

用于将一组数据按照特定的规则进行排序。
排序算法可以分为内部排序和外部排序两种。
不同的排序算法在时间复杂度、空间复杂度和稳定性等方面有所差异，选择合适的排序算法取决于具体的应用场景和数据规模。

1、内部排序算法

算法描述
冒泡排序（Bubble Sort）重复比较相邻的两个元素，如果顺序错误就交换位置，直到整个序列有序
插入排序（Insertion Sort）将待排序的元素插入已经排好序的序列中的正确位置，直到整个序列有序
选择排序（Selection Sort）每次从待排序序列中选择最小（或最大）的元素放到已排序序列的末尾，直到整个序列有序
快速排序（Quick Sort）选择一个基准元素，将比基准元素小的元素放在基准元素的左边，比基准元素大的元素放在基准元素的右边，然后递归地对左右两个子序列进行快速排序
归并排序（Merge Sort）将待排序序列划分为两个子序列，分别对两个子序列进行归并排序，然后将排序好的两个子序列合并成一个有序序列
堆排序（Heap Sort）将待排序序列构建成一个最大堆（或最小堆），然后依次取出堆顶元素，再对剩余元素进行堆调整，直到整个序列有序

2、外部排序算法

算法描述
多路归并排序将待排序的数据分为多个有序的子序列，然后通过多次归并操作将这些子序列合并为一个有序序列
基于置换的排序通过多次置换操作将待排序的数据重新排列成有序的序列
多层归并排序将待排序的数据分成多个层次，每个层次都进行归并排序操作，最终得到一个有序序列

二、查找算法

查找算法 = 搜索算法，是一种用于在数据集中查找特定元素的算法。
查找算法可以应用于各种数据结构，如数组、链表、树等。

算法描述
线性查找顺序遍历数据集，逐个比较元素，直到找到目标元素或遍历完整个数据集。时间复杂度为O(n)，其中n为数据集的大小
二分查找仅适用于已经排序的数据集。从数据集的中间元素开始比较，如果目标元素小于中间元素，则在左半部分继续查找；如果目标元素大于中间元素，则在右半部分继续查找；如果目标元素等于中间元素，则找到目标元素。时间复杂度为O(log n)
哈希查找通过哈希函数将目标元素映射到一个位置，然后在该位置进行查找。哈希查找的平均时间复杂度为O(1)，但是在处理哈希冲突时可能需要线性查找
二叉查找树将数据集构建成二叉查找树，其中每个节点的左子树的值小于节点的值，右子树的值大于节点的值。通过比较目标元素和节点的值，可以在二叉查找树中进行快速查找
平衡二叉查找树在二叉查找树的基础上，通过旋转操作保持树的平衡，以提高查找效率。常用的平衡二叉查找树有红黑树、AVL树等
B树和B+树适用于大规模数据的查找，将数据集分散存储在多个节点中，通过多级索引进行查找。B树和B+树的高度较小，能够减少磁盘I/O操作，提高查找效率
字符串匹配算法用于在文本中查找特定的字符串。常用的字符串匹配算法有暴力匹配算法、KMP算法、Boyer-Moore算法等