Graph內(nèi)容過于復(fù)雜击敌，而且近期面試不會很容易考到。
Graph系列鏈接：
http://www.reibang.com/p/f968ef8dc0b6
所以先復(fù)習(xí)排序焕妙。
今天上午看了蒋伦，
selection sort
insertion sort
insertion sort without exchanges
shell sort
merge sort
并且寫了代碼。之后會粘貼上焚鹊。意義挺大痕届。
---- Richardo 09/16/2015
下面先講一個我對Java static 的新認(rèn)識。
static 表示是末患，固有的特征研叫。一個類如果有static變量或者方法。表示這個方法或者變量璧针，是這個類的固有特征. 可以直接通過嚷炉， Class.xxx 直接使用。因?yàn)檫@是我的固有特征探橱，即使每個類的對象里面有些細(xì)節(jié)不同申屹，但是這個特征，大家都是相同的隧膏。
就好像兩個親生兄弟哗讥，可能會有許多不同，但是他們的父親一定是相同的胞枕。
A.father B.father
就是這么個意思杆煞。
但是，如果在方法里曲稼，再次申明了這個變量索绪。那么，在這個方法中贫悄，這個static變量不會起作用瑞驱，你申明等于多少，他就會等于多少窄坦。但等到函數(shù)結(jié)束唤反，這個局部變量的效果也就結(jié)束了凳寺。
第二個認(rèn)識。
我知道public static void func() { } 特點(diǎn)就是可以直接調(diào)用彤侍。
那么肠缨，private static void func() {} 意義何在呢？
在公共static方法中使用到的其他任何方法盏阶，任何變量晒奕。都必須是static的。
所以這是private static 意義所在名斟。否則別人用這個公共方法脑慧，卻不能使用里面的私有方法，程序就無法繼續(xù)執(zhí)行砰盐，就會出錯闷袒。
但是，請注意岩梳，我們是需要考慮安全因素的囊骤。static只能保證使用權(quán)，而不能獲得像公共方法一樣的了解權(quán)冀值。也就是說也物，我無法在其他類中，直接使用這個私有方法池摧，而只能通過某個公共方法間接地去使用這個私有方法焦除。因此激况，安全得到了保證作彤。
---- 09/16/2015 12:19
selection sort
就是第一遍從第一個開始遍歷到底，找出最小的乌逐，放在第一個竭讳。
第二遍從第二個開始遍歷到底，找出最小的浙踢，放在第二個绢慢。
如此往復(fù)。
優(yōu)勢： 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
遍歷前兩個，比較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ù)列葫隙，進(jìn)行insertion sort栽烂， 速度很快，運(yùn)行時間線性恋脚。
很重要的優(yōu)勢愕鼓。如果以后別人給你一個大致排好序的數(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
之前的插入排序菇晃，一個很大的問題是，一旦發(fā)現(xiàn)某個值小于他前面的值蚓挤，就要交換一下磺送，需要三次取值操作，大大浪費(fèi)了時間和資源灿意。
于是開發(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的時候，再把它復(fù)原荒辕。
綜上汗销，插入排序在大規(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ìn)版。
插入排序?yàn)槭裁绰舴浚恳驗(yàn)樗脑厥且粋€個移動的茧跋。所以，他的特點(diǎn)是卓囚，到后期瘾杭，越來越快。因?yàn)榍懊嬉呀?jīng)排列的差不多了捍岳。
那么富寿，有辦法睬隶，讓他移動的格子更多些嗎？前期加快移動的幅度页徐，讓他大致成型苏潜，然后，再來一次總的插入排序变勇，因?yàn)橹耙呀?jīng)大致成型了恤左，所以最后一輪插入排序會很快。
這就是 shell sort 的思想搀绣。
于是飞袋，設(shè)置一個 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
放在一塊對比下忆谓，
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í)大家也都熟悉了类咧，就是分治的思想，分成一個個塊蟹腾，然后痕惋，再合體。
從頂上開始分娃殖。
分成兩塊值戳，分別排序。
假設(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)里面做完了从诲。可以自己體會下靡羡，很巧妙盏求。
暫且更新到這里。最近很忙亿眠。剛收到通知碎罚，9.30，面試微軟纳像。很緊張也很興奮荆烈。在浪潮之巔里面的看到的公司，當(dāng)時覺得高不可攀竟趾，現(xiàn)在竟然有機(jī)會去參加他的面試憔购。
雖然希望很渺茫，但我一定會去努力嘗試的２砻薄Ｃ的瘛！
------ 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ī)會犀勒。加油屎飘。
Anyway, Good luck, Richardo!
