# 为面试编码排序和搜索备忘单
> 原文:
## 简介[](#introduction "Direct link to heading")
排序是将序列中的元素按顺序重新排列的行为,可以是数字顺序或字典顺序,也可以是升序或降序。
一些基本算法运行在 O(n 2 )中,不应该在面试中使用。在算法面试中,你不太可能需要从头开始实现任何排序算法。相反,您需要使用语言的默认排序函数对输入进行排序,这样您就可以对它们使用二进制搜索。
在一个排序的元素数组上,通过利用它的排序属性,使用二分搜索法可以在比 O(n)更快的时间内完成搜索。二分搜索法将目标值与数组的中间元素进行比较,这将通知算法目标值是位于左半部分还是右半部分,并且对剩余的一半进行比较,直到找到目标或者剩余的一半为空。
## 学习资源[](#learning-resources "Direct link to heading")
虽然你不太可能在面试中被要求从头实现一个排序算法,但了解不同排序算法的各种时间复杂度是有好处的。
* 读物
* [整理排序算法背后的基础知识](https://medium.com/basecs/sorting-out-the-basics-behind-sorting-algorithms-b0a032873add),basecs
* [二分搜索法](https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/),可汗学院
* 附加(仅当您有时间时)
* [指数简易选择排序](https://medium.com/basecs/exponentially-easy-selection-sort-d7a34292b049),basecs
* [冒泡与冒泡排序](https://medium.com/basecs/bubbling-up-with-bubble-sorts-3df5ac88e592),basecs
* [向插入排序](https://medium.com/basecs/inching-towards-insertion-sort-9799274430da)点动,basecs
* [理解合并排序(第一部分)](https://medium.com/basecs/making-sense-of-merge-sort-part-1-49649a143478),basecs
* [理解合并排序(第二部分)](https://medium.com/basecs/making-sense-of-merge-sort-part-2-be8706453209),basecs
* [旋转理解快速排序(第一部分)](https://medium.com/basecs/pivoting-to-understand-quicksort-part-1-75178dfb9313),basecs
* [旋转理解快速排序(第二部分)](https://medium.com/basecs/pivoting-to-understand-quicksort-part-2-30161aefe1d3),basecs
* [使用计数排序](https://medium.com/basecs/counting-linearly-with-counting-sort-cd8516ae09b3)进行线性计数,basecs
* [用基数排序](https://medium.com/basecs/getting-to-the-root-of-sorting-with-radix-sort-f8e9240d4224)得到排序的根,basecs
## 时间复杂度[](#time-complexity "Direct link to heading")
| 算法 | 时间 | 空间 |
| --- | --- | --- |
| 冒泡排序 | 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)) |
## 面试时要注意的事情[](#things-to-look-out-for-during-interviews "Direct link to heading")
一定要知道语言默认排序算法的时间和空间复杂度!时间复杂度几乎肯定是 O(nlog(n))。如果你能说出这种分类,那就加分了。在 Python 中是 [Timsort](https://en.wikipedia.org/wiki/Timsort) 。
## 拐角情况[](#corner-cases "Direct link to heading")
* 空序列
* 单元素序列
* 双元素序列
* 包含重复元素的序列。
## 技巧[](#techniques "Direct link to heading")
### 排序后的输入[](#sorted-inputs "Direct link to heading")
当一个给定的序列是有序的(升序或降序),使用二分搜索法应该是你首先想到的事情之一。
### 对具有有限范围 [](#sorting-an-input-that-has-limited-range "Direct link to heading") 的输入进行排序
[计数排序](https://en.wikipedia.org/wiki/Counting_sort)是一种不基于比较的排序,您可以在预先知道值的范围的数字上使用。例子: [H 指数](https://leetcode.com/problems/h-index/)
## 基本问题[](#essential-questions "Direct link to heading")
如果你在学习这个话题,这些是需要练习的基本问题。
* [二分搜索法](https://leetcode.com/problems/binary-search/)
* [在旋转排序数组中搜索](https://leetcode.com/problems/search-in-rotated-sorted-array/)
## 推荐练习题[](#recommended-practice-questions "Direct link to heading")
*这些是在你为题目学习并练习了基本问题后推荐练习的问题。*
* [排序矩阵中的第 k 个最小元素](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/)
* [搜索 2D 矩阵](https://leetcode.com/problems/search-a-2d-matrix/)
* [数组中第 k 个最大的元素](https://leetcode.com/problems/kth-largest-element-in-an-array/)
* [在旋转排序数组中寻找最小值](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)
* [两个排序数组的中值](https://leetcode.com/problems/median-of-two-sorted-arrays/)
## 推荐课程[](#recommended-courses "Direct link to heading")
### [AlgoMonster](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)[T3】](#algomonster "Direct link to heading")
AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式,并有内容帮助你快速修改基本的数据结构和算法。最重要的是,AlgoMonster 不是基于订阅的——支付一次性费用,就可以获得**终身访问**。 [**今天加入七折优惠→**](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)
### [寻找编码面试:编码问题的模式](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)[](#grokking-the-coding-interview-patterns-for-coding-questions "Direct link to heading")
设计大师的这门课程扩展了推荐练习题中的问题,但从问题模式的角度来进行练习,这是一种我也同意的学习方法,我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题,并提供这些语言的示例解决方案以及一步一步的可视化。**学习和理解模式,而不是背答案!** [**现在获得终身使用权→**](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)
### [掌握编码面试:数据结构+算法](https://fxo.co/DQpY)[](#master-the-coding-interview-data-structures--algorithms "Direct link to heading")
这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星,21.5k 评分,135k 学生),包含了价值 **19 个小时**的内容。像技术面试手册一样,它超越了编码面试,涵盖了简历,非技术面试,谈判。是一个全包!请注意,JavaScript 用于编码演示。 [**结账→**](https://fxo.co/DQpY)