一，介绍分治算法主要包含两个步骤：分、治。分，就是递归地将原问题分解成小问题；治则是：在解决了各个小问题之后(各个击破之后)合并小问题的解，从而得到整个问题的解 二，分治递归表达式分治算法一般都可以写出一个递归表达式；比如经典的归并排序的递归表达式：T(N)=2T(N/2)+O(N)T(N)代表整个原问题，采用了分治解决方案后，它可以表示成：①分解成了两个规模只有原来一半(N/2)的子问题:T(N/2)②当解决完这两个子问题T(N/2)之后，再合并这两个子问题需要的代价是O(N)递归表达式的解就是该算法的时间复杂度。关于某些特定形式的递归表达式，求解时，是可以直接套公式的：T(N)=aT(N/b)+Θ(N^K)表示将原问题分解成a个规模大小为N/b的子问题，合并这a个子问题的代价是Θ(N^K) （N^k表示N的k次方）T(N)的解有以下三种情况：1)T(N)=O(N^logba)  当a>bk时2)T(N)=O(NklogN)  当a=bk时3)T(N)=O(Nk)  当a&l...

一，希尔排序算法介绍①希尔排序又称缩小增量排序，它本质上是一个插入排序算法。为什么呢？因为，对于插入排序而言，插入排序是将当前待排序的元素与前面所有的元素比较，而希尔排序是将当前元素与前面增量位置上的元素进行比较，然后，再将该元素插入到合适位置。当一趟希尔排序完成后，处于增量位置上的元素是有序的。②希尔排序算法的效率依赖于增量的选取假设增量序列为h(1)，h(2).....h(k)，其中h(1)必须为1，且h(1)<h(2)<...h(k)。第一趟排序时在增量为h(k)的各个元素上进行比较；第二趟排序在增量为h(k-1)的各个元素上进行比较;..........最后一趟在增量h(1)上进行比较。由此可以看出，每进行一趟排序，增量是一个不断减少的过程，因此称之为缩小增量。当增量减少到h(1)=1时，这里完全就是插入排序了，而在此时，整个元素经过前面的k-1趟排序后，已经变得基本有序了，而我们知道，对于插入排序而言，当待排序的数组基本有序时，插入排序的效率是非常高的。因此，希尔排序就是利用“增量”技巧将插入排序的平均时间复杂度O(N^2)降低为亚二次方。...

一，快速排序介绍快速排序与归并排序一样，也是基于分治的递归算法，体现在：在每一趟快速排序中，需要选出枢轴元素，然后将比枢轴元素大的数组元素放在枢轴元素的右边，比枢轴元素小的数组元素都放在枢轴元素的左边。然后，再对分别对枢轴元素左边和枢轴元素右边的元素进行快速排序。 二，快速排序算法分析 ①相比于直接插入排序，快排合适于数据量大（上百万）的情形，而插入排序适合于小数据量的情形。因为，在数据量小的情形下，快排的递归是需要一定的开销的。②相比于归并排序，归并排序的比较次数要比快速排序少，但是它需要一个额外的临时数组，而且移动的元素多。而快速排序不需要显示地声明一个临时数组，它用的是递归栈。在C++中使用它来作为标准的排序程序，而JAVA中则是用归并排序来作为标准的排序（比如java.util.Arrays.java中的sort(T[])方法使用的就是归并排序）。③快速排序主要有两个基本操作：一是选取枢轴元素，另一个则是递归分割数组。枢轴元素的选取对快速排序的效率至关重要，因为它决定了递归的深度。如果枢轴元素刚好处于数组的中间值，那么，数组在分割时就分成了平均的两部分。这样...

一，归并排序介绍归并排序是一个典型的基于分治的递归算法。它不断地将原数组分成大小相等的两个子数组(可能相差1)，最终当划分的子数组大小为1时(下面代码第17行left小于right不成立时)，将划分的有序子数组合并成一个更大的有序数组。为什么是有序子数组？？？归并排序的递归公式：T(N)=2T(N/2)+O(N)从公式中可以看出：将规模为N的原问题分解成两个规模N/2的两个子问题；并且，合并这两个子问题的代价是O(N)---[后面的+O(N)表示合并的代价]  二，归并排序算法分析 归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。它将数组平均分成两部分:center=(left+right)/2，当数组分得足够小时---数组中只有一个元素时，只有一个元素的数组自然而然地就可以视为是有序的，此时就可以进行合并操作了。因此，上面讲的合并两个有序的子数组，是从只有一个元素的两个子数组开始合并的。合并后的元素个数：从1-->2-->4-->8......比如初始数...

一，堆排序介绍堆是一个优先级队列，对于大顶堆而言，堆顶元素的权值最大。将待排序的数组建堆，然后不断地删除堆顶元素，就实现了排序。关于堆，参考：数据结构--堆的实现之深入分析下面的堆排序算法将数组中的元素从小到大排序，用大顶堆来实现。 二，堆排序算法分析 现给定了一维数组，需要将数组中的元素使用堆排序。首先，得创建一个堆，可以在这个给定的一维数组上建堆。对N个元素建堆的时间复杂度为O(N)堆排序具体的细节实现有两种方式：一种方式是将堆顶元素删除后，放到一个辅助数组中，然后进行堆调整使之成为一个新堆。接下来，继续删除堆顶元素，直至将堆中所有的元素都出堆，此时排序完成。这种方式需要一个额外的辅助空间O(N)另一种方式是：将每次删除的堆顶元素放到数组的末尾。因为，对于堆的基本操作delMin/delMax而言（delMin针对的是小顶堆，delMax针对的是大顶堆，原理一样）是将堆中的最后一个元素替换堆顶元素，然后向下进行堆调整。因此，可以利用这个特点将每次删除的堆顶元素保存在数组末尾，当所有的元素都出堆后，数组就排好序了。这种方式不需要额外的辅助空间，空间复杂度为O(1)...

一，插入排序介绍 插入排序是基于比较的排序。所谓的基于比较，就是通过比较数组中的元素，看谁大谁小，根据结果来调整元素的位置。因此，对于这类排序，就有两种基本的操作：①比较操作；②交换操作其中，对于交换操作，可以优化成移动操作，即不直接进行两个元素的交换，还是用一个枢轴元素(tmp)将当前元素先保存起来，然后执行移动操作，待确定了最终位置后，再将当前元素放入合适的位置。（下面的插入排序就用到了这个技巧）--因为，交换操作需要三次赋值，而移动操作只需要一次赋值！有些排序算法，比较次数比较多，而移动次数比较少，而有些则相反。比如，归并排序和快速排序，前者移动次数比较多，而后者比较次数比较多。 这里主要介绍插入排序 二，插入排序算法分析插入排序算法有种递归的思想在里面，它由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的。然后第一趟对下标1处的元素进行排序，保证数组[0,1]上的元素有序；第二趟对下标2处的元素进行排序，保证数组[0,2]上的元素有序；..........第N-1趟对下标N-1处的元素进行排序，保证数组[0,N-1]上...

都是基于内存的排序算法，包括插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序14年在网易Blog上写的，现把它放到这里。  一，直接插入排序    总体思路：位于表中后面的元素依次与表中前面的元素比较，若比之小，则还需继续和更前面的元素比较，直至遇到一个比它大的元素或者比较到第一个元素(哨兵)了。               ①先将第一个元素视为有序，第二个元素与第一个元素比较，若比第一个元素小，则插入到第一个元素之前。第三个元素依次与第二个元素、第一个元素比较（前三个元素有序）；第四个元素依次与第三个、第二个、第一个元素比较，插入到合适位置以形成一个有序表（即此时前四个元素有序）因此，直接插入排序算法是逐步地形成一个有序序列的。也即在表的前头形成一个局部有序序列。       ②不论初始...

一，介绍本文介绍使用Kruskal算法求解无向图的最小生成树。Kruskal是一个贪心算法，并且使用了并查集这种数据结构。关于并查集的介绍，参考：数据结构--并查集的原理及实现 二，构造一个无向图图，肯定有顶点和边。由于求解最小生成树，故边还需要有权值。此外，对于每一条边，需要找到与它相关联的两个顶点，因为在将这条边加入到最小生成树时需要判断这两个顶点是否已经连通了。顶点类定义如下：1privateclassVertex{2privateStringvertexLabel;3privateList<Edge>adjEdges;//邻接表45publicVertex(StringvertexLabel){6this.vertexLabel=vertexLabel;7adjEdges=newLinkedList<Edge>();8}9}表明，图是采用邻接表的形式存储的。边类的定义如下：1privateclassEdgeimplementsComparable<Edge>{2privateVertexstartVertex;3privateVer...

一，介绍什么是二项队列，为什么会用到二项队列？与二叉堆一样，二项队列也是优先级队列的一种实现方式。在 数据结构--堆的实现之深入分析的末尾，简单地比较了一下二叉堆与二项队列。对于二项队列而言，它可以弥补二叉堆的不足:merge操作的时间复杂度为O(N)。二项队列的merge操作的最坏时间复杂度为O(logN)。二项队列的合并操作为什么是O(logN)？因为：对于N个结点的二项队列，最多只有logN棵二项树。而合并操作就是合并两棵高度相同的二项树。（合并操作是指将二个二项队列合并，合并这两个二项队列中高度相同的二项树） 二，二项队列的基本操作及实现在详细介绍二项的队列的基本操作之前，先了解下二项队列这种数据结构：1）一个二项队列是若干棵树的集合。也就是说，二项队列不仅仅是一棵树，而是多棵树，并且每一棵树都遵守堆序的性质，所谓堆序的性质，就是指每个结点都比它的左右子树中结点要小（小顶堆）。这棵树称为“二项树”2）二项队列中的树高度不同，一个高度至多存在一棵二项树。将高度为0的二项树记为B(0)，高度为k的二项树记为B(k)也就是说，对于k>...

一，介绍以前在学习堆时，写了两篇文章：数据结构--堆的实现(上)  和  数据结构--堆的实现(下)， 感觉对堆的认识还是不够。本文主要分析数据结构堆(讨论小顶堆)的基本操作的一些细节，比如insert(插入)操作和deleteMin(删除堆顶元素)操作的实现细节、分析建堆的时间复杂度、堆的优缺点及二叉堆的不足。 二，堆的实现分析堆的物理存储结构是一维数组，逻辑存储结构是完全二叉树。堆的基本操作有：insert--向堆中插入一个元素；deleteMin--删除堆顶元素故堆的类结构如下：publicclassBinaryHeap<TextendsComparable<?superT>>{privateT[]array;privateintcurrentSize;publicBinaryHeap(){}publicBinaryHeap(T[]array){}publicvoidinsert(Tx){//dosomething}publicTdeleteMin(){}//otheroperations.......

一，问题描述在英文单词表中，有一些单词非常相似，它们可以通过只变换一个字符而得到另一个单词。比如：hive-->five；wine-->line；line-->nine；nine-->mine.....那么，就存在这样一个问题：给定一个单词作为起始单词(相当于图的源点)，给定另一个单词作为终点，求从起点单词经过的最少变换(每次变换只会变换一个字符)，变成终点单词。这个问题，其实就是最短路径问题。由于最短路径问题中，求解源点到终点的最短路径与求解源点到图中所有顶点的最短路径复杂度差不多，故求解两个单词之间的最短路径相当于求解源点单词到所有单词之间的最短路径。 给定所有的英文单词，大约有89000个，我们需要找出通过单个字母的替换可以变成至少15个其他单词的单词？程序如何实现？给定两个单词，一个作为源点，另一个作为终点，需要找出从源点开始，经过最少次单个字母替换，变成终点单词，这条变换路径中经过了哪些单词？比如：(zero-->five)：（zero-->hero-->here-->hire-->five） 二，算法...

一，问题描述给出一个无向图，指定无向图中某个顶点作为源点。求出图中所有顶点到源点的最短路径。无向图的最短路径其实是源点到该顶点的最少边的数目。本文假设图的信息保存在文件中，通过读取文件来构造图。文件内容的格式参考这篇文章第一部分。 二，算法实现思路无向图的最短路径实现相对于带权的有向图最短路径实现要简单得多。源点的最短路径距离为0，从源点开始，采用广度优先的顺序，首先将与源点邻接的顶点的路径求出，然后再依次求解图中其他顶点的最短路径。由于顶点的最短路径的求解顺序是一个广度优先的顺序，因此需要一个辅助队列。初始时，将源点的最短路径距离设置为0，将源点入队列。然后，在一个while循环中，从队列中弹出顶点，遍历该顶点的邻接点，若该邻接点的距离未被更新过（表示该邻接点未被访问过），更新邻接点的最短路径距离为该顶点的距离加上1，并将所有的邻接点入队列。 三，最短路径算法的实现感觉该算法的实现与二叉树的层序遍历，有向图的拓扑排序算法实现都非常的相似。他们都采用了广度的思想在里面。广度优先的思想就是：处理完某个顶点后，去处理该顶点的所有邻接点，处理完它的邻接点后，再去处理更远（...

一，问题描述给定一个有向图G=（V,E），将之进行拓扑排序，如果图有环，则提示异常。要想实现图的算法，如拓扑排序、最短路径……并运行看输出结果，首先就得构造一个图。由于构造图的方式有很多种，这里假设图的数据存储在一个文件中，每一行包含如下的信息：LinkID,SourceID,DestinationID,Cost其中，LinkID为该有向边的索引，SourceID为该有向边的起始顶点的索引，DestinationID为该有向边的终止顶点的索引，Cost为该有向边的权重。0,0,1,11,0,2,22,0,3,13,2,1,34,3,1,15,2,3,16,3,2,1(以上示例引用自网上，该图仅用来表示存储图信息的文件内容的格式，对拓扑排序而言，上图显然存在环)对于以下的拓扑排序程序，只用到了SourceID，和DestionatinID这两个字段。拓扑序列以顶点的索引表示。后续会实现无向图的最短路径算法，就会用到Cost这个字段啦！！！ 二，算法实现思路拓扑排序，其实就是寻找一个入度为0的顶点，该顶点是拓扑排序中的第一个顶点序列，将之标记删除，然后...

一，问题描述实现二叉树的层序遍历--从根开始，依次向下，对于每一层从左向右遍历。 二，算法分析层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列，而先、中、后序需要用到栈。因此，先、中、后序遍历可以采用递归方式来实现，而层序遍历则没有递归方式。算法步骤：初始时，根结点入队列然后，while循环判断队列不空时，弹出一个结点，访问它，并把它的所有孩子结点入队列。 三，代码实现1publicvoidlevelTraverse(BinarySearchTree<T>tree){2levelTraverse(tree.root);3}4privatevoidlevelTraverse(BinaryNode<T>root){5if(root==null)6return;78Queue<BinaryNode<T>>queue=newLinkedList<>();//层序遍历时保存结点的队列9queue.offer(root);//初始化10while(!queue.isEmpty()){11BinaryNode<...

一，一些定义树的深度定义：对于树中的节点n(i)，n(i)的深度定义为，从根到n(i)的唯一路径的长度。树的高度定义：对于树中的节点n(i)，n(i)的高度定义为，从n(i)到树中叶子节点的最长路径的长度。因为树中可能有多个叶子结点，n(i)到每个叶子结点都会有路径，路径最长的即为n(i)的高度。 二，表达式树表达式树的树叶是操作数，非叶结点是操作符。表达式树可用来进行表达式求值。对表达式树中序遍历，就会得到一个符合人类习惯的表达式，这是一个中缀表达式。关于中缀表达式，参考：  对表达式树后序遍历，就得到一个后缀表达式，关于后缀表达式，参考：那，如何构造表达式树呢？即：给定一个后缀表达式，如何将之转换成中缀表达式？---后缀表达式转换成中缀表达式的过程，即为构造表达式树的过程。幸运的是：后缀表达式转换成中缀表达式的过程与后缀表达式求值的过程非常相似。算法如下：输入：后缀表达式输出：(表达式树)中缀表达式扫描后缀表达式，一次读入一个符号①若它是操作数，则建立一个单节点树并将它推入栈中②若它是操作符，则从栈中弹出两颗树T1(先弹出)和T2。该树的树根就是操作符...