Question

查找和排序都是在程序设计中经常用到的算法。查找相对而言较为简单，不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找。在面试的时候，不管是用循环还是用递归，面试官都期待应聘者能够信手拈来写出完整正确的二分查找代码，否则可能连继续面试的兴趣都没有。面试题8旋转数组的最小数字和面试题38数字在排序数组中出现的次数都可以用二分查找算法解决。

面试小提示：

如果面试题是要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，我们都可以尝试用二分查找算法。

哈希表和二叉排序树查找的重点在于考查对应的数据结构而不是算法。哈希表最主要的优点是我们利用它能够在O（1）时间查找某一元素，是效率最高的查找方式。但其缺点是需要额外的空间来实现哈希表。面试题35第一个只出现一次的字符就是用哈希表的特性来高效查找。与二叉排序树查找算法对应的数据结构是二叉搜索树，我们将在面试题24二叉搜索树的后序遍历序列和面试题27二叉搜索树与双向链表中详细介绍二叉搜索树的特点。

排序比查找要复杂一些。面试官会经常要求应聘者比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣。强烈建议应聘者在准备面试的时候，一定要对各种排序算法的特点烂熟于胸，能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。需要特别强调的是，很多公司的面试官喜欢在面试环节中要求应聘者写出快速排序的代码。应聘者不妨自己写一个快速排序的函数并用各种数据作测试。当测试都通过之后，再和经典的实现做比较，看看有什么区别。

实现快速排序算法的关键在于先在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边。这个函数可以如下实现：

函数RandomInRange用来生成一个在start和end之间的随机数，函数Swap的作用是用来交换两个数字。接下来我们可以用递归的思路分别对每次选中的数字的左右两边排序。下面就是递归实现快速排序的参考代码：

对一个长度为n的数组排序，只需把start设为0、把end设为n－1，调用函数QuickSort即可。

在前面的代码中，函数Partition除了可以用在快速排序算法中，还可以用来实现在长度为n的数组中查找第k大的数字。面试题29数组中出现次数超过一半的数字和面试题30最小的k个数都可以用这个函数来解决。

不同的排序算法适用的场合也不尽相同。快速排序虽然总体的平均效率是最好的，但也不是任何时候都是最优的算法。比如数组本身已经排好序了，而每一轮排序的时候都是以最后一个数字作为比较的标准，此时快速排序的效率只有O（n²）。因此在这种场合快速排序就不是最优的算法。在面试的时候，如果面试官要求实现一个排序算法，那么应聘者一定要问清楚这个排序应用的环境是什么、有哪些约束条件，在得到足够多的信息之后再选择最合适的排序算法。下面来看一个面试的片段：

面试官：请实现一个排序算法，要求时间效率O（n）。

应聘者：对什么数字进行排序，有多少个数字？

面试官：我们想对公司所有员工的年龄排序。我们公司总共有几万名员工。

应聘者：也就是说数字的大小是在一个较小的范围之内的，对吧？

面试官：嗯，是的。

应聘者：可以使用辅助空间吗？

面试官：看你用多少辅助内存。只允许使用常量大小辅助空间，不得超过O（n）。

在面试的时候应聘者不要怕问面试官问题，只有多提问，应聘者才有可能明了面试官的意图。在上面的例子中，该应聘者通过几个问题就弄清楚了需排序的数字在一个较小的范围内，并且还可以用辅助内存。知道了这些限制条件，就不难写出如下的代码了：

公司员工的年龄有一个范围。在上面的代码中，允许的范围是0～99岁。数组timesOfAge用来统计每个年龄出现的次数。某个年龄出现了多少次，就在数组ages里设置几次该年龄，这样就相当于给数组ages排序了。该方法用长度100的整数数组作为辅助空间换来了O（n）的时间效率。