我说我不会算法，阿里把我挂了。

绝地灬酷狼 2021-08-27 17:38 438阅读 0赞

## 前言 ##

工作已经有一段时间了，有的时候会跟同事们打趣：“**如果你让我现在去手写一个快速排序，我怕是真的写不出来**”。

如果不接触一段时间的算法，真的很容易就忘了。不信？你现在想想你自己能不能手写一个堆排序。

经历过校招的人都知道，**算法和数据结构**都是不可避免的。

在笔试的时候，最主要的就是靠算法题。像拼多多、头条这种大公司，上来就来几道算法题，如果你没AC出来，面试机会都没有。

在面试（现场面或者视频面）的时候也会问算法题，难度肯定是没有笔试的时候那么难的。我们可以想象一个场景，一面面试面到一半，面试官让你反转二叉树，问问现在的自己，你还会吗。

不扯远了，如果还在上大学的同学可以先以**排序**和各种的**基本数据结构**开始入门。

下面来简单介绍一下八大基础排序和基础的数据结构  
![format_png][]

## 冒泡排序 ##

思路：俩俩交换，大的放在后面，第一次排序后最大值已在数组末尾。因为俩俩交换，需要`n-1`趟排序（比如10个数，需要9趟排序）

代码实现要点：**两个for循环，外层循环控制排序的趟数，内层循环控制比较的次数**。**每趟过后，比较的次数都应该要减1**

![format_png 1][]

## 选择排序 ##

思路：找到数组中最大的元素，与数组最后一位元素交换。当只有一个数时，则不需要选择了，因此需要`n-1`趟排序

代码实现要点：**两个for循环，外层循环控制排序的趟数，内层循环找到当前趟数的最大值，随后与当前趟数组最后的一位元素交换**

![format_png 2][]

## 插入排序 ##

思路：将一个元素插入到已有序的数组中，在初始时未知是否存在有序的数据，因此将元素**第一个元素看成是有序的**。与有序的数组进行比较，**比它大则直接放入，比它小则移动数组元素的位置，找到个合适的位置插入**。当只有一个数时，则不需要插入了，因此需要`n-1`趟排序

代码实现：一个for循环内嵌一个while循环实现，外层for循环控制需要排序的趟数，while循环找到合适的插入位置(并且插入的位置不能小于0)

![format_png 3][]

![format_png 4][]

## 快速排序 ##

> 学习快速排序的前提：需要了解递归

思路：在数组中找一个元素(节点)，比它小的放在节点的左边，比它大的放在节点右边。一趟下来，比节点小的在左边，比节点大的在右边。不断执行这个操作….

代码实现：支点取中间，使用L和R表示数组的最小和最大位置。不断进行比较，直到找到比支点小(大)的数，随后交换，不断减小范围。递归L到支点前一个元素(j)。递归支点后一个元素(i)到R元素

![format_png 5][]

## 归并排序 ##

> 学习归并排序的前提：需要了解递归

思路：将两个已排好序的数组合并成一个有序的数组。**将元素分隔开来，看成是有序的数组，进行比较合并**。不断拆分和合并，直到只有一个元素

代码实现：在第一趟排序时实质是两个元素(看成是两个已有序的数组)来进行合并，不断执行这样的操作，最终数组有序，拆分左边，右边，合并…

![format_png 6][]

## 堆排序 ##

> 学习堆排序的前提：需要了解二叉树

思路：堆排序使用到了完全二叉树的一个特性，根节点比左孩子和右孩子都要大，完成**一次建堆**的操作实质上是比较根节点和左孩子、右孩子的大小，大的交换到根节点上，**直至最大的节点在树顶**。随后与数组最后一位元素进行交换

代码实现：只要左子树或右子树大于当前根节点，则替换。替换后会导致下面的子树发生了变化，因此同样需要进行比较，直至各个节点实现父>子这么一个条件

![format_png 7][]

## 希尔排序 ##

思路：希尔排序实质上就是插入排序的增强版，希尔排序将数组分隔成n组来进行插入排序，\*\*直至该数组宏观上有序，\*\*最后再进行插入排序时就不用移动那么多次位置了～

代码思路：希尔增量一般是`gap = gap / 2`，只是比普通版插入排序多了这么一个for循环而已。

![format_png 8][]

## 基数排序(桶排序) ##

思路：基数排序(桶排序)：将数字切割成个、十、百、千位放入到不同的桶子里，放一次就按桶子顺序回收一次，直至最大位数的数字放完～那么该数组就有序了

代码实现：先找到数组的最大值，然后根据最大值/10来作为循环的条件(只要>0，那么就说明还有位数)。**将个位、十位、…分配到桶子上，每分配一次就回收一次**

![format_png 9][]

## 递归 ##

递归在算法里边用得非常非常多，排序算法的快速排序和归并排序就需要用到递归（至少用递归来实现是最方便的）。

想要用递归必须知道两个条件：**递归出口(终止递归的条件)和递归表达式(规律)**

技巧：在递归中常常是将问题**切割成两个部分(1和整体的思想)**，这能够让我们快速找到递归表达式(规律)

![format_png 10][]

汉罗塔实现：

![format_png 11][]

## 基本数据结构 ##

链表、队列、二叉树、栈都是些非常基本的数据结构。针对每种的数据结构都会有对应的算法题，比如说：

*  LeetCode No206：反转链表
 *  LeetCode No20：检验字符串`[]{]}{]{}(`这样的字符串是否有效(对齐)
 *  LeetCode No104：树的最大深度
 *  LeetCode No102：层序遍历树
 *  …

在校招不求字典树、红黑树、图这种数据结构要会，但链表、队列、二叉树、栈这些数据结构的题（LeetCode简单） 还是应该要能做出来。

![img][]

#### 涵盖Java后端所有知识点的开源项目（已有5.8K star）：[https://github.com/ZhongFuCheng3y/3y][https_github.com_ZhongFuCheng3y_3y] ####

如果大家想要**实时**关注我更新的文章以及分享的干货的话，微信搜索**Java3y**。

PDF文档的内容**均为手打**，有任何的不懂都可以直接**来问我**（公众号有我的联系方式）。

![format_png 12][]

![format_png 13][]

![aHR0cHM6Ly90dmExLnNpbmFpbWcuY24vbGFyZ2UvMDA2dE5iUndseTFnYjBuenBuOHo3ZzMwZ28wZ29rYnAuZ2lm][]

![aHR0cHM6Ly90dmExLnNpbmFpbWcuY24vbGFyZ2UvMDA4MzFyU1RseTFnY3Rza203d3lsZzMwOGMwNTJuazUuZ2lm][]

[format_png]: /images/20210827/1a2c2bcf48e14913a83b5af9d478f1f3.png
[format_png 1]: /images/20210827/79a66982a88e4931be7144673bdd405a.png
[format_png 2]: /images/20210827/9e33f6f82b5a4be9b64ceb243507fb84.png
[format_png 3]: /images/20210827/647d9d8f45c446fb8c753f919e527f63.png
[format_png 4]: /images/20210827/bcd89f4732bd474bb68eae5e39b0a462.png
[format_png 5]: /images/20210827/6d0e510986f84531b84195c1f8224442.png
[format_png 6]: /images/20210827/06c50428249148dbb9eee4c7ea21606c.png
[format_png 7]: /images/20210827/edf3253dedf94afca35d94444e37f024.png
[format_png 8]: /images/20210827/c66a5d58041e4214b61adb6928b08215.png
[format_png 9]: /images/20210827/f79272191515423caaa811b46b9228e8.png
[format_png 10]: /images/20210827/12efd7dfcf8a481baf8e2fdf50cb9ee4.png
[format_png 11]: /images/20210827/683c4ebe0f9a404f9a377fb5ac6997e8.png
[img]: /images/20210827/303bc67b8bb24439b3bb374016cc137e.png
[https_github.com_ZhongFuCheng3y_3y]: https://github.com/ZhongFuCheng3y/3y
[format_png 12]: /images/20210827/a698e8c6a0204cf8bd23a13840880707.png
[format_png 13]: /images/20210827/7fdf50b62b18419a8e1f3bb270c311ef.png
[aHR0cHM6Ly90dmExLnNpbmFpbWcuY24vbGFyZ2UvMDA2dE5iUndseTFnYjBuenBuOHo3ZzMwZ28wZ29rYnAuZ2lm]: /images/20210827/c2be2945f2c34cfbab19757b28443742.png
[aHR0cHM6Ly90dmExLnNpbmFpbWcuY24vbGFyZ2UvMDA4MzFyU1RseTFnY3Rza203d3lsZzMwOGMwNTJuazUuZ2lm]: /images/20210827/7b94b0024f2040ab9f4f9456c10fc859.png