Graph內(nèi)容過于復雜，而且近期面試不會很容易考到。
Graph系列鏈接：
http://m.itdecent.cn/p/f968ef8dc0b6
所以先復習排序。
今天上午看了，
selection sort
insertion sort
insertion sort without exchanges
shell sort
merge sort

并且寫了代碼。之后會粘貼上。意義挺大。

                                                                      ---- Richardo 09/16/2015

下面先講一個我對Java static 的新認識。
static 表示是，固有的特征。一個類如果有static變量或者方法。表示這個方法或者變量，是這個類的固有特征. 可以直接通過， Class.xxx 直接使用。因為這是我的固有特征，即使每個類的對象里面有些細節(jié)不同，但是這個特征，大家都是相同的。
就好像兩個親生兄弟，可能會有許多不同，但是他們的父親一定是相同的。
A.father B.father
就是這么個意思。
但是，如果在方法里，再次申明了這個變量。那么，在這個方法中，這個static變量不會起作用，你申明等于多少，他就會等于多少。但等到函數(shù)結(jié)束，這個局部變量的效果也就結(jié)束了。

第二個認識。
我知道public static void func() { } 特點就是可以直接調(diào)用。
那么，private static void func() {} 意義何在呢？
在公共static方法中使用到的其他任何方法，任何變量。都必須是static的。
所以這是private static 意義所在。否則別人用這個公共方法，卻不能使用里面的私有方法，程序就無法繼續(xù)執(zhí)行，就會出錯。
但是，請注意，我們是需要考慮安全因素的。static只能保證使用權(quán)，而不能獲得像公共方法一樣的了解權(quán)。也就是說，我無法在其他類中，直接使用這個私有方法，而只能通過某個公共方法間接地去使用這個私有方法。因此，安全得到了保證。

                                                                  ---- 09/16/2015  12:19

selection sort
就是第一遍從第一個開始遍歷到底，找出最小的，放在第一個。
第二遍從第二個開始遍歷到底，找出最小的，放在第二個。
如此往復。
優(yōu)勢： exchange 次數(shù)很小，只有~N，據(jù)說是最小的。線性。
復雜度， ~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]
類似于冒泡排序。把最小的往前冒泡。
優(yōu)勢：對已經(jīng)排好序的數(shù)列，進行insertion sort， 速度很快，運行時間線性。
很重要的優(yōu)勢。如果以后別人給你一個大致排好序的數(shù)列，就可以考慮用插入排序而不是想都不想直接使用快速排序了。
復雜度 ~ 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
之前的插入排序，一個很大的問題是，一旦發(fā)現(xiàn)某個值小于他前面的值，就要交換一下，需要三次取值操作，大大浪費了時間和資源。
于是開發(fā)出了一種方法只需要一次取值操作。
記錄下，起點a[i]
temp = a[i];
int k = i - 1;
while (k >= 0 && a[k] < temp) {
a[k + 1] = a[k];
k--;
}
然后，當前面的值大于了他，或者到0的時候，再把它復原。
綜上，插入排序在大規(guī)模測試中，速度還是要比選擇排序更快的。
代碼如下：

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
這是一種我之前沒怎么印象，或者說，完全忘記了的算法。
下面講一講他的思路。
他是插入排序的改進版。
插入排序為什么慢？因為他的元素是一個個移動的。所以，他的特點是，到后期，越來越快。因為前面已經(jīng)排列的差不多了。
那么，有辦法，讓他移動的格子更多些嗎？前期加快移動的幅度，讓他大致成型，然后，再來一次總的插入排序，因為之前已經(jīng)大致成型了，所以最后一輪插入排序會很快。
這就是 shell sort 的思想。
于是，設(shè)置一個 k， k = 1, 4, 13, 53....
k = 3 * k + 1 and k < N
然后將數(shù)列分成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

現(xiàn)在插入排序的輸入隊列是，
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
介紹下。
其實大家也都熟悉了，就是分治的思想，分成一個個塊，然后，再合體。
從頂上開始分。
分成兩塊，分別排序。
假設(shè)已經(jīng)排好了。
然后新建一個數(shù)組，將兩個子數(shù)組按照大小順序合并在這個總數(shù)組上，再返回。
這就是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這個函數(shù)寫的很巧妙，老師寫的。
為什么呢？
以前我處理merge的時候，也是循環(huán)，但是時while，然后條件是，
while(i < left.length && j < right.length) {
...
...
}
if (i == left.length)
{....}
else
{....}

很麻煩，然后這代碼，直接把這些事都在一個循環(huán)里面做完了?？梢宰约后w會下，很巧妙。

暫且更新到這里。最近很忙。剛收到通知，9.30，面試微軟。很緊張也很興奮。在浪潮之巔里面的看到的公司，當時覺得高不可攀，現(xiàn)在竟然有機會去參加他的面試。
雖然希望很渺茫，但我一定會去努力嘗試的?。?！

                                                             ------ 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!