Skip to content

为面试编码排序和搜索备忘单

原文：https://www.techinterviewhandbook.org/algorithms/sorting-searching/

简介

排序是将序列中的元素按顺序重新排列的行为，可以是数字顺序或字典顺序，也可以是升序或降序。

一些基本算法运行在 O(n 2 )中，不应该在面试中使用。在算法面试中，你不太可能需要从头开始实现任何排序算法。相反，您需要使用语言的默认排序函数对输入进行排序，这样您就可以对它们使用二进制搜索。

在一个排序的元素数组上，通过利用它的排序属性，使用二分搜索法可以在比 O(n)更快的时间内完成搜索。二分搜索法将目标值与数组的中间元素进行比较，这将通知算法目标值是位于左半部分还是右半部分，并且对剩余的一半进行比较，直到找到目标或者剩余的一半为空。

学习资源

虽然你不太可能在面试中被要求从头实现一个排序算法，但了解不同排序算法的各种时间复杂度是有好处的。

时间复杂度

算法 时间 空间
冒泡排序 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 用于编码演示。 结账→

回到顶部