32.md

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

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



## 简介[](#introduction "Direct link to heading")

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

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

在一个排序的元素数组上，通过利用它的排序属性，使用二分搜索法可以在比 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 <sup>2</sup> | O(1) |
| 插入排序 | O(n <sup>2</sup> | O(1) |
| 选择排序 | O(n <sup>2</sup> | 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)