前言
算法的核心問題是排序和搜索。這2個領域應用最廣，研究也最透。本文我將講解排序和搜索領域最高效的兩個算法：快速排序算法和二分搜索算法。
教科書和很多實現庫給出的這兩個算法的代碼非常復雜，很難理解，本文中我給出的代碼是最簡單的實現代碼，易于理解，效率也很高。
緣起
剛才有人問我怎樣實現快速排序，我在5分鐘之內寫了一個快速排序的Java代碼出來，不知道他們有沒有理解。
因此，我想到要寫作這篇文章。介紹一下快速排序算法和二分搜索算法的最簡實現。
我的二分搜索算法是在我用Flex開發工作流編輯器時實現的。當時的需求是在2個圖形之間畫出連接線，要求根據鼠標操作來繪制，并且線段的起點和終點都是在圖形的外框上。
上面的描述可能比較抽象，這么說吧，原來我實現的GUI效果是，2個方框，使用鼠標把它們連接起來，我繪制的線是鼠標點下和釋放這2個端點連接起來的線段。但是，這樣的線段比較丑，客戶要求線段的兩頭應該在2個方框的邊框上。
怎么解決這個問題呢？我把線段看做是排序后的點的集合，然后就可以使用二分搜索算法搜索到線段和邊框的交點，然后把它們繪制出來。
當時的二分搜索算法是用ActionScript3寫的，現在我把它改成Java了。
快速排序算法和二分搜索算法
算法主要分為排序算法、搜索算法、圖算法。圖算法我用得不多，沒有發言權，本文就不說了。
排序算法中最快的是快速排序算法，搜索算法中最快的是二分搜索算法。我也最喜歡這2個算法。
因為，它們是使用遞歸實現的，代碼簡潔清晰，效率又非常高。
根據我的理解，算法的本質就是數學。根據輸入和設定的目標，采用有限的步驟實現輸出。通常，使用計算機實現的算法，都會用到循環，這樣才能發揮計算機高速運算的優勢。
循環和遞歸是等效的，這已經被科學家所證明。數學上沒有循環，只有遞歸的概念，因此使用遞歸代替循環表示算法有很多好處：
1， 遞歸的代碼要比循環簡潔很多，也優雅很多。
2， 遞歸的代碼可以用數學方式建模，可以從數學角度驗證其正確性。
很多函數式語言甚至沒有循環的概念和關鍵字，強迫你使用遞歸來實現循環。如，ErLang。
遞歸也有一些缺點，遞歸使用棧來保存函數地址和參數、返回值，而棧是有一定大小的，過多的遞歸調用可能會造成棧溢出。
但是，遞歸算法會容易轉變為循環。我更欣賞遞歸的簡潔，除非真的出現棧溢出的問題，我是不會使用循環的。
二分搜索算法
理論：
二分搜索算法用于針對已排序的集合進行搜索。
它的原理是：
1， 找到排序數組的中間元素，如果它匹配目標值，那么就返回它在數組中的索引。
2， 如果沒有找到，那么判斷中間值比目標值大還是小，
如果中間值比目標值大，那么就對第一個元素到middle-1的元素遞歸這個過程。
如果中間值比目標值小，那么就對middle+1到最后一個元素。
3， 如果結束的索引小于開始的索引，返回-1，表示沒有找到。
4， 如果子集合有2個元素，那么各自比較。因為Java的整數除法會舍棄小數，如果數組只有2個元素，那么middle值一直都是第一個元素。
經過上述的遞歸過程，最終將返回匹配元素的索引，或者是-1，表示找不到。
二分搜索算法之所以速度快，是因為它每次可以把數組切分成兩半，每次遞歸調用都能去除一半數據，而不用匹配每一個數據。
代碼：
下面是代碼，邏輯清楚，代碼簡單。
/**
* by 沈東良/良少 http://blog.csdn.net/shendl/
* @param array
* @param start
* @param end 這是最后一個元素的索引，第一次調用應該是array.length-1
* @param value
* @return
*/
public static int binarySearch(int[] array,int start,int end,int value){
int middle=(start+end)/2;
if(end<start){
return -1;
}
if(end==(start+1)){
if(array[start]==value){
return start;
}else if(array[end]==value){
return end;
}
}else if(array[middle]==value){
return middle;
}else if(value>array[middle]){
return binarySearch(array,middle+1,end,value);
}else if(value<array[middle]){
return binarySearch(array,start,middle-1,value);
}
return -1;
}
上述代碼稍加改變，就可以排序任意類型。如使用泛型，然后加上對Comparable接口的實現，即可。
快速排序算法
二分搜索算法確實非常快，但是它只能用于已排序數組。如果數組未排序呢，該怎么辦呢？簡單，先用快速排序算法進行排序，然后再用二分搜索進行搜索。
先排序再搜索，要比匹配每一個元素快得多。搜索引擎，數據庫索引也都使用了對數據集合的排序技術，這樣搜索數據才會快速。
理論：
最慢，也是最容易想到的排序算法是插入排序算法：
1， 遍歷數組，找出最小的元素，把它放到第一個元素。
2， 循環查找未排序的數組，直到整個數組排序。
這需要2個嵌套的循環，意味著它的效率是O(n^2);
之所以插入排序的效率如此之地，是因為要找出整個數組中最小的數據，需要遍歷整個數組的元素。
而插入排序聰明就聰明在它不查找整個數組最小、次小…的元素，而是每次僅僅把小于某個元素的值移到一邊，通過迭代最終自動實現排序。這就大大節約了排序所需的計算步驟。
快速排序算法的理論：
1， 如果S中的元素個數是0或者1，那么返回。
2， 選取S中的任一元素v，稱為中心點。
3， 將S集合中的元素分為2個部分：L={小于pivot 的元素+ pivot }和R={大于或者等于pivot的元素}。
4， 返回L和R。
我們使用Java使用的是就地排序的方式，因此不需要返回值。
因為Java是一種可以修改變量的語言，用函數式語言的術語來說，就是有“副作用”。我們利用這個副作用直接修改作為參數的Array，不需要返回值。
代碼：
/** by 沈東良/良少 http://blog.csdn.net/shendl/
* 快速排序，有副作用 從小到大
* @param array
* @param start
* @param end這是最后一個元素的索引，第一次調用應該是array.length-1
*/
public static void quickSort(int[] array,int start,int end){
//有可能造成start>end 因為遞歸調用時j+1，可能引起j比end還大1。 另外如果數組是空的，或者輸入錯誤也會出現這種情況
if(end<=start){
return;
}else {
//取中間元素為中心點，然后移到最右邊
int sign=(start+end)/2;
int tmp=array[end];
array[end]=array[sign];
array[sign]=tmp;
int j=start;
for(int i=start;i<=end-1;i++){
//小于的元素和標記互換，等于的不能互換，否則會形成死循環
if(array[i]<array[end]) {
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
j=j+1;
}
}
//把標記元素和第一個>=它的元素位置互換，這樣數組就分成2個部分，一個部分比中心值小，一個部分比中心值大。
tmp=array[j];
array[j]=array[end];
array[end]=tmp;
quickSort(array,start,j);
quickSort(array,j+1,end);
}
}
Java的Arrays類也使用快速排序算法進行排序。但它的代碼寫得像天書一樣。
提高快速排序算法執行效率的主要方法是對中心點進行檢測，希望選中的中心點有更大的概率是整個數組的中值。
我的實現中簡單的選擇數組中間的值作為中心點，一般來說這樣的選擇效率還是不錯的。
注意上面的一項實現技術，我們使用把中心數據元素移到數組最后的方式實現了數組的就地比較。這是比較常用的技術，把數據移到數組的最前面或者最后面，方便比較數據。
另外，我的Java快速排序代碼使用了“副作用”，而在純函數式語言，如Haskell,ErLang中是沒有“副作用”的，也就是說變量不可以重新賦值。此時就需要返回值，每次都創建新的子數組。但函數式語言的數組處理功能很強，也會做很多性能優化，因此函數式語言實現快速排序代碼更加簡單，沒有“副作用”，也更加數學化。
JDK使用二分搜索和快速排序算法實現搜索和排序，足見上述兩個算法的性能優勢。
發表于 @ 2009年04月07日 12:38:00|評論(25 )|舉報|收藏