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

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

                                                                      ---- Richardo 09/16/2015

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

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

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

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

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ìn)版。
插入排序?yàn)槭裁绰?？因?yàn)樗脑厥且粋€(gè)個(gè)移動(dòng)的。所以，他的特點(diǎn)是，到后期，越來越快。因?yàn)榍懊嬉呀?jīng)排列的差不多了。
那么，有辦法，讓他移動(dòng)的格子更多些嗎？前期加快移動(dòng)的幅度，讓他大致成型，然后，再來一次總的插入排序，因?yàn)橹耙呀?jīng)大致成型了，所以最后一輪插入排序會(huì)很快。
這就是 shell sort 的思想。
于是，設(shè)置一個(gè) k， k = 1, 4, 13, 53....
k = 3 * k + 1 and k < N
然后將數(shù)列分成k塊。塊與塊之間進(jìn)行排序。
比如，
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;
就是插入排序了。
可以看到，
原輸入隊(duì)列是，
9 8 7 6 5 4 3 2 1

現(xiàn)在插入排序的輸入隊(duì)列是，
5 4 3 2 1 8 7 6 9

放在一塊對(duì)比下，
9 8 7 6 5 4 3 2 1
5 4 3 2 1 8 7 6 9
可以看到，小的都往前面移動(dòng)了很多，大的相對(duì)往后移動(dòng)了很多。
于是，插入排序的效率會(huì)很高，效率會(huì)很快。

代碼如下：

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;
        }
    }

下面是，普林斯頓算法書對(duì)shell sort的評(píng)價(jià)，感覺很客觀。
**
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í)大家也都熟悉了，就是分治的思想，分成一個(gè)個(gè)塊，然后，再合體。
從頂上開始分。
分成兩塊，分別排序。
假設(shè)已經(jīng)排好了。
然后新建一個(gè)數(shù)組，將兩個(gè)子數(shù)組按照大小順序合并在這個(gè)總數(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這個(gè)函數(shù)寫的很巧妙，老師寫的。
為什么呢？
以前我處理merge的時(shí)候，也是循環(huán)，但是時(shí)while，然后條件是，
while(i < left.length && j < right.length) {
...
...
}
if (i == left.length)
{....}
else
{....}

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

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

                                                             ------ 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,抓住機(jī)會(huì)。加油。

Anyway, Good luck, Richardo!