【第七章：高频算法】第26节：高频面试算法 - 基础（上）

大家好，很高兴我们可以继续学习交流Java相关面试题目。本小节开始，我们主要进行高频算法题目的讲解。“手撕算法”应该算是技术岗位最通用的面试题目了。

在各大公司的面试中，有一个最基本的要求，那就是必须写点代码。技术面试一般情况下可以归纳为三大块，即业务逻辑面试，基础技术面试和算法面试。

业务逻辑面试就是让你讲述你的项目，并且进行针对性提问，考察你对项目是否足够熟悉与了解。基础技术面试就比较广了，所有涉及到的相关技术知识点都可以考察。一般情况下，面试官会留出20分钟左右的时间和我们一起研究探讨算法。

对于服务端开发同学来说，算法面试及其重要。在校招的面试中，一个算法题是否有思路并且可以完整的写出来，很多时候都直接决定了这轮面试的结果，因为校招毕竟是相当注重基础的考察。在社招的面试上，本轮的面试结果也会很大程度上受到算法题表现的影响。

为什么算法面试的重要性这么高？

• 首先，算法是一种通用的考察点，任何技术岗面试都可以进行考察。
• 其次，算法包含了太多的逻辑思维，可以考察应聘者思考问题的逻辑和解决问题的能力。
• 最后，连这么有难度的算法题你都可以搞定，那么其他只需要看看写写用用就可以掌握的基础知识和相关技术框架还怕学不会吗？

应该去哪里练习算法题呢？

• 当然是去牛客网啦，牛客网是一个专注于程序员的学习和成长的专业平台，集笔试面试系统、课程教育、社群交流、招聘内推于一体。我们可以在在线编程模块进行算法题的练习，对于找工作是一个不可多得的好帮手。
• 然后是LeetCode，这是一个美国的在线编程网站，上面主要收集了各大IT公司的笔试面试题， LeetCode的主要特点就是按照难易将题目分为了easy、medium和hard三种，并且在LeetCode上将题目进行了分类。在自己练习通过之后可以打开讨论区，看看别人解决问题的思路。

在本次的专刊中，我们主要从下边的七个考察点来交流，精选其中最高频的算法题目与大家进行交流。

• 排序和查找算法
• 单链表
• 二叉树
• 队列和栈
• 字符串
• 数组
• 其它算法

本小节中，我们主要交流探讨排序与查找算法，常见链表和二叉树的考察算法。好了，让我们一起来交流吧。

（1）排序与查找算法：

关于排序和查找算法的考察，在校招面试和社招面试中都是极其热门的，不外乎别的，仅仅是因为这就是最基础并且常用的算法。

排序算法分类：

常见的排序算法从排序方式上可以分为四种，即选择排序，交换排序，插入排序以及归并排序。

• 选择排序：直接选择排序和堆排序
• 交换排序：冒泡排序和快速排序
• 插入排序：直接插入排序，二分插入排序和希尔排序
• 归并排序：归并排序

关于排序算法的考察，考察点包括每一个排序算法的原理（排序方式），时间空间复杂度以及判断其是否稳定（得会分析）。这里我们给出最常见的快速排序的算法实现。

快速排序算法：

快速排序是一种分区交换排序算法。采用分治策略对两个子序列再分别进行快速排序，是一种递归算法。

算法描述：

在数据序列中选择一个元素作为基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为了基准值的最终位置。同时，序列被划分成两个子序列，再分别对两个子序列进行快速排序，直到子序列的长度为1，则完成排序。

举例：

假设要排序的数组是a[6]，长度为7，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

• 设置两个变量i，j，排序开始的时候i=0；j=6；
• 以第一个数组元素作为关键数据，赋值给key，即key=a[0]；
• 从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值，两者交换；
• 从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的值，两者交换；
• 重复第3、4步，直到i=j；此时将key赋值给a[i]；

例如：待排序的数组a的值分别是：（初始关键数据key=49）

此时完成了一趟循环，将49赋值给a[3]，数据分为三组，分别为{27,38,13}{49}{76,96,65}，利用递归，分别对第一组和第三组进行排序，则可得到一个有序序列，这就是快速排序算法。

算法实现：

public void quickSort(int[] num, int left, int right) {
    if (num == null)
        return; //如果左边大于右边，则return，这里是递归的终点，需要写在前面。
    if (left >= right) {
        return;
    }
    int i = left;
    int j = right;
    int temp = num[i]; //此处开始进入遍历循环
    while (i < j) { //从右往左循环
        while (i < j && num[j] >= temp) {//如果num[j]大于temp值，则pass，比较下一个
            j--;
        }
        num[i] = num[j];
        while (i < j && num[i] <= temp) {
            i++;
        }
        num[j] = num[i];
        num[i] = temp; // 此处不可遗漏，将基准值插入到指定位置
    }
    quickSort(num, left, i - 1);
    quickSort(num, i + 1, right);
}

查找算法：

关于查找算法的考察主要是二分查找算法。二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

二分查找算法实现步骤：

• 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功。
• 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前面子表，否则进一步查找后面子表。
• 重复以上过程，直到找到满足条件的记录，使查找成功，或一直到子表不存在为止，此时查找失败。

算法前提：必须采用顺序存储结构；必须按关键字大小有序排列。

实现方式：包含递归实现和非递归实现两种方式。

递归实现方式如下：

private  int halfSearch(int[] a,int left,int right,int target) {
    int mid=left+(right-left)/2; // 防止整型溢出
    int midValue=a[mid];
    if(left<=right){
        if(midValue>target){
            return halfSearch(a, left, mid-1, target);
        }else if(midValue<target) {
            return halfSearch(a, mid+1, right, target);
        }else {
            return mid;
        }
    }
    return -1;
}

非递归实现方式如下：

private  int halfSearch(int[] a,int targe