軟考程序員：最快排序和搜索算法最簡代碼實現(xiàn)

　　程序員：最快排序和搜索算法最簡代碼實現(xiàn)

　　算法的核心問題是排序和搜索。這2個領(lǐng)域應(yīng)用最廣，研究也最透。本文我將講解排序和搜索領(lǐng)域最高效的兩個算法：快速排序算法和二分搜索算法。

　　教科書和很多實現(xiàn)庫給出的這兩個算法的代碼非常復(fù)雜，很難理解，本文中給出的代碼是最簡單的實現(xiàn)代碼，易于理解，效率也很高。

　　二分搜索算法是在我用Flex開發(fā)工作流編輯器時實現(xiàn)的。當(dāng)時的需求是在2個圖形之間畫出連接線，要求根據(jù)鼠標(biāo)操作來繪制，并且線段的起點和終點都是在圖形的外框上。

　　上面的描述可能比較抽象，這么說吧，原來我實現(xiàn)的GUI效果是，2個方框，使用鼠標(biāo)把它們連接起來，我繪制的線是鼠標(biāo)點下和釋放這2個端點連接起來的線段。但是，這樣的線段比較丑，客戶要求線段的兩頭應(yīng)該在2個方框的邊框上。

　　怎么解決這個問題呢?我把線段看做是排序后的點的集合，然后就可以使用二分搜索算法搜索到線段和邊框的交點，然后把它們繪制出來。

　　當(dāng)時的二分搜索算法是用ActionScript3寫的，現(xiàn)在我把它改成Java了。

　　快速排序算法和二分搜索算法

　　算法主要分為排序算法、搜索算法、圖算法。圖算法我用得不多，沒有發(fā)言權(quán)，本文就不說了。

　　排序算法中最快的是快速排序算法，搜索算法中最快的是二分搜索算法。我也最喜歡這2個算法。

　　因為，它們是使用遞歸實現(xiàn)的，代碼簡潔清晰，效率又非常高。

　　根據(jù)我的理解，算法的本質(zhì)就是數(shù)學(xué)。根據(jù)輸入和設(shè)定的目標(biāo)，采用有限的步驟實現(xiàn)輸出。通常，使用計算機實現(xiàn)的算法，都會用到循環(huán)，這樣才能發(fā)揮計算機高速運算的優(yōu)勢。

　　循環(huán)和遞歸是等效的，這已經(jīng)被科學(xué)家所證明。數(shù)學(xué)上沒有循環(huán)，只有遞歸的概念，因此使用遞歸代替循環(huán)表示算法有很多好處：

　　1， 遞歸的代碼要比循環(huán)簡潔很多，也優(yōu)雅很多。

　　2， 遞歸的代碼可以用數(shù)學(xué)方式建模，可以從數(shù)學(xué)角度驗證其正確性。

　　很多函數(shù)式語言甚至沒有循環(huán)的概念和關(guān)鍵字，強迫你使用遞歸來實現(xiàn)循環(huán)。如，ErLang。

　　但是，遞歸算法會容易轉(zhuǎn)變?yōu)檠�環(huán)。我更欣賞遞歸的簡潔，除非真的出現(xiàn)棧溢出的問題，我是不會使用循環(huán)的.

　　軟考程序員考試歷年真題匯總(2007年-2010年)

　　2010年下半年軟考成績查詢時間及方式匯總

　　2011年上半年軟考報名時間及方式匯總