一，希尔排序算法介绍①希尔排序又称缩小增量排序，它本质上是一个插入排序算法。为什么呢？因为，对于插入排序而言，插入排序是将当前待排序的元素与前面所有的元素比较，而希尔排序是将当前元素与前面增量位置上的元素进行比较，然后，再将该元素插入到合适位置。当一趟希尔排序完成后，处于增量位置上的元素是有序的。②希尔排序算法的效率依赖于增量的选取假设增量序列为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...

一，问题描述在英文单词表中，有一些单词非常相似，它们可以通过只变换一个字符而得到另一个单词。比如：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，生成从1开始的：1，2，3，4，......N一组随机序列，序列中的数不能重复出现。比如：N=5，合法的随机序列为{4,3,1,5,2}、{3,1,4,2,5}……非法的序列有{5,4,1,2,1}来源：《数据结构与算法分析-MAW著 第二章习题2.8》 思路1：对于数据a[N]而言，当随机生成第i个数a[i]时，确保a[i]在a[0]至a[i-1]中没有出现过，就把该数放入a[i]，继续生成下一个数a[i+1]算法复杂度为O(N^2logN)---每生成一个a[i]，需要扫描a[0]...a[i-1]。publicstaticint[]algorithm1(intN){int[]a=newint[N];for(inti=0;i<a.length;++i){while(true){a[i]=randInt(1,N);//生成[1,N]之间的一个随机数　　　　　　　　　　　　intj=0;for(;j<i;++j){if(a[i]==a[j]){break;//如果这个随机数已经在前面出现过了,break,...

1，导论什么是数据结构？Adatastructureisanaggregationofdatacomponentsthattogetherconstituteameaningfulwhole。在计算机领域中，技术千变万化，但是基本的数据结构始终只有那几种。而抽象数据类型（ADT)就是用来描述数据结构具有的功能。比如，二叉树就有前序、中序遍历功能；栈，有先进后出功能。对于某一数据结构，放在不同的层次，它有不同的抽象，比如，对于存入整形数组的栈而言，站在使用Stack的角度，它具有提供先入后出功能；而栈可以用List实现，而List又可以用数组实现，而数组元素又可以是由各个Integer组成，而Integer对于编译器而言，又由bit组成。因此，谈论一种数据结构（类型），需要考虑站在的角度。 2，二叉树的构建算法--以二叉树的结点存储String类型的数据为例讨论通常的想法是，创建一个根结点，再创建一颗左子树和右子树，然后把根结点的左孩子指向左子树，右孩子指向右子树。这种说法并没有考虑，结点如何构造？子树根据什么原则来构造？具体的实现代码怎么写？下面就是记录二叉树创建的具体实现算...

1，对于待存储的海量数据，如何将它们分配到各个机器中去？---数据分片与路由当数据量很大时，通过改善单机硬件资源的纵向扩充方式来存储数据变得越来越不适用，而通过增加机器数目来获得水平横向扩展的方式则越来越流行。因此，就有个问题，如何将这些海量的数据分配到各个机器中？数据分布到各个机器存储之后，又如何进行查找？这里主要记录一致性Hash算法如何将数据分配到各个机器中去。 2，衡量一致性哈希算法好处的四个标准：①平衡性：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。②单调性：单调性是指如果已经有一些数据通过哈希分配到了相应的机器上，又有新的机器加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的机器中去，而不会被映射到旧的机器集合中的其他机器上。这里再解释一下：就是原有的数据要么还是呆在它所在的机器上不动，要么被迁移到新的机器上，而不会迁移到旧的其他机器上。③分散性：④负载：参考这里 3，一致性哈希的原理：由于一般的哈希函数返回一个int（32bit）型的hashCode。因此，可以将该哈希函数能够返回...

1，AVL树又称平衡二叉树，它首先是一颗二叉查找树，但在二叉查找树中，某个结点的左右子树高度之差的绝对值可能会超过1，称之为不平衡。而在平衡二叉树中，任何结点的左右子树高度之差的绝对值会小于等于1。2，为什么需要AVL树呢？在二叉查找树中最坏情况下查找某个元素的时间复杂度为O(n)，而AVL树能保证查找操作的时间复杂度总为O(logn)。   对于一棵BST树而言，不仅有查找操作，也有插入、删除等改变树的形态的操作。随着不断地插入、删除，BST树有可能会退化成链表的形式，使得查找的时间复杂度变成O(N)，这种情形下，BST树的结构非常不平衡了。为了保持树的平衡，需要对树的形态做一些限制，因此，引入了AVL树，以保证树的左右子树高度之差的绝对值小于等于1。3，AVL树的JAVA代码实现： AVLTree 继承BinarySearchTree并改写添加节点的add方法，在add方法中判断插入元素后是否导致树不平衡，当不平衡时需要通过旋转进行调整。何时进行旋转调整是通过左右子树的高度之差进行判断的。这里通过rebalance方法使得某结点保持...