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

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

排序算法解決的是一類什么具體問(wèn)題呢？

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

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

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

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

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

// 主方法

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]

??? ??? ? // 移動(dòng)眼睛，轉(zhuǎn)換比較的對(duì)象

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

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

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

?

大概的思路已經(jīng)在腦子中形成了，剩下的是簡(jiǎn)單的工作：將思路轉(zhuǎn)化為實(shí)實(shí)在在的代碼。在這里我用 java 編寫了一個(gè)靜態(tài)方法。關(guān)于這個(gè)算法的具體證明過(guò)程詳見《 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的范型以及一個(gè)對(duì)象接口，詳細(xì)情況可以參見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;

}

}

?

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

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

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

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

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

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

?????*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;

????????

??????????? // 新建兩個(gè)輸入堆用于存放待組合牌
????????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;

??????????? // 逐個(gè)比較，一直到一個(gè)堆為空
???????? 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 ++ ;

????????}

????}

?

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

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

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

?

算法初探 之 排序算法