軟考程序員：最快排序和搜索算法最簡代碼實(shí)現(xiàn)
算法的核心問題是排序和搜索。這2個(gè)領(lǐng)域應(yīng)用最廣，研究也最透。本文我將講解排序和搜索領(lǐng)域最高效的兩個(gè)算法：快速排序算法和二分搜索算法。
教科書和很多實(shí)現(xiàn)庫給出的這兩個(gè)算法的代碼非常復(fù)雜，很難理解，本文中給出的代碼是最簡單的實(shí)現(xiàn)代碼，易于理解，效率也很高。
二分搜索算法是在我用Flex開發(fā)工作流編輯器時(shí)實(shí)現(xiàn)的。當(dāng)時(shí)的需求是在2個(gè)圖形之間畫出連接線，要求根據(jù)鼠標(biāo)操作來繪制，并且線段的起點(diǎn)和終點(diǎn)都是在圖形的外框上。
上面的描述可能比較抽象，這么說吧，原來我實(shí)現(xiàn)的GUI效果是，2個(gè)方框，使用鼠標(biāo)把它們連接起來，我繪制的線是鼠標(biāo)點(diǎn)下和釋放這2個(gè)端點(diǎn)連接起來的線段。但是，這樣的線段比較丑，客戶要求線段的兩頭應(yīng)該在2個(gè)方框的邊框上。
怎么解決這個(gè)問題呢?我把線段看做是排序后的點(diǎn)的集合，然后就可以使用二分搜索算法搜索到線段和邊框的交點(diǎn)，然后把它們繪制出來。
當(dāng)時(shí)的二分搜索算法是用ActionScript3寫的，現(xiàn)在我把它改成Java了。
快速排序算法和二分搜索算法
算法主要分為排序算法、搜索算法、圖算法。圖算法我用得不多，沒有發(fā)言權(quán)，本文就不說了。
排序算法中最快的是快速排序算法，搜索算法中最快的是二分搜索算法。我也最喜歡這2個(gè)算法。
因?yàn)椋鼈兪鞘褂眠f歸實(shí)現(xiàn)的，代碼簡潔清晰，效率又非常高。
根據(jù)我的理解，算法的本質(zhì)就是數(shù)學(xué)。根據(jù)輸入和設(shè)定的目標(biāo)，采用有限的步驟實(shí)現(xiàn)輸出。通常，使用計(jì)算機(jī)實(shí)現(xiàn)的算法，都會用到循環(huán)，這樣才能發(fā)揮計(jì)算機(jī)高速運(yùn)算的優(yōu)勢。
循環(huán)和遞歸是等效的，這已經(jīng)被科學(xué)家所證明。數(shù)學(xué)上沒有循環(huán)，只有遞歸的概念，因此使用遞歸代替循環(huán)表示算法有很多好處：
1， 遞歸的代碼要比循環(huán)簡潔很多，也優(yōu)雅很多。
2， 遞歸的代碼可以用數(shù)學(xué)方式建模，可以從數(shù)學(xué)角度驗(yàn)證其正確性。
很多函數(shù)式語言甚至沒有循環(huán)的概念和關(guān)鍵字，強(qiáng)迫你使用遞歸來實(shí)現(xiàn)循環(huán)。如，ErLang。
但是，遞歸算法會容易轉(zhuǎn)變?yōu)檠h(huán)。我更欣賞遞歸的簡潔，除非真的出現(xiàn)棧溢出的問題，我是不會使用循環(huán)的.
二分搜索算法
理論：
二分搜索算法用于針對已排序的集合進(jìn)行搜索。
它的原理是：
1， 找到排序數(shù)組的中間元素，如果它匹配目標(biāo)值，那么就返回它在數(shù)組中的索引。
2， 如果沒有找到，那么判斷中間值比目標(biāo)值大還是小，
如果中間值比目標(biāo)值大，那么就對第一個(gè)元素到middle-1的元素遞歸這個(gè)過程。
如果中間值比目標(biāo)值小，那么就對middle+1到最后一個(gè)元素。
3， 如果結(jié)束的索引小于開始的索引，返回-1，表示沒有找到。
4， 如果子集合有2個(gè)元素，那么各自比較。因?yàn)镴ava的整數(shù)除法會舍棄小數(shù)，如果數(shù)組只有2個(gè)元素，那么middle值一直都是第一個(gè)元素。
經(jīng)過上述的遞歸過程，最終將返回匹配元素的索引，或者是-1，表示找不到。
二分搜索算法之所以速度快，是因?yàn)樗看慰梢园褦?shù)組切分成兩半，每次遞歸調(diào)用都能去除一半數(shù)據(jù)，而不用匹配每一個(gè)數(shù)據(jù)。
代碼：
下面是代碼，邏輯清楚，代碼簡單。
/**
* @param array
* @param start
* @param end 這是最后一個(gè)元素的索引，第一次調(diào)用應(yīng)該是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
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
return binarySearch(array,start,middle-1,value);
}
return -1;
}
上述代碼稍加改變，就可以排序任意類型。如使用泛型，然后加上對Comparable接口的實(shí)現(xiàn)，即可。
快速排序算法
二分搜索算法確實(shí)非常快，但是它只能用于已排序數(shù)組。如果數(shù)組未排序呢，該怎么辦呢?簡單，先用快速排序算法進(jìn)行排序，然后再用二分搜索進(jìn)行搜索。
先排序再搜索，要比匹配每一個(gè)元素快得多。搜索引擎，數(shù)據(jù)庫索引也都使用了對數(shù)據(jù)集合的排序技術(shù)，這樣搜索數(shù)據(jù)才會快速。
理論：
最慢，也是最容易想到的排序算法是插入排序算法：
1， 遍歷數(shù)組，找出最小的元素，把它放到第一個(gè)元素。
2， 循環(huán)查找未排序的數(shù)組，直到整個(gè)數(shù)組排序。
這需要2個(gè)嵌套的循環(huán)，意味著它的效率是O(n^2);
之所以插入排序的效率如此之地，是因?yàn)橐页稣麄€(gè)數(shù)組中最小的數(shù)據(jù)，需要遍歷整個(gè)數(shù)組的元素。
而插入排序聰明就聰明在它不查找整個(gè)數(shù)組最小、次小…的元素，而是每次僅僅把小于某個(gè)元素的值移到一邊，通過迭代最終自動實(shí)現(xiàn)排序。這就大大節(jié)約了排序所需的計(jì)算步驟。
快速排序算法的理論：
1， 如果S中的元素個(gè)數(shù)是0或者1，那么返回。
2， 選取S中的任一元素v，稱為中心點(diǎn)。
3， 將S集合中的元素分為2個(gè)部分：L={小于pivot 的元素+ pivot }和R={大于或者等于pivot的元素}。
4， 返回L和R。
我們使用Java使用的是就地排序的方式，因此不需要返回值。
因?yàn)镴ava是一種可以修改變量的語言，用函數(shù)式語言的術(shù)語來說，就是有“副作用”。我們利用這個(gè)副作用直接修改作為參數(shù)的Array，不需要返回值。
代碼：
* 快速排序，有副作用 從小到大
* @param array
* @param start
* @param end這是最后一個(gè)元素的索引，第一次調(diào)用應(yīng)該是array.length-1
*/
public static void quickSort(int[] array,int start,int end){
//有可能造成start>end 因?yàn)檫f歸調(diào)用時(shí)j+1，可能引起j比end還大1。 另外如果數(shù)組是空的，或者輸入錯(cuò)誤也會出現(xiàn)這種情況
if(end<=start){
return;
}else {
//取中間元素為中心點(diǎn)，然后移到最右邊
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++){
//小于的元素和標(biāo)記互換，等于的不能互換，否則會形成死循環(huán)
if(array[i]
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
j=j+1;
}
}
//把標(biāo)記元素和第一個(gè)>=它的元素位置互換，這樣數(shù)組就分成2個(gè)部分，一個(gè)部分比中心值小，一個(gè)部分比中心值大。 tmp=array[j];
array[j]=array[end];
array[end]=tmp;
quickSort(array,start,j);
quickSort(array,j+1,end);
}
}
Java的Arrays類也使用快速排序算法進(jìn)行排序。但它的代碼寫得像天書一樣。
提高快速排序算法執(zhí)行效率的主要方法是對中心點(diǎn)進(jìn)行檢測，希望選中的中心點(diǎn)有更大的概率是整個(gè)數(shù)組的中值。
我的實(shí)現(xiàn)中簡單的選擇數(shù)組中間的值作為中心點(diǎn)，一般來說這樣的選擇效率還是不錯(cuò)的。
注意上面的一項(xiàng)實(shí)現(xiàn)技術(shù)，我們使用把中心數(shù)據(jù)元素移到數(shù)組最后的方式實(shí)現(xiàn)了數(shù)組的就地比較。這是比較常用的技術(shù)，把數(shù)據(jù)移到數(shù)組的最前面或者最后面，方便比較數(shù)據(jù)。
另外，我的Java快速排序代碼使用了“副作用”，而在純函數(shù)式語言，如Haskell,ErLang中是沒有“副作用”的，也就是說變量不可以重新賦值。此時(shí)就需要返回值，每次都創(chuàng)建新的子數(shù)組。但函數(shù)式語言的數(shù)組處理功能很強(qiáng)，也會做很多性能優(yōu)化，因此函數(shù)式語言實(shí)現(xiàn)快速排序代碼更加簡單，沒有“副作用”，也更加數(shù)學(xué)化。
【編輯推薦】
