数据结构和算法（java）

数据结构：数据结构是指数据在计算机内存空间中或磁盘中的组织形式。

其实java只是摆脱了显式表露的指针，指针依旧以存储地址的形式埋藏在程序的深处。有时设置可以说，在java中所有东西都是指针。这句话虽不是百分之一百的正确，但也差不多。

引用（reference）

java中没有重载操作符。在java中，任何类似的重新定义都是不可能的，而可以使用命名的方法，例如add()或其他名字。

在c和c++中int型的大小可能不同，这取决于它们运行的计算机环境；在java中，一个int型的变量永远是32位

数组：插入算法一步查找n/2步删除需要（假设不允许数据项重复）查找平均n/2个数据项并平均移动剩下的n/2个数据项来填充删除而带来的洞。总共是N步。

有序数组：查找速度比无序的快很多插入由于所有靠后的数据都需要移动以腾空空间，速度较慢

有序数组和无序数组的删除操作都很慢，数据项必须向前移动来填补已删除数据项的洞。

有序数组在查找频繁的情况下十分有用，若插入和删除较为频繁，则无法高效工作。

计算机算法效率：大O表示法

无序数组的插入：常数

T=K在现实情况中，插入所需的实际时间（不管是微秒还是其他单位）与以下因素有关：微处理器，编译程序生成程序代码的效率

线性查找：与N成正比T=K*N/2

二分查找：与log(N)成正比

T=K*log2(N)

大O表示法使用大写字母O,并省去了常数K.可以认为O的含义是"orderof"(大约是)。

O(1)优秀O(logN)良好O(N)还可以O(N2)差

大O表示法的实质并不是对运行时间给出时间值，而是表达了运行时间是如何受数据项个数所影响的。除了实际安装后真正测量一次算法的运行时间之外，这可能是对算法进行比较的最有意义的方法了。

无序数组可以很快进行插入，O(1),但是查找却需要较慢的时间O（N）时间，删除O(N)

有序数组可以很快查找O(logN)时间，但插入花费O(N)，删除O(N)

冒泡排序的算法

O(N2)比较O(N2)交换O（N2）冒泡排序的先排最右边的数据，及最大的下标放最大的数据

选择排序的算法

O(N2)比较O(N2)交换次数O(N)先排序最左边的，及最小的下标放最小的数据

插入排序的算法

O(N2)对于随机的数据来说，需要O(N2)的比较，复制的次数大致等于比较的次数。然而，一次复制与一次交换的事件耗费不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。对于已经有序或基本有序的数据来说，插入排序要好得多。

排序的稳定性

算法对需要排序的数据进行排序，让不需要排序的数据保持原来的顺序。某些算法满足这样的要求，它们就可以称为稳定的算法。（如果具有相同关键字的数据项，经过排序它们的顺序保持不变，这样的排序就是稳定的）

上述算法都是稳定的

栈（Stack）只允许访问一个数据项：即最后插入的数据项。

大部分微处理器运用基于栈的体系结构。当调用一个方法时，把它的返回地址和参数压入栈，当方法结束返回时，那些数据出栈。栈操作就嵌入在微处理器中。

栈的概念和实现它的内部数据结构应该是完全分开的，栈可以用数组来实现，也可以用其他的存储结构，比如链表来实现。

栈通常很小，是临时的数据结构。

栈通常用于解析某种类型的文本串。通常，文本串是用计算机语言写的代码行，而解析他们的程序就是编译器。

栈是一个概念上的辅助工具，栈在抽象概念上更便于使用。栈通过提供限定性的访问方法push()和pop(),使程序易读且不易出错。

用数组实现的栈的入栈和出栈的事件复杂度都为常数O(1).也就是说，栈操作所消耗的时间不依赖与栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。

Queue(队列)

数组可以实现队列，链表也可以用来实现队列

和栈一样，队列中插入数据项和移除数据项的时间复杂度均为O(1)

双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会有双端队列来提供栈和队列的两种功能。但是不太常用

优先级队列是比栈和队列更专用的数据结构。但它在很多情况下都很有用。像普通队列一样，优先级队列有一个队头和一个队尾，并且也是从队头移除数据项。不过在优先级

队列中，数据项按关键字的值有序，这样关键字最小的数据项（或在某些实现中是关键字最大的数据项）总是在队头。

数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。

优先级队列通常使用一种称为堆的数据结构来实现。也可以用简单的数组来实现优先级队列。这种实现方法插入比较慢，但是它比较简单，适用于

数据量比较小并且不是特别注重插入速度的情况。用数组实现的优先级队列的效率：插入需要O(N)的时间，删除需要O(1)的时间

栈、队列和优先级队列是经常用于简化某些程序操作的数据结构。在这些数据结构中，只有一个数据项可以被访问。

链表可能是继数组之后第二种使用最广泛的通用存储结构。链表的机制灵活，用途广泛，它适用于许多通用的数据库。它也可以取代

数组，作为其他存储结构的基础，例如栈、队列。除非需要频繁通过下标随机访问各个数据，否则在很多使用数组的地方都可以用链表来代替。

双端链表：与传统的链表非常相似，但是它有一个新增的特性：即对最后一个链接点的引用，就像对第一个链接点的引用一样。对最后一个链接点的引用允许像在表头一样，在表尾直接插入一个链接点。当然仍可以在普通的单链表的表尾

插入一个链接点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，队列的实现就是这样一个情况。

双端链表类叫做FirstLastList.用双端链表也不能有助于删除最后一个链接点，因为没有一个引用指向倒数第二个链接点。

如果最后一个链接点被删除，倒数第二个链接点的next字段应该变成null值。为了方便的删除最后一个链接点，需要一个双向链表。(当然也可以遍历整个链表找到最后一个链接点，但是那样做效率不是很高)

抽象数据类型（ADT）

它是一种考虑数据结构的方式：着重于它做了什么，而忽略它是怎么做的。

栈和队列都是ADT的例子。可以用数组来实现，也可以用链表来实现栈和队列。栈和队列的"抽象"特性：即如何脱离具体的实现来考虑栈和队列。

双向链表允许向前遍历，也允许向后遍历整个链表。在于每个链接点有两个指向其他链接点的引用，而不是一个。第一个像普通链表一样指向下一个链接点。第二个指向前一个链接点。

递归方法效率：调用一个方法会有一定的额外开销。控制必须从这个调用的位置转移到这个方法的开始处。除此之外，传给这个方法的参数以及这个方法的返回地址都要被压入一个内部的栈里，为的是这个方法可以访问参数值和知道返回到哪里。

人们常常采用递归，是因为它从概念上简化了问题，而不是因为它本质上更有效率。一般情况下，基于循环的方法效率更高。

递归就是程序设计中的数学归纳法。

递归的二分查找和非递归的二分查找有同样的大O效率：O(logN).递归的二分查找更为简洁一些，但是它的速度可能会慢一点。

汉诺塔问题：当手动解决这个难题的时候，有一个经验法则，可以提供帮助。如果试图要移动的子树含有奇数个盘子，开始时直接把最顶端的盘子移动到想要把这颗子树移动到的那个塔座上。如果试图要移动一颗含有偶数个盘子的子树，那么开始时要把最顶端的盘子移动到中介塔座上。

汉诺塔的问题包含三个塔座和任意数量的盘子。

汉诺塔难题可以递归来解决：把除了最低端盘子外的所有盘子形成的子树移动到一个中介塔座上，然后把最低端的盘子移到目标塔座上，最终把那个子树移动到目标塔座上。

对于汉诺塔和归并排序问题，它们的递归的方法包括两次递归调用。

归并排序的算法：缺点：需要在存储器上有另一个大小等于被排序的数据项数目的数组。

归并算法的中心是归并两个已经有序的数组

归并排序的思想是把一个数组分成两半，排序每一半，然后用merge()方法把数组的两半归并成一个有序的数组。

归并排序的效率：运行时间为O(N*logN)

在归并排序中，比较的次数总是比复制的次数略微少一些的。

各种分治算法，比如归并排序的递归函数，能工作的非常好。

一个算法作为一个递归的方法通常从概念上很容易理解，但是，在实际的运用中证明递归算法的效率不太高。在这种

情况下，把递归的算法转换成非递归的算法是非常有用的。这种转换经常会用到栈。

递归和栈之间有一种紧密的联系。事实上，大部分的编译器都是使用栈来实现递归的。

一些有趣的递归应用：

求一个数的乘方，在背包中放入合适的物品，以及登上队选择成员组队的问题。

高级排序

希尔排序：基于插入排序。通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能大跨度的移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去。进行这些排序时数据项之间的间隔

被称为增量，并且习惯上用字母h来表示。

希尔排序比插入排序快很多，它是基于什么原因呢？当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离

很长。这是非常有效率的。当h减小时，每一趟排序需要移动的元素个数增多，但是此时数据项已经接近它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。

希尔排序的效率：有各种各样基于实验的评估，估计它的时间级从O(N^3/2)到O（N^7/6）.

划分：是快速排序的根本机制，但是划分本身也是一个有用的操作。

划分数据就是把数据分成两组，使所有关键字大于特定值的数据项在一组，使所有关键字小于特定值的数据项在另一组。

快速排序时最流行的排序算法，在大多数情况下，快速排序都是最快的，执行时间为O(N*logN)级。（这只是对内部排序或者说随机存储器内的排序而言，对于在磁盘文件中的数据进行的排序，其他的排序算法可能更好）。

快速排序算法本质上通过把一个数组划分为两个子数组，然后递归地调用自身为每一个子数组进行快速排序来实现的。

对快速排序算法来说拥有两个大小相等的子数组是最优的情况。如果快速排序算法必须要对划分的一大一小两个子数组排序，那么将会降低算法的效率，这是因为较大的子数组必须要被划分更多次。

基数排序：把关键字拆分为数字位。并且按数字位的值对数据项进行排序。奇怪的是，实现基数排序不需要比较操作。

基数这个词的意思是一个数字系统的基。10是十进制系统的基数，2是二进制系统的基数。排序包括分别检测关键字的每一个数字，检测从个位（最低有效位）开始。

基数排序的时间复杂度和快速排序相同，只是它需要两倍的存储空间。

树：实现了如下特点：既能像链表那样快速的插入和删除，又能像有序数组那样快速查找。树是范畴更广的图的特例。

根：书顶端的节点称为"根".一棵树只有一个根。如果要把一个节点和边的集合定义为树，那么从根到其他任何一个节点都必须有一条（而且只有一条）路径。

如果树中每个节点最多只能有两个子节点，这样的树就称为"二叉树".它是最简单的，也是最常用的。

二叉搜索树：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字值大于或等于这个父节点。

像其他数据结构一样，有好多方法可以在计算机内存中表示树。最常用的方法是把节点存在无关联的存储器中，而通过每个节点中指向自己子节点的引用来连接。

还可以在内存中用数组表示树，用存储在数组中相对的位置来表示节点在树中的位置。

后继节点：比初始节点大的最小的节点

红黑树的平衡是在插入的过程中取得的。对一个要插入的数据项，插入例程要检查不会破坏树一定的特征。如果破坏了，程序就会纠正，根据需要更改树的结构。

通过维持树的特征，保持了树的平衡。红黑树的优点就是对有序数据的操作不会慢到O(N)的时间复杂度。

红黑树的特征：节点都有颜色、在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则。

红黑规则：

当插入（或者删除）一个新节点时，必须要遵循的一定的规则，它们被称为红黑规则。如果遵循这些规则，树就是平衡的。

1.每一个节点不是红色的就是黑色的。

2.根总是黑色的。

3.如果节点是红色的，则它的子节点必须是黑色的（反之倒不一定必须为真）。

4.从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。

从根到叶节点的路径上的黑色节点的数目称为黑色高度（blackheight）.规则4的另一种陈述方法是所有从根到叶节点路径上的黑色高度必须相同。

修正违规的情况：

1.改变节点的颜色（颜色交换）

2.执行旋转操作（旋转）

在二叉树中加入红黑平衡对平均执行效率只有很小的负面影响，然而却避免了对有序的数据操作的最坏的性能。

B-树保存文件中的记录，快速查找、插入、删除记录。

用B-树作为外部存储的数据结构。B-树所有的节点至少是半满的。虽然B-树中的查找比在顺序有序排列的磁盘文件查找快，不过插入和删除操作才

显示出B-树最大的优越性。

B-树是多叉树，每个节点可以有几十或上百个关键字和子节点。B-树中子节点的个数总是比关键字的个数多1。为了达到最好的性能，B-树通常在一个节点中保存一块的数据。

哈希表基于数组。关键字值的范围通常比数组容量大。关键字值通过哈希函数映射为数组的下标。

哈希表是基于数组的，数组创建后难以扩展。某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期把数据转移到更大的哈希表中，这是个费时的过程。）

而且，也没有一种简便的方法可以以任何一顺序（例如从小到大）遍历表中数据项。如果需要这种能力，就只能选择其他数据结构。

然而，如果不需要有序遍历数据，并且可以提前预测数据量的大小，那么哈希表在速度和易用性方面是无与伦比的。

不论哈希表中有多少数据，插入和删除（有时包括删除）只需要接近常量的时间：即O(1)的时间级。

哈希函数smallNumber=largeNumber%smallRange

它把一个大范围的数字哈希（转化）成一个小范围的数字。这个小的范围对应着数组的下标。使用哈希函数向数组插入数据后，这个数组就称为哈希表。

冲突：把巨大的数字空间压缩成较小的数字空间，必然要付出代价，即不能保证，每个单词都映射到数组的空白单元。

冲突的可能性会导致哈希化方案无法实施，实际上，可以通过另外的方式接近这个问题。因为指定的数组大小两倍于需要存储的数据量。因此，可能一般的单元是空的。当冲突发生时，一个方法是通过系统的方法找

到数组的一个空位，并把这个单词填入，而不再用哈希函数得到的数组下标。这个方法叫做开放地址法。

第二种方法是创建一个存放单词链表的数组，数组内不直接存储单词。这样，当发生冲突时，新的数据项之间接到这个数组下标所指的链表中。这种方法叫做链地址法。

通用的哈希表中，数组的大小应该是素数。当数据项目占哈希表长的一半，或最多到三分之二（60个单元的表容纳40个数据项时），哈希表的性能最好。

因此设计哈希表的关键是确保它的数据项不会超过整个数组容量的一半，最多到三分之二。

开放地址法：通过在哈希表中在寻找一个空位解决冲突问题。

线性探测：原始下标是x探测顺序：x+1,x+2,x+3

二次探测：已填入哈希表的数据项和表长的比率叫做装填因子。loadFactor=nItems/arraySize;

二次探测是防止聚集产生的一种尝试。思想是探测相隔较远的单元，而不是和原始位置相邻的单元。

探测顺序：x+1^2,x+2^2,x+3^2,x+4^2

再哈希法：产生一种依赖关键字的探测序列，而不是每个关键字都一样。不同的关键字几十映射到相同的数字下标，也可以使用不同的探测序列。

方法是把关键字用不同的哈希函数再做一遍哈希化，用这个结果作为步长。对指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用不同的步长。

第二个哈希函数必须具备如下特点：

和第一个哈希函数不同。

不能输出0。

stepSize=constant-(key%constant);

constant是质数，且小于数组容量。

使用开放地址策略时，探测序列通常用再哈希法生成。

哈希表的容量是一个质数：用质数作为数组容量使得任何数想整除它都是不可能的，因此探测序列最终会检查所有单元。

链地址法：

在哈希表中每个单元中设置链表。在链地址法中，装填因子可以达到1以上，且对性能影响不大。因此，链地址法是更健壮的机制，特别是当事先难以确定

哈希表要存储多少数据是更是如此。

用链地址法，表容量是质数的要求不像在二次探测和在哈希法中显得那么重要。但是，但数组容量不是质数时，这种关键字的分布还是能够导致数据的聚集。

桶：类似于链地址法，它在哈希表的每个单元中使用数组，而不是链表。这样的数组有时称为桶。

关于哈希函数的窍门是找到既简单又快的哈希函数，而且要去掉关键字中的无用数据，并尽量使用所有的数据。

如果关键字本身不是随机分布的，不论使用什么哈希化系统，都应该要求数组容量是质数。

哈希表中执行插入和搜索操作可以达到O(1)的时间级。如果没有发生冲突，只需要使用一次哈希函数和数组的引用，就可以插入一个新的数据项或找到一个已存在的数据项。

这是最小的存取时间级。

如果发生冲突，存取时间就依赖后来的探测长度。平均探测长度（以及平均存取时间）取决于装填因子（表中项数和表长的比率）。随着装填因子变大，探测长度也越来越长。

实际情况中，最好的装填因子取决于存储效率和速度之间的平衡。随着装填因子变小，存储效率下降，而速度上升。

链地址法，平均链表的长度等于装填因子。

成功查找，查找时间是1+loadFactor/2;

不成功查找:1+loadFactor

在链地址法中，通常装填因子为1（数据项的个数和数组容量相同）。

开发地址法和链地址法的比较

当两种都可选时，使用链地址法。它需要使用链表类，但回报是增加比预期更多的数据时，不会导致性能的快速下降。