为面试编码排序和搜索备忘单
原文：https://www.techinterviewhandbook.org/algorithms/sorting-searching/
简介
排序是将序列中的元素按顺序重新排列的行为，可以是数字顺序或字典顺序，也可以是升序或降序。
一些基本算法运行在 O(n 2 )中，不应该在面试中使用。在算法面试中，你不太可能需要从头开始实现任何排序算法。相反，您需要使用语言的默认排序函数对输入进行排序，这样您就可以对它们使用二进制搜索。
在一个排序的元素数组上，通过利用它的排序属性，使用二分搜索法可以在比 O(n)更快的时间内完成搜索。二分搜索法将目标值与数组的中间元素进行比较，这将通知算法目标值是位于左半部分还是右半部分，并且对剩余的一半进行比较，直到找到目标或者剩余的一半为空。
学习资源
虽然你不太可能在面试中被要求从头实现一个排序算法，但了解不同排序算法的各种时间复杂度是有好处的。
- 读物
- 整理排序算法背后的基础知识，basecs
- 二分搜索法，可汗学院
- 附加(仅当您有时间时)
- 指数简易选择排序，basecs
- 冒泡与冒泡排序，basecs
- 向插入排序点动，basecs
- 理解合并排序(第一部分)，basecs
- 理解合并排序(第二部分)，basecs
- 旋转理解快速排序(第一部分)，basecs
- 旋转理解快速排序(第二部分)，basecs
- 使用计数排序进行线性计数，basecs
- 用基数排序得到排序的根，basecs
时间复杂度
| 算法 | 时间 | 空间 |
|---|---|---|
| 冒泡排序 | O(n 2 | O(1) |
| 插入排序 | O(n 2 | O(1) |
| 选择排序 | O(n 2 | O(1) |
| 快速分类 | o(国家和地区) | O(log(n)) |
| 合并分类 | o(国家和地区) | O(n) |
| 堆排序 | o(国家和地区) | O(1) |
| 计数排序 | O(n + k) | O(k) |
| 基数排序 | O(nk) | O(n + k) |
| 算法 | 大 O |
|---|---|
| 二进位检索 | O(log(n)) |
面试时要注意的事情
一定要知道语言默认排序算法的时间和空间复杂度！时间复杂度几乎肯定是 O(nlog(n))。如果你能说出这种分类，那就加分了。在 Python 中是 Timsort 。
拐角情况
- 空序列
- 单元素序列
- 双元素序列
- 包含重复元素的序列。
技巧
排序后的输入
当一个给定的序列是有序的(升序或降序)，使用二分搜索法应该是你首先想到的事情之一。
对具有有限范围 的输入进行排序
计数排序是一种不基于比较的排序，您可以在预先知道值的范围的数字上使用。例子: H 指数
基本问题
如果你在学习这个话题，这些是需要练习的基本问题。
推荐练习题
这些是在你为题目学习并练习了基本问题后推荐练习的问题。
推荐课程
AlgoMonsterT3】
AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→
寻找编码面试:编码问题的模式
设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→
掌握编码面试:数据结构+算法
这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 19 个小时的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 结账→
