java数据结构和算法_数据结构和算法（JAVA）.pdf 数据结构：数据结构是指数据在计算机内存空间中或磁盘中的组织形式。
其实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 的含义是"order of"(⼤约是)。
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)
java类的概念双端队列与栈或队列相⽐，是⼀种多⽤途的数据结构，在容器类库中有时会有双端队列来提供栈和队列的两种功能。但是不太常⽤
优先级队列是⽐栈和队列更专⽤的数据结构。但它在很多情况下都很有⽤。像普通队列⼀样，优先级队列有⼀个队头和⼀个队尾，并且也是从队头移除数据项。不过在优先级
队列中，数据项按关键字的值有序，这样关键字最⼩的数据项 (或在某些实现中是关键字最
⼤的数据项)总是在队头。
数据项插⼊的时候会按照顺序插⼊到合适的位置以确保队列的顺序。
优先级队列通常使⽤⼀种称为堆的数据结构来实现。 也可以⽤简单的数