<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))。

   /**
     * 二分查找(循环法)
     * @param key
     * @return
     */
    public int binarySearchLoop(int key)
    {
    	System.out.println("begin to binary search key = " + key);
    	
    	int low = 0;
    	int high = arr.length - 1;
    	
    	while(low <= high && low >=0 && high < arr.length)
    	{
    		if (arr[(low + high)/2] == key)
    		{
    			System.out.println("found key and index=" + (low + high)/2);
    			return (low + high)/2;
    		}
    		else
    		{
    	    	if (key < arr[(low + high)/2])
    	    	{
    	    		System.out.println("high = " + (low + high)/2);
    	    		high = (low + high)/2 - 1;
    	    	}
    	    	else
    	    	{
    	    		System.out.println("low = " + (low + high)/2);
    	    		low = (low + high)/2 + 1;
    	    	}
    		}
    	}

    	System.out.println("do not found key");
    	return -1;
}

3. 删除
删除需要先查找，然后删除。具体就是查到要删除的元素，然后把这个元素后面的所有元素向前移位一个，相当于把关键字给删除了。

4. 简单排序
排序是一个应用十分广泛和重要的算法。目前我们开发时使用的jdk提供的集合或map虽然给我们封装好了排序，但jdk的底层实现还是用了这些排序算法，只是对我们透明了而已。比如Arrays.sort（）方法就是使用的快速排序算法。

这里先介绍简单排序：冒泡排序，选择排序和插入排序。这三种排序算法实现步骤都是两个：
先比较，然后交换（或复制其中一个到临时变量里以节省交换时间）。

1） 冒泡排序（数组有N个元素）
冒泡排序（以从小到大排序为例，不特殊说明后面都是这样）：
（1） 从数组第一个元素开始，依次比较相邻的两个元素，保证右边的比左边的大，否则就交换两个元素。直到最后两个元素比较完成，则确定了最后的一个元素肯定是整个数组最大的一个。
（2） 然后再从剩下的N-1个元素中确定最大的一个。依次类推，每次选出最大的元素然后移到后面。就像泡泡一样一步一步的向后确定。每次确定一个元素。

算法比较和交换的次数都很多，时间复杂度O(n^2)。

// 冒泡排序
    public void bubbleSort(int[] dest)
    {
    	print("begin to bubble sort, dest = ", dest);
    	
    	// 外循环下标和内循环下标
    	int index_out = 0;
    	int index_in = 0;
    	
    	for(index_out = dest.length - 1; index_out > 0; index_out--)
    	{
    		for(index_in = 0; index_in < index_out; index_in++)
    		{
    			if(dest[index_in] > dest[index_in + 1])
    			{
    				swap(index_in, index_in + 1);
    			}
    		}
    	}
    	
    	print("the sorted arry is ", dest);
    }

2） 选择排序
选择排序改进了冒泡排序，把交换的次数从O(n^2)减少到了O(n),但比较的次数仍是O(n^2).
(1) 从左向右依次比较相邻两个元素，初始默认最小的数是第一个元素，如果比较第一个比第二个大，则把第二个位置记为最小的数，然后在比较这个较小的和第三个元素，依次类推直到最后。比完之后把最小的元素与第一个元素交换位置。这样一轮比较并交换之后确定了第一个元素是所有里面最小的，而且只交换一次。其余都是简单的赋值。注意每次只是记录最小的元素的索引，并不是记录值，也没有必要。
(2) 再从第二个位置开始比较，把剩下里最小的放到第二个位置。依次类推就完成了排序。跟冒泡不同的是冒泡每次比较能确定最后一个数是最大的，选择排序每次能确定最前面一个是最小的。

// 选择排序
    public void selectSort(int[] dest)
    {
    	print("begin to selectSot,", dest);
    	
    	int min = 0;
    	
    	for(int index_out = 0; index_out < dest.length; index_out++)
    	{
    		min = index_out;
    		
    		for(int index_in = index_out; index_in < dest.length - 1; index_in++)
    		{
    			if (dest[min] > dest[index_in + 1])
    			{
    				min = index_in + 1;
    			}
    		}
    		
    		swap(min, index_out);
    	}
    	
    	print("sorted arr is ", dest);
    }

3） 插入排序
插入排序尤其适合数组基本有序的情况。插入排序认为数组的部分是有序的，只要把无序的找到适当的位置插入有序的部分里就可以了。
（1） 从第一个元素开始认为第一个元素是有序的；第一次循环从第二个元素开始，第二个元素左边是有序的，左边只有一个元素，则比较如果第二个元素比第一个小，则第二个元素插入到第一个元素前面（注意这里是插入，不是交换。意味着是移位操作）；第二次循环从第三个元素开始认为左边两个元素是有序的，则从右往左比较，先跟第二个元素比较，遇到第一个比自己小的元素就把自己插入到这个小的元素后面，其余比自己大的元素就要移位。依次类推，到最后一个元素插入完成排序就完成了。

//插入排序
    public void insertSort(int[] dest)
    {
    	print("begin to insetSort", dest);
    	
    	for (int index_out = 1; index_out < dest.length; index_out++)
    	{
    		int index_in = index_out;
    		int temp = dest[index_out];
    		
    		while(index_in > 0 && dest[index_in - 1] >= temp)
    		{
    			dest[index_in] = dest[index_in -1];
    			index_in--;
    		}
    		
    		dest[index_in] = temp;
    	}
    	
    	print("sorted arr is ", dest);
    }

三种简单排序中插入排序应用最多，同时还是后面会讲到的快速排序中间会使用的排序方法。

三、 栈，队列，优先级队列
栈：可以由数组和链表来实现，数组实现的居多。只允许从一端来操作（压入栈push或弹出栈pop，或单纯的查看peek等）栈的数据，允许访问的一端是栈顶，不允许访问的一端是栈底。通常数组索引0是栈底，大索引是栈顶。遵循后进先出（LIFO）。可以用来解析表达式，辅助实现树的深度优先遍历等。还可以用栈实现单词逆序，链表反转等。
栈的入栈、出栈时间都是O(1).

Jdk中提供了类java.util.Stack<E> extends Vector<E>.几个主要方法push, pop, peek都是synchronized的。

队列：可以由数组和链表来实现，数组实现居多。允许从两端操作（入队或出队）队列的数据，但只允许从固定的一端（队头取出数据，队尾插入数据），先进先出（FIFO）。可以用来辅助实现树的广度优先遍历等。
队列的插入和删除效率也都是O（1）.

Jdk提供了java.util.Queue接口，LinkedList类实现了这个接口，一般可以使用LinkedList来模拟Queue，提供了offer(使用的是list的add方法)，poll(使用的是list的remove方法)，peek方法。


优先级队列：可用堆来实现，永远保证队列的第一个元素是最小的。

Jdk提供了类java.util. PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

四、 链表
链表是继数组之后第二种最通用的数据结构，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。
链表又有单链表，双链表，有迭代器的链表（迭代器是用来随机访问链表元素的方法）等。

和数组一样，在链表上一般执行插入，删除，查找，遍历操作。插入和删除效率比较高，不需要复制移动其他数据，只需要修改相关节点的引用就可以了。
链表的操作比较简单，例子可以参考：
http://wenku.baidu.com/view/06481885ec3a87c24028c443.html

上面介绍完了数组，栈，队列，链表，有篇文章强烈推荐，分别介绍了jdk中这几种数据结构的支持和不同：
http://xu20cn.blog.51cto.com/274020/74075

还有Arrays提供的一些排序算法，关注下hashcode的实现：
http://hi.baidu.com/life_to_you/item/b4b99d23c99297132a0f1c57
http://java.chinaitlab.com/base/808196.html

五、 递归
程序调用自身的编程技巧称为递归（ recursion）。

看个简单的例子，阶乘：n*(n-1)*(n-2)*…*2*1
Int factorial(int n)
{
   If(n==0)
   {
      Return 1;
   }
   Else
   {
     Return n * factorial(n-1);
   }
}
递归的思想就是能把复杂问题逐步转化为简单的同类问题，直到结果很明显。
又比如上面讲过的二分查找：

/**
     * 二分查找(递归法)
     * @param key
     * @return
     */
    public int binarySearchRecursion(int key, int from, int to)
	{
		System.out.println("begin to binary search key = " + key + "from: "
				+ from + "to: " + to);

		if (from > to)
		{
			return -1;
		}
		
		int current = (from + to) / 2;
		
		if (arr[current] == key)
		{
			print("found it,index is ", current);
			return 0;
		} 
		
		if(current == from)
		{
			if(arr[current + 1] == key)
			{
				print("found it,index is ", current + 1);
				return 0;
			}
			System.out.println("can not found it.");
			return -1;
		}
		else if (arr[current] > key)
		{
			return binarySearchRecursion(key, from, current);
		} 
		else
		{
			return binarySearchRecursion(key, current, to);
		}
	}

递归还可以实现归并排序：即把两个有序数组合并成一个有序数组，利用递归可以把任意一个数组分成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()内部就是使用的快速排序。