一般来说，前四个效率比较高，中间两个差强人意，后三个比较差（只要N比较大，这个算法就动不了了）。
线性阶主要要分析循环结构的运行情况，如下所示：
接着看如下代码：
下面的代码是循环嵌套：
分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。顾名思义，分而治之。一般分为以下三个过程：
比较经典的应用就是归并排序(MergeSort)以及快速排序(QuickSort)等。我们来从归并排序理解分治思想，归并排序就是将待排序数组不断二分为规模更小的子问题处理，再将处理好的子问题合并起来。
贪心算法是动态规划算法的一个子集，可以更高效解决一部分更特殊的问题。实际上，用贪心算法解决问题的思路，并不总能给出最优解。因为它在每一步的决策中，选择目前最优策略，不考虑全局是不是最优。
贪心算法+双指针求解
使用回溯法进行求解，回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。究其本质，其实就是枚举。
虽然动态规划的最终版本(降维再去维)大都不是递归，但解题的过程还是离开不递归的。新手可能会觉得动态规划思想接受起来比较难，确实，动态规划求解问题的过程不太符合人类常规的思维方式，我们需要切换成机器思维。使用动态规划思想解题，首先要明确动态规划的三要素。动态规划三要素：
就是一个一个依次查找。
二分查找又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。如果待查值小于候选区中间值，则只需比较中间值左边的元素，减半查找范围。依次类推依次减半。
JAVA代码如下：
插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。将折半查找中的求mid索引的公式，low表示左边索引left，high表示右边索引right，key就是前面我们讲的findVal。
注意事项
深度优先搜索（Depth-FirstSearch/DFS）是一种优先遍历子节点而不是回溯的算法。
DFS解决的是连通性的问题。即给定两个点，一个是起始点，一个是终点，判断是不是有一条路径能从起点连接到终点。起点和终点，也可以指的是某种起始状态和最终的状态。问题的要求并不在乎路径是长还是短，只在乎有还是没有。
代码案例
BFS一般用来解决最短路径的问题。和深度优先搜索不同，广度优先的搜索是从起始点出发，一层一层地进行，每层当中的点距离起始点的步数都是相同的，当找到了目的地之后就可以立即结束。广度优先的搜索可以同时从起始点和终点开始进行，称之为双端BFS。这种算法往往可以大大地提高搜索的效率。
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
基本思想
通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是'起点s到该顶点的路径'。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。...重复该操作，直到遍历完所有顶点。
操作步骤
迪杰斯特拉算法图解
以上图G4为例，来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)：
循环遍历多次每次从前往后把大元素往后调，每次确定一个最大(最小)元素，多次后达到排序序列。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤
代码实现
以下是冒泡排序算法复杂度:
最好情况
最坏情况
空间复杂度
O(n2)
O(n)
O(1)
Tips:由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置,它并不改变相同元素之间的相对顺序,因此它是稳定的排序算法。
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
/***选择排序*描述：每轮选择出最小值，然后依次放置最前面**@paramarr待排序数组*/publicstaticint[]selectSort(int[]arr){for(inti=0;i
选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n2/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。唯一值得高兴的是，它并不耗费额外的内存空间。
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序由于操作不尽相同，可分为直接插入排序、折半插入排序(又称二分插入排序)、链表插入排序、希尔排序。
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
插入排序复杂度：
Tips：由于直接插入排序每次只移动一个元素的位，并不会改变值相同的元素之间的排序，因此它是一种稳定排序。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
/***希尔排序*1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）*2.按增量序列个数k，对序列进行k趟排序；*3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。*仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。**@paramarr待排序数组*/publicstaticint[]shellSort(int[]arr){intgap=arr.length/2;//不断缩小gap，直到1为止for(;gap>0;gap/=2){//使用当前gap进行组内插入排序for(intj=0;(j+gap)
O(nlog2n)
Tips：希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者RobertSedgewick提出的。
简介
基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
场景使用
应用场景：内存少的时候使用，可以进行并行计算的时候使用。
步骤：
a.递归法（假设序列共有n个元素）
①.将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素；②.将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素；③.重复步骤②，直到所有元素排序完毕。
b.迭代法
①.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列②.设定两个指针，最初位置分别为两个已经排序序列的起始位置③.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置④.重复步骤③直到某一指针到达序列尾⑤.将另一序列剩下的所有元素直接复制到合并序列尾
以下是归并排序算法复杂度:
O(nlogn)
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C.A.R.Hoare在1962年提出。基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
O(1)（原地分区递归版）
Tips:同选择排序相似,快速排序每次交换的元素都有可能不是相邻的,因此它有可能打破原来值为相同的元素之间的顺序.因此,快速排序并不稳定。
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
以下是基数排序算法复杂度，其中k为最大数的位数：
O(d*(n+r))
O(n+r)
Tips:基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。
对于堆排序，首先是建立在堆的基础上，堆是一棵完全二叉树，还要先认识下大根堆和小根堆，完全二叉树中所有节点均大于(或小于)它的孩子节点，所以这里就分为两种情况：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。
动图演示
O(n\log_{2}n)
Tips:由于堆排序中初始化堆的过程比较次数较多,因此它不太适用于小序列.同时由于多次任意下标相互交换位置,相同元素之间原本相对的顺序被破坏了,因此,它是不稳定的排序.
算法分析
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序(Bucketsort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
/***桶排序算法**@paramarr待排序数组*/publicstaticint[]bucketSort(int[]arr){//计算最大值与最小值intmax=Integer.MIN_VALUE;intmin=Integer.MAX_VALUE;for(intvalue:arr){max=Math.max(max,value);min=Math.min(min,value);}//计算桶的数量intbucketNum=(max-min)/arr.length+1;List