一. 概述

　　在程序员这个群体的日常工作中，我们经常会听到一个词----算法;也经常接触一个岗位----算法工程师。那么究竟什么是算法，作为一个程序员又需要掌握哪些算法那?

　　度娘对计算机算法的定义如下:

　　计算机算法是以一步接一步的方式，来详细描述计算机该如何将输入转化为所要求的输出的过程。或者说，算法是对计算机上执行的计算过程的具体描述。

　　这个解释有些小伙伴可能不是很能理解，那索尔就用一个容易理解例子给大家说一下：

　　比如有一个数组，存储了10个随机存入的整数，我们想对这个数组进行排序。在这个排序的过程中，其实就用到了算法--排序算法。

　　再比如我们想要在一组数据中找到某个具体的数据，这个查找的过程也会用到算法--查找算法。

　　二. 常用算法

　　作为一个程序员，我们在开发过程中还真的需要了解和使用一些算法来帮助我们完成编码工作，下面索尔就来给大家介绍几种常用的算法：

　　冒泡排序

　　选择排序

　　插入排序

　　快速排序

　　二分查找

　　二叉树算法

　　Dijkstra算法

　　字符串查找算法

　　1. 冒泡排序

　　1.1 算法简介

　　冒泡排序(Bubble Sort)是一种较为简单的排序算法。它会重复地走访要排序的元素列，依次比较两个相邻的元素，如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作会重复地进行，直到没有相邻元素需要交换为止，也就是说直到该元素列完成排序。

　　这个算法之所以叫这个名字，是因为越小的元素经过交换会慢慢“浮”到数列的最顶端(升序或降序排列)，就如同碳酸饮料中二氧化碳的气泡最终会上浮到最顶端一样，故名“冒泡排序”。

　　1.2 冒泡原理

　　冒泡算法的基本原理就是比较相邻的两个元素，如果第一个比第二个大，就交换他们两个。然后对每一对相邻的两个元素进行同样的工作，从第一对开始，直到最后的一对结尾，等到最后的元素应该就是最大的元素。

　　我们只需要针对所有的元素，重复以上的步骤，除了最后一个。所以持续对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较为止。

　　我们可以参考下图来理解冒泡算法：

　　2. 选择排序

　　选择排序(Selection sort)是一种简单直观的排序算法，这是一种不稳定的排序方法，其工作原理是：

　　第一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置;

　　然后再从剩余的未排序元素中寻找到最小(大)的元素，然后再放到已排序的序列末尾;

　　以此类推，直到全部待排序的数据元素的个数为零。

　　3. 插入排序

　　3.1 算法简介

　　插入排序一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

　　3.2 插入原理

　　插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

　　插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

　　4. 快速排序

　　快速排序(Quicksort)是对冒泡排序算法的一种改进，其基本原理如下：

　　设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据(通常选用数组的第一个数)作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。这样一趟快速排序的算法是：

　　设置两个变量i、j，排序开始的时候：i=0，j=N-1;

　　以第一个数组元素作为关键数据，赋值给key，即key=A[0];

　　从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换;

　　从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换;

　　重复第3、4步，直到i==j;(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束)。

　　5. 二分查找

　　5.1 算法简介

　　二分查找也称折半查找(Binary Search)，这是一种效率较高的查找方法。但折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

　　5.2 算法原理

　　首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功;

　　否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表;

　　重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

　　6. 二叉树算法

　　6.1 算法简介

　　二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^(i-1)个节点。深度为k的二叉树至多有2^k- 1个结点; 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。

　　二叉树是每个节点最多有两个子树的有序树，通常子树被称作“左子树”(left subtree)和"右子树"(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

　　6.2 算法特性

　　二叉树算法通常具有如下特性：

　　(1). 在二叉树中，第i层的结点总数不超过2^(i-1);

　　(2). 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点;

　　(3). 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;

　　(4). 具有n个结点的完全二叉树的深度为int(log2n)+1

　　(5). 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果I>1，则其父结点的编号为I/2;如果2*IN，则无左儿子;如果2*I+1N，则无右儿子。

　　(6). 给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

　　7. Dijkstra算法

　　迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

　　Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

　　Dijkstra算法可以解决如下问题：

　　在有向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短值。

　　8. 字符串搜索算法

　　字符串搜索算法是一种搜索算法，目的为在一长字符串中找出其是否包含某字符串。

　　字符串搜索算法工作的原理如下：

　　遍历目标字符串，使用指定的字符逐个比较，如果发现有相同的，返回这个元素的索引并结束遍历;如果从头比较到结束都没有相同的，返回-1。

　　例如问题：在abcdefg中查找cd：

　　第一步：ab与cd比较;

　　第二步：bc与cd比较;

　　第三步：cd与cd比较

　　上面的操作会返回cd中c字符的索引。

　　字符串比较算法比较简单，效率也比较低，但是这种思想适合很多搜索场景。

　　三. 结语

　　上面索尔给大家介绍了一些基础的常用算法，其实算法也是一门独立的学科，通常和数据结构一起学习，合适的算法在特定场景下能够帮助我们更好更快的完成工作。

　　如果大家对Java算法感兴趣可以联系千锋索尔老师，我们一起来体味算法中的奥妙。