Graph内容过于复杂，而且近期面试不会很容易考到。
Graph系列链接：
http://www.jianshu.com/p/f968ef8dc0b6
所以先复习排序。
今天上午看了，
selection sort
insertion sort
insertion sort without exchanges
shell sort
merge sort
并且写了代码。之后会粘贴上。意义挺大。
---- Richardo 09/16/2015
下面先讲一个我对Java static 的新认识。
static 表示是，固有的特征。一个类如果有static变量或者方法。表示这个方法或者变量，是这个类的固有特征. 可以直接通过， Class.xxx 直接使用。因为这是我的固有特征，即使每个类的对象里面有些细节不同，但是这个特征，大家都是相同的。
就好像两个亲生兄弟，可能会有许多不同，但是他们的父亲一定是相同的。
A.father B.father
就是这么个意思。
但是，如果在方法里，再次申明了这个变量。那么，在这个方法中，这个static变量不会起作用，你申明等于多少，他就会等于多少。但等到函数结束，这个局部变量的效果也就结束了。
第二个认识。
我知道public static void func() { } 特点就是可以直接调用。
那么，private static void func() {} 意义何在呢？
在公共static方法中使用到的其他任何方法，任何变量。都必须是static的。
所以这是private static 意义所在。否则别人用这个公共方法，却不能使用里面的私有方法，程序就无法继续执行，就会出错。
但是，请注意，我们是需要考虑安全因素的。static只能保证使用权，而不能获得像公共方法一样的了解权。也就是说，我无法在其他类中，直接使用这个私有方法，而只能通过某个公共方法间接地去使用这个私有方法。因此，安全得到了保证。
---- 09/16/2015 12:19
selection sort
就是第一遍从第一个开始遍历到底，找出最小的，放在第一个。
第二遍从第二个开始遍历到底，找出最小的，放在第二个。
如此往复。
优势： exchange 次数很小，只有~N，据说是最小的。线性。
复杂度， ~O(N2 / 2)
但是感觉没什么用。。不具体讲了，代码如下。
public static void sort(Comparable[] a) {
if (a == null || a.length == 0)
return;
for (int i = 0; i < a.length; i++) {
int minIndex = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j].compareTo(a[minIndex]) < 0)
minIndex = j;
}
Comparable temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
insertion sort
遍历前两个，比较i 与 i - 1,如果a[i] < a[i -1]，则 swap(a[i], a[i - 1]);
and then compare a[i - 2] and a[i - 1]
类似于冒泡排序。把最小的往前冒泡。
优势：对已经排好序的数列，进行insertion sort， 速度很快，运行时间线性。
很重要的优势。如果以后别人给你一个大致排好序的数列，就可以考虑用插入排序而不是想都不想直接使用快速排序了。
复杂度 ~ O(N2 / 4)
代码如下：
public static void sort(Comparable[] a) {
if (a == null || a.length == 0)
return;
for (int i = 1; i < a.length; i++) {
for (int j = i; j >= 1; j--) {
if (a[j - 1].compareTo(a[j]) > 0) {
Comparable temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp; }
}
}
}
Insertion sort without exchanges
之前的插入排序，一个很大的问题是，一旦发现某个值小于他前面的值，就要交换一下，需要三次取值操作，大大浪费了时间和资源。
于是开发出了一种方法只需要一次取值操作。
记录下，起点a[i]
temp = a[i];
int k = i - 1;
while (k >= 0 && a[k] < temp) {
a[k + 1] = a[k];
k--;
}
然后，当前面的值大于了他，或者到0的时候，再把它复原。
综上，插入排序在大规模测试中，速度还是要比选择排序更快的。
代码如下：
public static void sort(Comparable[] a) {
if (a == null || a.length == 0)
return;
for (int i = 1; i < a.length; i++) {
Comparable temp = a[i];
int k = i - 1;
while (k >= 0 && a[k].compareTo(temp) > 0) {
a[k + 1] = a[k];
k--;
}
a[k + 1] = temp;
}
}
shell sort
这是一种我之前没怎么印象，或者说，完全忘记了的算法。
下面讲一讲他的思路。
他是插入排序的改进版。
插入排序为什么慢？因为他的元素是一个个移动的。所以，他的特点是，到后期，越来越快。因为前面已经排列的差不多了。
那么，有办法，让他移动的格子更多些吗？前期加快移动的幅度，让他大致成型，然后，再来一次总的插入排序，因为之前已经大致成型了，所以最后一轮插入排序会很快。
这就是 shell sort 的思想。
于是，设置一个 k， k = 1, 4, 13, 53....
k = 3 * k + 1 and k < N
然后将数列分成k块。块与块之间进行排序。
比如，
k = 4
i = k;
9 8 7 6 5 4 3 2 1
a[0] compare with a[4], swap or not
5 8 7 6 9 4 3 2 1
a[4] compare with a[8], swap or not
5 8 7 6 1 4 3 2 9
i = k + 1 = 5;
a[1] compare with a[5], swap or not
5 4 7 6 1 8 3 2 9
a[5] compare with a[9], a[9] does not exist
quit
i = k + 2 = 6
a[2] compare with a[6], swap or not
5 4 3 6 1 8 7 2 9
a[6] compare with a[10], a[10] does not exist
quit
i = k + 3 = 7
a[3] compare with a[7], swap or not
5 4 3 2 1 8 7 6 9
...
quit
i = k + 4 = 8
a[4] compare with a[8], swap or not
not swap
5 4 3 2 1 8 7 6 9
k = 1;
i = k;
=> k = 1; i = 1;
就是插入排序了。
可以看到，
原输入队列是，
9 8 7 6 5 4 3 2 1
现在插入排序的输入队列是，
5 4 3 2 1 8 7 6 9
放在一块对比下，
9 8 7 6 5 4 3 2 1
5 4 3 2 1 8 7 6 9
可以看到，小的都往前面移动了很多，大的相对往后移动了很多。
于是，插入排序的效率会很高，效率会很快。
代码如下：
public static void sort(Comparable[] a) {
if (a == null || a.length == 0)
return;
for (int i = 1; i < a.length; i++) {
Comparable temp = a[i];
int k = i - 1;
while (k >= 0 && a[k].compareTo(temp) > 0) {
a[k + 1] = a[k];
k--;
}
a[k + 1] = temp;
}
}
下面是，普林斯顿算法书对shell sort的评价，感觉很客观。
**
We shall see methods that are more efficient, but they are perhaps only twice as fast (if that much) except for very large N, and they are more complicated. If you need a solution to a sorting problem, and are working in a situation where a system sort may not be available (for example, code destined for hardware or an embedded system), you can safely use shell sort, then determine sometime later whether it will be worthwhile to replace it with a more sophisticated method.
**
merge sort
merge sort 分为两种， top-down and bottom-up
我刚看到 top-down
介绍下。
其实大家也都熟悉了，就是分治的思想，分成一个个块，然后，再合体。
从顶上开始分。
分成两块，分别排序。
假设已经排好了。
然后新建一个数组，将两个子数组按照大小顺序合并在这个总数组上，再返回。
这就是top - down 的思想。
代码如下：
public class MergeSort {
private static Comparable[] aux;
public static void sort(Comparable[] a) {
if (a == null || a.length == 0)
return;
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
int g = 15;
}
private static void sort(Comparable[] a, int lo, int hi) {
if (lo >= hi)
return;
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
private static void merge(Comparable[] a, int lo, int mid, int hi) {
for (int i = lo; i <= hi; i++)
aux[i] = a[i];
int i = lo;
int j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (j > hi)
a[k] = aux[i++];
else if (i > mid)
a[k] = aux[j++];
else if (aux[i].compareTo(a[j]) < 0)
a[k] = aux[i++];
else
a[k] = aux[j++];
}
}
}
感觉merge这个函数写的很巧妙，老师写的。
为什么呢？
以前我处理merge的时候，也是循环，但是时while，然后条件是，
while(i < left.length && j < right.length) {
...
...
}
if (i == left.length)
{....}
else
{....}
很麻烦，然后这代码，直接把这些事都在一个循环里面做完了。可以自己体会下，很巧妙。
暂且更新到这里。最近很忙。刚收到通知，9.30，面试微软。很紧张也很兴奋。在浪潮之巅里面的看到的公司，当时觉得高不可攀，现在竟然有机会去参加他的面试。
虽然希望很渺茫，但我一定会去努力尝试的！！！
------ Richardo 09/17/2015 21:19
quick sort 更新
My code:
import java.io.*;
import java.util.*;
public class Solution {
public static void sort(int[] nums) {
if (nums == null || nums.length == 0)
return;
quicksort(0, nums.length - 1, nums);
}
private static void quicksort(int lo, int hi, int[] nums) {
if (lo >= hi)
return;
int middle = lo + (hi - lo) / 2;
int pivot = nums[middle];
int i = lo;
int j = hi;
while (i <= j) {
while (nums[i] < pivot)
i++;
while (nums[j] > pivot)
j--;
if (i <= j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
if (lo < j)
quicksort(lo, j, nums);
if (i < hi)
quicksort(i, hi, nums);
}
public static void main(String[] args) {
int[] nums = {5, 3, 4, 2, 6, 1};
Solution.sort(nums);
for (int i = 0; i < nums.length; i++)
System.out.println(nums[i]);
}
}
明天是春季career fair,抓住机会。加油。
Anyway, Good luck, Richardo!
