前言

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

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

“经历过校招”的人都知道,算法『和』数据结构<都是不可避免的>。

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

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

不扯远了,如果还在上大学的同学可以先以 排序[<『和』各种的>基本数据结构 开始入门[。我花了 一个[星期将八大基础 排序[『和』链表/二叉树/栈/〖队列〗制作成一份精美的PDF

这份PDF阅读体验肯定是要比公众号『和』各大的博客平台的文章要好的。PDF内容纯手打,有不懂的可以‘来问我’。

下面来简单介绍一下八大基础 排序[『和』基础的数据结构,每种 排序[的思想『和』基础的讲解『和』源码在PDF里边有。

冒泡 排序[

(《思路》):俩俩交换,大的放在后面,第一次 排序[后最大值已在数组末尾。〖因〗为俩俩交换,需要n-1趟 排序[(比如10个数,需要9趟 排序[)

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

选择 排序[

(《思路》):找「到」数组中最大的(元素),与数组最后一位(元素)交换。{当只有 一个[数时},则不需要选择了,因此需要n-1趟 排序[

代码实现要点:两个for循环,外层循环控制 排序[的趟数,“内层循环找「到」当前趟数的最大值”,随后与当前趟数组最后的一位(元素)交换

插入 排序[

(《思路》):“将 一个[(元素)插入「到」已有序的”数组中,【在】初始时未知是否存在有序的数据,因此将(元素)第 一个[(元素)看成是有序的。与有序的数组进行比较,比它大则直接放入,比它小则移动数组(元素)的位置,找「到」个合适的位置插入。{当只有 一个[数时},则不需要插入了,因此需要n-1趟 排序[

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

快速 排序[

学习快速 排序[的前提:“【需要了解『递归』】”

(《思路》):在数组中找 一个[(元素)(节点),“比它小的放在节点的左边”,〖比它大的放在节点右边〗。一趟下来,‘比节点小的在左边’,比节点大的在右边。不断执行这个操作….

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

归并 排序[

学习归并 排序[的前提:“【需要了解『递归』】”

(《思路》):将两个已排好序的数组合并成 一个[有序的数组。将(元素)分隔开来,看成是有序的数组,【进行比较合并】。不断拆分『和』合并,直「到」只有 一个[(元素)

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

堆 排序[

学习堆 排序[的前提:需要了解二叉树

(《思路》):堆 排序[使用「到」了完全二叉树的 一个[特性,根节点比左孩子『和』右孩子都要大,完成一次建堆的操作实质上是比较根节点『和』左孩子、<右孩子的大小>,大的交换「到」根节点上,直至最大的节点在树顶。随后与数组最后一位(元素)进行交换

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

希尔 排序[

(《思路》):希尔 排序[实质上就是插入 排序[的增强版,希尔 排序[将数组分隔成n组来进行插入 排序[,直至该数组宏观上有序,最后再进行插入 排序[时就不用移动那么多次位置了~

代码(《思路》):希尔增量一般是gap = gap / 2,只是比普通版插入 排序[多了这么 一个[for“循环而已”。

基数 排序[(桶 排序[)

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

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

『递归』

『递归』在算法里边用得非常非常多, 排序[算法的快速 排序[『和』归并 排序[就需要用「到」『递归』(至少用『递归』来实现是最方便的)。

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

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

汉罗塔实现:

基本数据结构

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

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

在校招不求字典树、【红黑树】、图这种数据结构要会,“但链表”、〖队列〗、二叉树、栈这些数据结构的题(LeetCode简单) 还是应该要能做出来。

最后

最后想要说明的是, 排序[算法/ 数据结构的代码可能不是最优解[,(代码的实现都是以比较容易理解的方式)去写的。几乎每句代码都有对应的注释,应该是能看懂的。

现在已经工作有一段时间了,‘为什么还来写’最基础的算法『和』数据结构呢,“原因有以下几个”:

  • 我是 一个[对排版有追求的人,如果早期关注我的同学可能会发现,我的GitHub、文章导航的read.me会经常更换。现在的GitHub导航也不合我心意了(【太长了】),并且早期的文章,(说)实话排版也不太行,我决定重新搞一波。
  • 我的文章[会分发好几个平台,但文章发完了可能就没人看了,并且图床很可能因为平台的防盗链就挂掉了。又因为有很多的读者问我:”你能不能把你的文章转成PDF啊?“
  • 我写过很多系列级的文章,这些文章就几乎不会有太大的改动了,就非常适合把它们给”持久化“。

基于上面的原因,我决定把我的系列文章汇总成 一个[PDF/HTML/WORD『文档』。(说)实话,打造这么 一个[『文档』“花了我不少的时间”。为了防止白嫖,关注我的公众号回复「888」〖即可获取〗。

『文档』的内容均为手打,有任何的不懂都可以直接‘来问我’(微信搜索Java3y)

本已收录至我的GitHub《精选文章》,‘欢迎’Star:https://github.com/ZhongFuCheng3y/3y

求点赞 求关注️ 求『分享』