摘《李開復(fù)：算法的力量》 : 算法是計算機科學(xué)領(lǐng)域最重要的基石之一，但卻受到了國內(nèi)一些程序員的冷落。許多學(xué)生看到一些公司在招聘時要求的編程語言五花八門就產(chǎn)生了一種誤解，認為學(xué)計算機就是學(xué)各種編程語言，或者認為，學(xué)習(xí)最新的語言、技術(shù)、標準就是最好的鋪路方法。其實大家都被這些公司誤導(dǎo)了。編程語言雖然該學(xué)，但是學(xué)習(xí)計算機算 法和理論更重要，因為計算機算法和理論更重要，因為計算機語言和開發(fā)平臺日新月異，但萬變不離其宗的是那些算法和理論，例如數(shù)據(jù)結(jié)構(gòu)、算法、編譯原理、計算機體系結(jié)構(gòu)、關(guān)系型數(shù)據(jù)庫原理等等 。

許多計算機科學(xué)家認為，排序算法是算法學(xué)習(xí)中最基本的問題。那么我們就從排序這類算法開始，去看看算法究竟是什么。

排序算法解決的是一類什么具體問題呢？

輸入 :n 個數(shù)的序列 <a1,a2,a3,...,an>

輸出 : 輸入序列的一個重排 <a'1,a'2,a'3,...,a'n>, 使得 a'1<=a'2<=a'3<=...<=a'n

輸入序列通常是一個 n 元數(shù)組，但也可能由其他形式來表示，如鏈表。

對于這個問題，我們可以很容易聯(lián)想到日常生活中的許多例子。那么我們解決這個問題的第一個思路便可以從日常生活中獲得。

插入排序，這是一個對少量元素進行排序的有效算法。其工作機理和很多人打牌時，整理手中牌時的做法差不多。在開始摸牌時，我們的左手是空的，牌面朝下的放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌合適的位置，要將它與手中已有的每一張牌從右向左地進行比較。無論在什么時候，左手中的牌都是排好序的，而這些牌原先都是桌上那副牌里最頂上的一些牌。

// 主方法

INSERTION-SORT(A)

??? // 從桌面上一次次取牌

???? for j ← 2 to length[A]

??? do

??? ??? ??? ??? ??? // 取一張牌到右手 key

??? ??? ??? ??? ??? ?? key ← A[j]

??? ??? ??? ??? ??? ??? ??? ??? // 眼睛注意的位置（將要比較的位置）

??? ??? ??? ??? ??? ??? ??? ??? i ← j – 1

??? ??? ??? ??? ??? ??? ??? ??? // 開始尋找合適的位置

??? ??? ??? ??? ??? ??? ??? ??? while i > 0 and A[i] > key

??? ??? ??? ??? ??? ??? ??? ??? do

??? ??? ??? ??? ??? ??? ??? ??? ??? ??? // 微調(diào)左手中的已經(jīng)排好順序的牌

??? ??? ? A[i + 1] ← A[i]

??? ??? ? // 移動眼睛，轉(zhuǎn)換比較的對象

??? ??? ??? ??? ??? ??? ??? ??? ??? ??? i ← i – 1

??? ??? ??? ??? ??? ??? ??? ??? ??? ??? // 將右手中的牌放在左手牌中合適的位置上

???? ??? ??? ??? ??? ??? ??? ??? A[i + 1] ← key

?

大概的思路已經(jīng)在腦子中形成了，剩下的是簡單的工作：將思路轉(zhuǎn)化為實實在在的代碼。在這里我用 java 編寫了一個靜態(tài)方法。關(guān)于這個算法的具體證明過程詳見《 Introduction to Algorithms 》 .

? /**?*/ /**

*InsertionSort

*The?time?limit?of?this?sort?is?O(n^2)

*<strong>O(n^2)</strong>

* @param ?element?will?be?sorted

*在這段代碼中使用了java的范型以及一個對象接口，詳細情況可以參見java相關(guān)教材

*/

public ? static ? < Type? extends ?Comparable > ? void ?insertionSort(Type?element[]) ... {

for ( int ?j = 1 ;j < element.length;j ++ ) ... {

Type?key? = ?element[j];

int ?i? = ?j - 1 ;

while (?(i >= 0 ) && (element[i].compareTo(key) > 0 )) ... {

element[i + 1 ]? = ?element[i];

i -- ;

}

element[i + 1 ]? = ?key;

}

}

?

如同大家打牌一樣，很多人熟能生巧整理手中的牌時又準又快，而有些人卻費時費力。那么一個算法也是友好有壞，在這里我只給出相關(guān)的評價指數(shù)，至于具體規(guī)定可參見相關(guān)書籍。

這個算法的時間復(fù)雜度為 O(n^2) ，空間復(fù)雜度為 O(n). 關(guān)于“ O” 符號可以在微積分類書籍上找到更為詳盡的解釋。

科學(xué)技術(shù)不斷進步，很多新的算法應(yīng)運而生。在這里再介紹一種排序算法。它在時間復(fù)雜度上有了具大提高，空間上卻付出了兩倍的代價。

合并排序，一種利用了“分治策略”的排序方法。分治策略：將原問題劃分成 n 個規(guī)模較小而結(jié)構(gòu)簡單與原問題相似的子問題；遞歸地解決這些子問題，然后再合并其結(jié)果，就得到原問題的解。排序算法就是借助了這種思想，本質(zhì)是：從中間把數(shù)組分成元素個數(shù)盡量相等的兩半，分別對他們進行排序，然后再合并兩個有序表。整個問題最困難的地方便是合并兩個有序表，在這里我們著重看看這個過程。

再舉打牌這個例子 , 假設(shè)有兩堆牌正 面朝上地放在桌上，每一堆都是已經(jīng)排好順序的，最小的牌在最上面。我們希望把這兩堆牌合并成一個排好序的輸出堆，面朝下地放在桌上。基本步驟包括在面朝上的兩堆牌中，選取頂上兩張牌中較小的一張，將其取出后面朝下地放入輸出堆中。重復(fù)這個步驟，直到某一堆為空為止。

???? /**?*/ /**

?????*Merge?used?in?the?mergeSort

?????*<strong>O(n)</strong>

?????* @param ?element?Type[]?the?elements?to?be?merged

?????* @param ?p?int?the?begin?of?the??first?elements

?????* @param ?q?int?the?end?of?the?first?elements

?????* @param ?r?int?the?end?of?the?second?elements

????? */

???? private ? static ? < Type? extends ?Comparable > ? void ?merge(Type?element[], int ?p, int ?q, int ?r) ... {

??????????? // 確定兩堆牌的起始位置
???????? int ?nl???? = ????q - p + 1 ;

???????? int ?nr???? = ????r - q;

????????

??????????? // 新建兩個輸入堆用于存放待組合牌
????????Type[]?lElement,rElement;

????????lElement???? = ????(Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nl);

????????rElement???? = ????(Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nr);

????????????????

??????????? // 做記錄處理
???????? for ( int ?i = 0 ;i < nl;i ++ ) ... {

????????????lElement[i]???? = ????element[p + i];

????????}

???????? for ( int ?i = 0 ;i < nr;i ++ ) ... {

????????????rElement[i]???? = ????element[q + i + 1 ];

????????}

????????

??????????? // 開始取牌
???????? int ?i = 0 ,j = 0 ;

???????? int ?k???? = ????p;

??????????? // 逐個比較，一直到一個堆為空
???????? while ((i < nl) && (j < nr)) ... {

???????????? if (lElement[i].compareTo(rElement[j]) <= 0 ) ... {

????????????????element[k]???? = ????lElement[i];

????????????????i ++ ;

????????????} else ... {

????????????????element[k]???? = ????rElement[j];

????????????????j ++ ;

????????????}

????????????k ++ ;

????????}

????????

??????????? // 處理某一堆中?剩下的牌
???????? while (i < nl) ... {

????????????element[k]???? = ????lElement[i];

????????????i ++ ;

????????????k ++ ;

????????}

???????? while (j < nr) ... {

????????????element[k]???? = ????rElement[j];

????????????j ++ ;

????????????k ++ ;

????????}

????}

?

這個算法的時間復(fù)雜度為 O(n log2 n), 空間復(fù)雜度為 O(2n) ＝ O(n).

至此兩個算法的介紹結(jié)束，我們將這類算法擴大化，從中取出根本的東西。

數(shù)據(jù)信息中的逆序?qū)?

?

算法初探 之 排序算法