<1> 数据结构回顾(数组，链表，栈，队列，递归，排序算法)
理论+实践永远是学习的最佳途径。写程序越到后面越觉得数据结构的重要，内功外功相得益彰吧，当然内功还包括算法，编译原理，操作系统原理等等。现在的认识跟上学时的认识已经完全不一样了，仅仅是认识，掌握还需修行，这种转变靠别人的教说是做不到的。
回顾下数据结构的内容，参考书籍《java数据结构和算法（第二版）》[Robert Lafore著]。
一、数据结构和算法的基本概念
数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。又说，是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：
Data-Structure=(D,R)
其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合
数据(Data):是对信息的一种符号表示。
在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。
数据结构主要指逻辑结构和物理结构。
数据之间的相互关系称为逻辑结构。通常分为四类基本结构：
集合：结构中的数据元素除了同属于一种类型外，别无其它关系。
线性结构：结构中的数据元素之间存在一对一的关系。
树型结构：结构中的数据元素之间存在一对多的关系。
图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
数据结构的物理结构就是指数据结构在计算机中的存储，通常有两种不同的表示方法：
顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。
数据结构的三方面
算法：模型分析的一组可行的、确定的和有穷的规则。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。
程序：是计算机能理解和执行的指令序列。一个程序实现一个算法。算法和程序的区别是算法的执行是有穷的，而程序的执行可以是无限的（搞个死循环嘛）。
一个算法有以下5个特征：
有穷性，明确性，输入项，输出项，可行性。
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
1.时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。
T(n)=Ο(f(n))
因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。
2.空间复杂度
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
3.正确性
算法的正确性是评价一个算法优劣的最重要的标准。
4.可读性
算法的可读性是指一个算法可供人们阅读的容易程度。
5.健壮性
健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。
程序 = 数据结构 + 算法
二、数组
数组是使用最广泛的数据结构，就是相同数据类型（可以是基本类型也可以是自定义对象）的元素按一定顺序排列的集合，它们在内存中按照这个先后顺序连续存放在一起。有一维数组，二维数组，多维数组。涉及最多的操作就是增删改查，排序等。
这种最简单的数据结构有时候可以用来解决比较复杂的现实问题，比如程序中很多的if或case语句时可以用表驱动法来消除if或case，这个表驱动的表就是数组。
Jdk提供了ArrayList，Vector实现动态数组（前者不是同步的，多线程中要自己保证正确，后者是同步的，所以效率会差点）。当然在简单的情况下还是使用自定义简单数组如Object[]的方式最快。
1.插入数据
数组插入数据很简单，就是取索引然后赋值，时间复杂度永远是O(1)。对于基本类型赋值就是把数值放入到数组元素分配的内存中，对于对象，赋值就是把对象在堆内存中的地址（这个是不是实际的存放地址取决于jvm实现，是采用的直接地址还是句柄）赋给数组元素。
2.查找
1）线性查找
线性查找就是按照数组索引顺序依次比较关键字进行查找，所以时间复杂度是O(N)。
2）二分查找
二分查找就是截中分段查找，比如查找1-10中的数，就先看是否在1-5之间，不在就再查找6-10之间，依次类推，使用的限制条件是数组必须有序。由此可见这种查找需要数组是有序数组，否则无效。这样最多需要查找log(n) (默认以2为底)次，查找效率比线性查找高，但时间复杂度表示依然是O(log(n))。
3.删除
删除需要先查找，然后删除。具体就是查到要删除的元素，然后把这个元素后面的所有元素向前移位一个，相当于把关键字给删除了。
4.简单排序
排序是一个应用十分广泛和重要的算法。目前我们开发时使用的jdk提供的集合或map虽然给我们封装好了排序，但jdk的底层实现还是用了这些排序算法，只是对我们透明了而已。比如Arrays.sort（）方法就是使用的快速排序算法。
这里先介绍简单排序：冒泡排序，选择排序和插入排序。这三种排序算法实现步骤都是两个：
先比较，然后交换（或复制其中一个到临时变量里以节省交换时间）。
1）冒泡排序（数组有N个元素）
冒泡排序（以从小到大排序为例，不特殊说明后面都是这样）：
（1）从数组第一个元素开始，依次比较相邻的两个元素，保证右边的比左边的大，否则就交换两个元素。直到最后两个元素比较完成，则确定了最后的一个元素肯定是整个数组最大的一个。
（2）然后再从剩下的N-1个元素中确定最大的一个。依次类推，每次选出最大的元素然后移到后面。就像泡泡一样一步一步的向后确定。每次确定一个元素。
算法比较和交换的次数都很多，时间复杂度O(n^2)。
递归还可以实现归并排序：即把两个有序数组合并成一个有序数组，利用递归可以把任意一个数组分成2份，然后分成4份，直到分成只有一个元素的数组，然后开始合并。时间复杂度是O(N*logN)，但一个大缺点是归并排序需要原始数组两倍的存储空间。
消除递归
有些情况需要消除递归，因为递归的效率并不好，优点是写法简单，容易理解。效率不高的原因是函数调用时要把调用方的信息压入内存栈，递归入栈出栈的操作太多。所有的递归都可以转成循环实现，特别是尾递归（即函数的最后一句是调用自身）。比如上面二分查找的两个例子。
六、高级排序（希尔排序， 快速排序）
相比前面的冒泡，选择，插入排序，还有更快的排序希尔排序和快速排序。
希尔排序：因为是计算机科学家Donald L. Shell发现的，所以叫shell排序。希尔排序是基于插入排序的，但是增加了一个新的特性，大大提高了插入排序的执行效率，实际上是一种分组插入排序，加大了插入排序中元素之间的间隔，在这些有间隔的元素中进行插入排序。
时间复杂度是O(n * (logn)^2)
用简单例子说明，如下几个数字需要排序，先排间隔为4（后面会说这个间隔怎么确定）的数字，然后缩小间隔，直到间隔为1.
间隔h的确定，假定需要排序的数字有n个，则最初的间隔用下面的循环确定：
While(h < n/3)
{
h = 3 * h +1;
}
每排完一个间隔就缩小间隔：h = (h - 1)/3.
注：这个间隔的确定是经过很长时间的演进的，一个原则是每次算出来的序列最好是互质的。最初采用的是n/2的间隔，但效果不是很好。
快速排序：是所有排序中速度最快的算法，时间复杂度O(n * logn). 但如果数组本身是有序的，则有可能会退化为O(n^2)，就是如果每次选取的划分两组的关键字只能把其中一个数字分为一组，其余所有的作为第二组，这样要分N次组.
快速排序先是把数组分成两组，一组是比“某个关键字”小的，一组是比“某个关键字”大的。然后递归调用自己，最后把所有的都排序出来。这里有两个关键，一个是怎么分出两组，一个是如何选取“某个关键字”。
关键字：一种方法是直接选取数组的最右边数作为关键字，另外还有取最左边，最右边和中间一个数中的中值作为关键字。这个关键字的选取很重要，关系到快速排序的效率，选取方法也是经过很长时间演进的。
分组：选取出关键字后的算法（1）设置一个指针指向数组最左边一个数，一个指针指向数组最右边一个数，然后左边的指针往右，右边的指针往左，当左边的指针遇到比关键字小的时候继续往右，否则停下；右边的指针遇到比关键字大的继续往左，否则停下。（2）两个指针都停下时交换两个数值，然后继续。（3）直到两个指针相遇结束。
Arrays.sort()内部就是使用的快速排序。