【技术小火车】万万没想到！原来你是这样的算法君？！

据说算法正在统治世界？吓得我瓜子都掉了......好吧无稽之谈，你们的神之蔑视脸我先收下了，谁让人家单纯无邪天真可爱说啥信啥呢。别闹了，赶紧言归正传（严肃脸）。虽然没有那么可怖，但是算法的作用自然不必多说。毕竟无论男男女女老老少少，想在计算机这条道路上走得更远，算法都是不可或缺的。

然而算法千千万，又有哪些算法属于“夜空中的那颗星”呢？本文就带领大家驰骋算法世界，为你展现丰富而又独特的算法之美。简言之嘛，就是咱们一起攻略新副本去！那走着？走啥走，赶紧飞吧！前方一大波福利来袭，千万要Hold住哦。

1.由插入排序看如何分析和设计算法

算法的作用自然不用多说，就像编程语言中的“Hello World！”一般，算法学习中第一步便是拿下排序算法。扑克牌玩过不？撇开部分人不说，相信大部分童鞋都热衷于将牌按序号排排好。那么这其中就蕴含着算法的思想：1.手中的扑克牌有2种可能：没有扑克牌（为空）或者有扑克牌且已排好序。2.从桌上抓起一张牌后，从左往右（从右往左）依次进行比较，最终选择一个合适的位置插入。

简单的说，插入排序的精髓在于“逐个比较”。

关于算法的分析也有两个定义：1.输入规模，当考虑的是排序算法时，那么规模就指的是项数；如果考虑的是图算法，那么规模就是顶点数和边数。2.运行时间，名义上来说就是算法执行的时间，但实际上我们在分析一个算法时考量的算法执行的操作数或步数。

关于渐近记号、设计分治算法、分析分治算法、递归和迭代等内容咱就不一一赘述了。

2.由股票收益问题再看分治算法和递归式

如前所述，分治算法三步走：divide、conquer、combine，可以自行通过多个小算法来深化对分治算法的理解哦：二分查找算法、平方算法、斐波那契数以及平方递归算法等。

下面我们探讨一个最大子数组问题。股票，经久不衰的热门话题，那么就由此引入来进一步学习分治算法。举个栗子，股票价格如下所示：

不过嘛，比起股票价格咱们更应该关注价格波动。如果将这个波动定义为数组A，那么问题就转换为寻找A的和最大的非空连续子数组。这种连续子数组就是标题中的最大子数组（maximum subarray）。So可以将原表简化如下：

在这个算法中，常常被说成是“一个最大子数组”而不是“最大子数组”，因为可能有多个子数组达到最大和。

那么使用分治思想解决问题、分析分治算法和渐近记号中的省略问题、借助递归树求解递归式的内容我们也就爽快跳过吧，感兴趣的自己戳去。

3.由招聘问题看随机算法

又是一年招聘季，在这里我们就来当个Boss过把瘾（Yeah）。假如某天，你想雇用一名算法工程师......相信一看大家就知道重点是什么了：费用必须最低。那么解决这个问题的逻辑呢，当然就是：1.从1到n个应聘者中不断地面试；2.如果当前应聘者比上一个更好，则雇用当前应聘者并解雇上一个雇用者。

如果大家理解了上面的描述，那就相当于理解了最坏情况分析。在这个算法中，我们显然不可能每次都去强制控制它的输入，因此便有了随机算法这么一说。所谓随机算法，就是使用排列的顺序随意。选取一个主元，输入的顺序便不重要了。无论所提供的输入是递增排序还是递减排序，亦或是没有排序，都对算法没有影响。我们都会将其打乱，让它们随机分布。

既然选择了这个算法，自然有它挡不住的优点：

1.它的运行时间不依赖于输入序列的顺序；

2.无需对输入序列的发布做任何假设；

3.无论是怎样的输入都不会引发最差的运行情况；

4.而最差的情况却是由随机数产生器决定的。

那么什么样的算法是随机的呢？其行为不仅由输入决定，而且也有随机数生成器产生的数值决定，这种算法就是随机的。

4.五张图带你体会堆算法

What is堆？堆是一类特殊的数据结构的统称，通常被看作一棵树的数组对象。在队列中，调度程序反复提取队列中的第一个作业并运行，因为实际情况中某些时间较短的任务却可能需要等待很长时间才能开始执行，或者某些不短小、但很重要的作业，同样应当拥有优先权。而堆就是为了解决此类问题而设计的数据结构。

二叉堆是一种特殊的堆，是完全二叉树或者近似完全二叉树，满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。当父节点的键值总是大于任何一个子节点的键值时为最大堆，当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。为了更加形象，可以借用带数字的圆圈和线条来表示二叉堆等，但其实都是用数组来表示的。如果根节点在数组中的位置是1，第n个位置的子节点则分别在2n和2n+1位置上。

所以，我们可以：

1.通过MAX-HEAPIFY维护最大堆；

2.通过BUILD-MAX-HEAP构建最大堆；

3.通过HEAPSORT进行堆排序算法。

5.传说中的快排是怎样的

下面咱们来见识下传说中可遇不可求的快速排序（英文名：Quicksort，也作划分交换排序）。快排是一个高效的排序算法，当情况良好时它可以比主要竞争对手的归并排序和堆排序快上大约两三倍。这也是一个分治算法，而且就在原地排序。

所谓原地排序，就是指在原来的数据区域内进行重排，就像插入排序一般。而归并排序就不一样，它需要额外的空间来进行归并排序操作。为了在线性时间与空间内归并，它不能在线性时间内实现就地排序，原地排序对它来说并不足够。而快速排序的优点就在于它是原地的，也就是说它很节省内存。

通过诸多实践童鞋们是不是也发现了：快速排序的运行时间依赖于Partition过程，也就是依赖于划分是否平衡，而归根结底这还是由于输入的元素决定的。

•   如果划分是平衡的，那么快速排序算法性能就和归并排序一样。
•   如果划分是不平衡的，那么快速排序的性能就接近于插入排序。

6.比较排序之外学习新的线性时间排序

通过前面的介绍肯定好多小伙伴顿悟了“在排序的最终结果中，各元素的次序依赖于它们之间的比较”。于是乎，这类排序算法被统称为”比较排序“。比较排序是通过一个单一且抽象的比较运算（比如“小于等于”）读取列表元素，而这个比较运算则决定了每两个元素中哪一个应该先出现在最终的排序列表中。典型的比较排序有：插入排序、选择排序、归并排序、堆排序、快速排序。此外，还有一些非典型性的比较排序：Intro sort、冒泡排序、奇偶排序、双向冒泡排序等。

那么线性时间排序有哪些呢？

1.计数排序：计数排序（counting sort）的思路很简单，就是确定比x小的数有多少个。严谨来讲，计数排序是一个根据比较键值大小的排序算法，它也是个整数排序算法。它通过比较对象的数值来操作，并通过这些计数来确定它们在即将输出的序列中的位置。运行时间是线性的且取决于最大值和最小值之间的差异，当值的变化明显大于数目时就不太适用了。

2.基数排序：基数排序（radix sort）是一个古老的算法，用于卡片排序机上。它可以使用前面介绍的计数排序作为子程序，然而它并不是原址排序。因此当数据过大而内存不太够时，使用它并不是一个明智的选择。

3.桶排序：这倒是一个有趣的算法了，它充分利用了链表的思想。

7.分不清栈和队列？一张图给你完整体会

栈？队列？是不是傻傻分不清了（蚊香眼）？往往容易弄混的就是“后进先出”和“先进先出”了。那么，关于栈和队列下面就直接列出相关操作的伪代码咯。

栈

STACK-EMPTY(S)
1   if S.top==0
2       return TRUE
3   else
4       return FLASE

PUSH(S,k)
1   S.top=S.top+1
2   S[S.top]=x

POP(S)
1   if STACK-EMPTY(S)
2       error "underflow"
3   else
4       S.top=S.top-1
5   return S[S.top+1]

队列

ENQUEUE(Q,x)
1   Q[Q.tail]=x
2   if Q.tail==Q.length
3       Q.tail=1
4   else
5       Q.tail=Q.tail+1

DEQUEUE(Q)
1   x=Q[Q.head]
2   if Q.head=Q.length
3       Q.head=1
4   else
5       Q.head=Q.head+1
6   return x

8.图文搭配诠释三种链表及其哨兵

链表是什么呢？它和前面的栈和队列一般，都是基本的数据结构，其中的各个对象按线性顺序排列。链表主要包括：单向链表、双向链表、循环链表。

我们来研究下不同的链表是如何指引的？

•  单链表中有一个关键字key和指针next，将链表中的一个元素设为x，那么x.key就是它的值，x.next就是链表的后继元素。如果x.next=NIL，那么就说明没有后继元素了，因此x就是链表的尾（tail）。
•  双向链表对比单链表，无非就是多了一个前驱，用x.prev来表示。同样的，x.prev=NIL，表示没有前驱，那么x就是链表的头（head）。而如果头都为空了，那么整个链表也就是空的了。
•  循环链表是双向链表的升级版，就是将链表尾部的元素x的next指向链表的头部y，元素头部的元素y的prev指向链表的尾部x。

关于链表的搜索、插入、删除等问题就不一一说明啦。

既然提到了哨兵，我们也来分析下。哨兵节点常常被用在链表和遍历树中，它并不拥有或引用任何被数据结构管理的数据。常常用哨兵节点来代替null，这样的好处有以下3点：

1.增加操作的速度

2.降低算法的复杂性和代码的大小

3.增加数据结构的鲁棒性

简而言之，哨兵就是为了简化边界条件的处理而存在滴。

【算法】1 由插入排序看如何分析和设计算法：

【算法】2 由股票收益问题再看分治算法和递归式：

【算法】3 由招聘问题看随机算法：

【算法】4 五张图带你体会堆算法：

【算法】5 传说中的快排是怎样的：

【算法】6 比较排序之外学习新的线性时间排序：

【算法】7 分不清栈和队列？一张图给你完整体会：

【算法】8 图文搭配诠释三种链表及其哨兵：