排序是将序列中的元素按顺序重新排列，无论是数值还是字典序，升序还是降序。
许多基本算法的时间复杂度为O(n^2)，在面试中不应使用。在算法面试中，你不太可能需要在面试中实现任何排序算法的原始版本。相反，你需要使用你的语言默认的排序函数对输入进行排序，以便可以使用二分查找它们。
在一个已排序的元素数组上，利用其已排序属性，可以通过使用二分查找在O(n)时间复杂度内搜索它们。二分查找将目标值与数组的中间元素进行比较，这通知算法目标值位于左半部分还是右半部分，并且这个比较继续在剩余的一半中进行，直到找到目标值或剩余的一半为空。
学习资源
虽然你在面试中不太可能被要求从头开始实现一个排序算法，但了解不同排序算法的不同时间复杂度是很好的。
- 阅读书籍
- 排序算法基础，basecs
- 二分查找，Khan Academy
- 其他（如果你有时间）
- 指数级简单的选择排序，basecs
- 冒泡排序的膨胀，basecs
- 插入排序的缓慢进展，basecs
- 理解归并排序（第一部分），basecs
- 理解归并排序（第二部分），basecs
- 理解快速排序的枢轴（第一部分），basecs
- 理解快速排序的枢轴（第二部分），basecs
- 线性计数计数排序，basecs
- 通过基数排序深入理解排序，basecs
- 视频
- 堆排序（幻灯片），Samuel Albanie，剑桥大学
- 快速排序（幻灯片），Samuel Albanie，剑桥大学
- 比较排序的下界（幻灯片），Samuel Albanie，剑桥大学
- 计数排序（幻灯片），Samuel Albanie，剑桥大学
- 基数排序（幻灯片），Samuel Albanie，剑桥大学
- 桶排序（幻灯片），Samuel Albanie，剑桥大学
时间复杂度
| 算法 | 时间 | 空间 |
|---|---|---|
| 冒泡排序 | O(n^2) | O(1) |
| 插入排序 | O(n^2) | O(1) |
| 选择排序 | O(n^2) | O(1) |
| 快速排序 | O(nlog(n)) | O(log(n)) |
| 归并排序 | O(nlog(n)) | O(n) |
| 堆排序 | O(nlog(n)) | O(1) |
| 计数排序 | O(n + k) | O(k) |
| 基数排序 | O(nk) | O(n + k) |
| 算法 | Big-O |
|---|---|
| 二分搜索 | O(log(n)) |
面试时需要注意的事项
确保你知道语言默认排序算法的时间和空间复杂度！时间复杂度几乎肯定是O(nlog(n)。如果可以指出排序算法的名称，会额外加分。在Python中，它是TimSort。在Java中，Timsort用于排序对象，Dual-Pivot Quicksort用于排序基本类型。
边缘情况
- 空序列
- 有一个元素的序列
- 有两个元素的序列
- 包含重复元素的序列。
技巧
排序输入
当给定的序列是有序的（无论是升序还是降序）时，你应该首先想到的使用二分搜索方法。
对范围有限的输入进行排序
计数排序 是一种非比较型排序算法，适用于事先知道数值范围的数字。示例：H-指数
基本问题
如果你正在为这个主题学习，这些是必须要练习的基本问题。
推荐练习题
在你已经为这个主题学习和练习了基本问题之后，这里是推荐的练习题。
推荐课程
import AlgorithmCourses from '../_courses/AlgorithmCourses.md'