DEV Community
·
搜索/排序算法
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
本文介绍了几种搜索和排序算法，包括线性搜索、二分搜索、归并排序、快速排序和冒泡排序。线性搜索的时间复杂度为O(n)，二分搜索为O(log n)，归并排序和快速排序的平均时间复杂度为O(n log n)，而冒泡排序为O(n^2)。文中还提供了示例代码。
🎯
关键要点
- 介绍了几种搜索和排序算法，包括线性搜索、二分搜索、归并排序、快速排序和冒泡排序。
- 线性搜索的时间复杂度为O(n)，二分搜索为O(log n)。
- 归并排序和快速排序的平均时间复杂度为O(n log n)，而冒泡排序为O(n^2)。
- 提供了线性搜索的示例代码。
- 提供了二分搜索的示例代码。
- 提供了归并排序的示例代码，包括合并两个已排序列表的函数。
- 提供了快速排序的示例代码，说明了最坏情况下的时间复杂度为O(n^2)。
- 提供了冒泡排序的示例代码，说明了如何通过交换元素进行排序。
- 展示了搜索和排序算法的示例用法。
❓
延伸问答
线性搜索的时间复杂度是多少？
线性搜索的时间复杂度为O(n)。
二分搜索适用于什么类型的数组？
二分搜索适用于已排序的数组。
归并排序的平均时间复杂度是什么？
归并排序的平均时间复杂度为O(n log n)。
快速排序在最坏情况下的时间复杂度是多少？
快速排序在最坏情况下的时间复杂度为O(n^2)。
冒泡排序的基本原理是什么？
冒泡排序通过重复交换相邻元素来排序，直到没有元素需要交换。
能否提供线性搜索的示例代码？
可以，线性搜索的示例代码如下： ```python def linear_search(arr, target): for i, val in enumerate(arr): if val == target: return i return -1 ```
➡️
