算法——》排序&&查找

桃扇骨 2024-02-17 12:04 29阅读 0赞

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

#### 算法——》排序&&查找 ####

*  一、排序算法
 *   *  1、内部排序算法
     *  2、外部排序算法
 *  二、查找算法

## 一、排序算法 ##

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

### 1、内部排序算法 ###

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

### 2、外部排序算法 ###

<table> 
 <thead> 
  <tr> 
   <th align="left"><strong>算法</strong></th> 
   <th align="left"><strong>描述</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">多路归并排序</td> 
   <td align="left">将待排序的数据分为多个有序的子序列，然后通过多次归并操作将这些子序列合并为一个有序序列</td> 
  </tr> 
  <tr> 
   <td align="left">基于置换的排序</td> 
   <td align="left">通过多次置换操作将待排序的数据重新排列成有序的序列</td> 
  </tr> 
  <tr> 
   <td align="left">多层归并排序</td> 
   <td align="left">将待排序的数据分成多个层次，每个层次都进行归并排序操作，最终得到一个有序序列</td> 
  </tr> 
 </tbody> 
</table>

## 二、查找算法 ##

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

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

[Java]: https://blog.csdn.net/weixin_43453386/article/details/84788317
[Mysql]: https://blog.csdn.net/weixin_43453386/article/details/88667709
[Redis]: https://blog.csdn.net/weixin_43453386/article/details/127966762
[Kafka]: https://blog.csdn.net/weixin_43453386/article/details/128189472
[Spring]: https://blog.csdn.net/weixin_43453386/article/details/124900806
[SpringBoot]: https://blog.csdn.net/weixin_43453386/article/details/84788714
[MyBatis_MyBatis-Plus]: https://blog.csdn.net/weixin_43453386/article/details/84788053
[Linux]: https://blog.csdn.net/weixin_43453386/article/details/89241912
[MongoDB]: https://blog.csdn.net/weixin_43453386/article/details/84788450
[Elasticsearch]: https://blog.csdn.net/weixin_43453386/article/details/108583782