『壹』 演算法怎麼就這么難
廣大碼農同學們大多都有個共識，認為演算法是個硬骨頭，很難啃，悲劇的是啃完了還未必有用——除了面試的時候。實際工程中一般都是用現成的模塊，一般只需了解演算法的目的和時空復雜度即可。
不過話說回來，面試的時候面演算法，包括面項目中幾乎不大可能用到的演算法，其實並不能說是毫無道理的。演算法往往是對學習和理解能力的一塊試金石，難的都能掌握，往往容易的事情不在話下。志於高者得於中。反之則不成立。另一方面，雖說教科書演算法大多數都是那些即便用到也是直接拿模塊用的，但不幸的是，我們這群搬磚頭的有時候還非得做些發明家的事情：要麼是得把演算法當白盒加以改進以滿足手頭的特定需求；要麼乾脆就是要發明輪子。所以，雖說面試的演算法本身未必用得到，但熟悉各種演算法的人通常更可能熟悉演算法的思想，從而更可能具備這里說的兩種能力。
那麼，為什麼說演算法很難呢？這個問題只有兩種可能的原因：
演算法本身就很難。也就是說，演算法這個東西對於人類的大腦來說本身就是個困難的事兒。
講得太爛。
下面會說明，演算法之所以被絕大多數人認為很難，以上兩個原因兼具。
我們說演算法難的時候，有兩種情況：一種是學演算法難。第二種是設計演算法難。對於前者，大多數人（至少我當年如此）學習演算法幾乎是在背演算法，就跟背菜譜似的（「Cookbook」是深受廣大碼農喜愛的一類書），然而演算法和菜譜的區別在於，演算法包含的細節復雜度是菜譜的無數倍，演算法的問題描述千變萬化，邏輯過程百轉千回，往往看得人愁腸百結，而相較之下任何菜譜涉及到的基本元素也就那麼些（所以程序員肯定都具有成為好廚師的潛力:D）注意，即便你看了演算法的證明，某種程度上還是「背」（為什麼這么說，後面會詳述）。我自己遇到新演算法基本是會看證明的，但是發現沒多久還是會忘掉，這是死記硬背的標准症狀。如果你也啃過演算法書，我相信很大可能性你會有同感：為什麼當時明明懂了，但沒多久就忘掉了呢？為什麼當時明明非常理解其證明，但沒過多久想要自己去證明時卻發現怎麼都沒法補上證明中缺失的一環呢？
初中學習幾何證明的時候，你會不會傻到去背一個定理的證明？不會。你只會背結論。為什麼？一方面，因為證明過程包含大量的細節。另一方面，證明的過程環環相扣，往往只需要注意其中關鍵的一兩步，便能夠自行推導出來。演算法邏輯描述就好比定理，演算法的證明的過程就好比定理的證明過程。但不幸的是，與數學裡面大量簡潔的基本結論不同，演算法這個「結論」可不是那麼好背的，許多時候，演算法本身的邏輯就幾乎包含了與其證明過程等同的信息量，甚至演算法邏輯本身就是證明過程（隨便翻開一本經典的演算法書，看幾個經典的教科書演算法，你會發現演算法邏輯和演算法證明的聯系有多緊密）。於是我們又回到剛才那個問題：你會去背數學證明么？既然沒人會傻到去背整個證明，又為什麼要生硬地去背演算法呢？
那麼，不背就不背，去理解演算法的證明如何？理解了演算法的證明過程，便更有可能記住演算法的邏輯細節，理解記憶嘛。然而，仍然不幸的是，絕大多數演算法書在這方面做的實在糟糕，證明倒是給全了，邏輯也倒是挺嚴謹的，可是似乎沒有作者能真正還原演算法發明者本身如何得到演算法以及演算法證明的思維過程，按理說，證明的過程應該反映了這個思維過程，但是在下文關於霍夫曼編碼的例子中你會看到，其實飽受贊譽的CLRS和《Algorithms》不僅沒能還原這個過程，反而掩蓋了這個過程。
必須說明的是，沒有哪位作者是故意這樣做的，但任何人在講解一個自己已經理解了的東西的時候，往往會無意識地對自己的講解進行「線性化」，例如證明題，如果你回憶一下高中做平面幾何證明題的經歷，就會意識到，其實證明的過程是一個充滿了試錯，聯想，反推，特例，修改問題條件，窮舉等等一干「非線性」思維的，混亂不堪的過程，而並不像寫在課本上那樣——引理1，引理2，定理1，定理2，一口氣直到最終結論。這樣的證明過程也許容易理解，但絕對不容易記憶。過幾天你就會忘記其中一個或幾個引理，其中的一步或幾步關鍵的手法，然後當你想要回過頭來自己試著去證明的時候，就會發現卡在某個關鍵的地方，為什麼會這樣？因為證明當中並沒有告訴你為什麼作者當時會想到證明演算法需要那麼一個引理或手法，所以，雖說看完證明之後，對演算法這個結論而言你是知其所以然了，但對於演算法的證明過程你卻還沒知其所以然。在我們大腦的記憶系統當中，新的知識必須要和既有的知識建立聯系，才容易被回憶起來（《如何有效地學習與記憶》），聯系越多，越容易回憶，而一個天外飛仙似地引理，和我們既有的知識沒有半毛錢聯系，沒娘的孩子沒人疼，自然容易被遺忘。（為什麼還原思維過程如此困難呢？我曾經在知其所以然（一）里詳述）
正因為絕大多數演算法書上悲劇的演算法證明過程，很多人發現證明本身也不好記，於是寧可選擇直接記結論。當年我在數學系，考試會考證明過程，但似乎計算機系的考試考演算法證明過程就是荒謬的？作為「工程」性質的程序設計，似乎更注重使用和結果。但是如果是你需要在項目中自己設計一個演算法呢？這種時候最起碼需要做的就是證明演算法的正確性吧。我們面試的時候往往都會遇到一些演算法設計問題，我總是會讓應聘者去證明演算法的正確性，因為即便是一個「看上去」正確的演算法，真正需要證明起來往往發現並不是那麼容易。
所以說，絕大多數演算法書在作為培養演算法設計者的角度來說是失敗的，比數學教育更失敗。大多數人學完了初中平面幾何都會做證明題（數學書不會要求你記住幾何所有的定理），但很多人看完了一本演算法書還是一團漿糊，不會證明一些起碼的演算法，我們背了一坨又一坨結論，非但這些結論許多根本用不上，就連用上的那些也不會證明。為什麼會出現這樣的差異？因為數學教育的理想目的是為了讓你成為能夠發現新定理的科學家，而碼農系的演算法教育的目的卻更現實，是為了讓你成為能夠使用演算法做事情的工程師。然而，事情真的如此簡單么？如果真是這樣的話乾脆連演算法結論都不要背了，只要知道演算法做的是什麼事情，時空復雜度各是多少即可。
如果說以上提到的演算法難度（講解和記憶的難度）屬於Accidental Complexity的話，演算法的另一個難處便是Essential Complexity了：演算法設計。還是拿數學證明來類比（如果你看過《Introction to Algorithms：A Creative Approach》就知道演算法和數學證明是多麼類似。），與單單只需證明相比，設計演算法的難處在於，定理和證明都需要你去探索，尤其是前者——你需要去自行發現關鍵的那（幾）個定理，跟證明已知結論相比（已經確定知道結論是正確的了，你只需要用邏輯來連接結論和條件），這件事情的復雜度往往又難上一個數量級。
一個有趣的事實是，演算法的探索過程往往蘊含演算法的證明過程，理想的演算法書應該通過還原演算法的探索過程，從而讓讀者不僅能夠自行推導出證明過程，同時還能夠具備探索新演算法的能力。之所以這么說，皆因為我是個懶人，懶人總夢想學點東西能夠實現以下兩個目的：
一勞永逸：程序員都知道「一次編寫到處運行」的好處，多省事啊。學了就忘，忘了又得學，翻來覆去浪費生命。為什麼不能看了一遍就再也不會忘掉呢？到底是教的不好，還是學得不好？
事半功倍：事實上，程序員不僅講究一次編寫到處運行，更講究「一次編寫到處使用」（也就是俗稱的「復用」）。如果學一個演算法所得到的經驗可以到處使用，學一當十，推而廣之，時間的利用效率便會大大提高。究竟怎樣學習，才能夠使得經驗的外推（extrapolate）效率達到最大呢？
想要做到這兩點就必須盡量從知識樹的「根節點」入手，雖然這是一個美夢，例如數學界尋找「根節點」的美夢由來已久（《跟波利亞學解題》的「一點歷史」小節），但哥德爾一個證明就讓美夢成了泡影（《永恆的金色對角線》））；但是，這並不阻止我們去尋找更高層的節點——更具普適性的解題原則和方法。所以，理想的演算法書或者演算法講解應該是從最具一般性的思維法則開始，順理成章地推導出演算法，這個過程應該盡量還原一個」普通人「思考的過程，而不是讓人看了之後覺得」這怎麼可能想到呢？
以本文上篇提到的霍夫曼編碼為例，第一遍看霍夫曼編碼的時候是在本科，只看了演算法描述，覺得挺直觀的，過了兩年，忘了，因為不知道為什麼要把兩個節點的頻率加在一起看做單個節點——一件事情不知道「為什麼」就會記不牢，知道了「為什麼」的話便給這件事情提供了必然性。不知道「為什麼」這件事情便可此可彼，我們的大腦對於可此可彼的事情經常會弄混，它更容易記住有理有據的事情（從資訊理論的角度來說，一件必然的事情概率為1，信息量為0，而一件可此可彼的事情信息量則是大於0的）。第二遍看是在工作之後，終於知道要看證明了，拿出著名的《Algorithms》來看，邊看邊點頭，覺得講得真好，一看就理解了為什麼要那樣來構造最優編碼樹。可是沒多久，又給忘了！這次忘了倒不是忘了要把兩個節點的頻率加起來算一個，而是忘了為什麼要這么做，因為當時沒有弄清霍夫曼為什麼能夠想到為什麼應該那樣來構造最優編碼樹。結果只知其一不知其二。
必須說明的是，如果只關心演算法的結論（即演算法邏輯），那麼理解演算法的證明就夠了，光背演算法邏輯難記住，理解了證明會容易記憶得多。但如果也想不忘演算法的證明，那麼不僅要理解證明，還要理解證明背後的思維，也就是為什麼背後的為什麼。後者一般很難在書和資料上找到，唯有自己多加揣摩。為什麼要費這個神？只要不會忘記結論不就結了嗎？取決於你想做什麼，如果你想真正弄清演算法設計背後的思想，不去揣摩演算法原作者是怎麼想出來的是不行的。
『貳』 為什麼有人說弄懂了《演算法導論》的90%，就超越了90%的程序員
其實計算機程序底層核心就是各種數學演算法，剩下就是怎麼用代碼去實現數學，世界上有名的計算機程序大牛幾乎都跟數學權威方面的專家有關。
從另一個角度回答，因為就算看懂百分百，也很難超越另外的百分之十
很多程序員沒讀過演算法導論
其實不管是對於在校生來說還是已經工作的程序員，一般很少都會接觸演算法。
學生的話也只有計算機相關專業的開設了數據結構和演算法相關課程的才需要用到，但如果只是對付期末考試的話也沒啥難度。
但是如果在大學期間接觸到演算法競賽就不一樣了，需要花費比較多的精力。
的確在工資上任何公司都是10%的演算法大佬拿的工資比其他90%的業務開發程序員或者其他的程序員都要高，不過就憑只懂《演算法導論》這本書的話還是不太行的，演算法離不開業務的。就算超越也是超越那10%的演算法工程師里的90%，如果能達到這個境界別說BAT了，微軟谷歌都是可以考慮的。
說這個話在我看來他可能是想賣課，賣完再慢慢告訴你，「學到90％也沒有那麼容易」，或者「在刷我這套題這件事上超越90％的程序員 並不等於收入上超越90％的程序員」。
你多去拼多多參加幾個活動，在文字 游戲 和預期管理上你應該就懂了；要是還不懂，大概你也不是那麼適合做這一行以及演算法導論。
公式：弄懂+一本名著+百分比+超越+百分比+你的群體。
例句：
弄懂sicp的67.9%，你就超越了95%的程序員。
弄懂本草綱目的72%，你就超越了93.7%的中醫。
弄懂冰箱說明書的83%，你就超越了99.9%的冰箱使用者（這也許是最真實的，雖然冰箱說明書不是名著……）
至於為什麼這么說……個人覺得就是對xx東西的一種崇拜，很大程度上是人雲亦雲。
演算法導論是本不會動的書，不同人讀效果不一樣的。不要神化某一本書，參差多態乃幸福本源。不看演算法導論你也可以會演算法，你也可以會數據結構，你也可以進大廠。沒有演算法導論的時候也依然有研究演算法的科學家。你能通過他學會知識很好，但你覺得它晦澀，搞不懂，沒有c的代碼讓你學的不舒服，那就不看他。
人生中見書，書中見人生。讀書有時候不一定是為了學東西，可能更多的是一種享受。就像你沒學看過csapp之前，通過各種課程，學了零零碎碎的知識。忽然有一天你看了csapp，你覺得好過癮啊，好爽啊。你覺得你學習的第一天就看csapp能有這種效果嗎？
好書不會變少只會變多，更何況幫到你的也未必需要是好書。也許一本書只是很普通的書，不嚴謹，還都是大白話，但未必就幫不到你。
學東西莫要搞崇拜。很多程序員學習的時候都不是通過演算法導論這本書學的，可他們依然很傑出。
程序員來回答一下：
1.《演算法導論》這本書理論來說90%程序員也沒弄懂，所以你弄懂了就超過了90%。
2.其實程序員是一個大的行業，IT也是一個大的行業，門外人看著都是一群寫程序的，修電腦的，更有人認為是裝電腦系統的，你被別人交過去裝過系統嗎？
3.程序員架構上來說，嵌入式 協議棧 應用 網路 伺服器 工具 系統 等等等！
4.有一些行業是不需要看演算法導論的，更有一些轉行過來的，應該更不太了解演算法導論。
這本書在美國的大學被稱為clrs, 是標準的本科高年級和研究生入門的演算法課課本。優點是比較全面的講解了常用和基本的演算法，習題質量不錯。問題是動態規劃講的不好，篇幅原因一些近代的演算法沒有概括。總的來說是本不錯的演算法入門教科書。
演算法是計算機科學的核心。計算理論偏數學，編譯原理和操作系統偏硬體，真正計算機科學的核心就是演算法。無論做研究還是搞工程，都是必不可少的。
程序是給人看的，不是給機器。寫給機器的程序誰都可以寫出來，但不是每個程序員都能寫出別人看懂的東西
程序是什麼，程序就是數據結構和演算法，弄懂了超90%的程序員不是很正常嘛
看懂2%就超過了80%，沒必要看那麼多
因為這本書翻譯的很枯燥、也很理解，這種情況下你還理解了90%，說明你有耐心，有恆心，耐得住寂寞。我相信不只是做程序員，做其它行業也會很優秀。
『叄』 內部排序演算法的比較課程設計
那六種排序演算法的實現我可以給你，至於隨機數產生，統計比較和交換次數，分析結果之類的你自己做就可以了，稍微加一點就行了。
『肆』 內部排序演算法比較
按平均時間將排序分為四類：
（1）平方階(O(n2))排序 一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；
（2）線性對數階(O(nlgn))排序 如快速、堆和歸並排序；
（3）O(n1+￡)階排序 ￡是介於0和1之間的常數，即0<￡<1，如希爾排序；
（4）線性階(O(n))排序 如桶、箱和基數排序。
各種排序方法比較 簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。 影響排序效果的因素 因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。
不同條件下，排序方法的選擇
(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。 當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。 快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短； 堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。 若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。
(4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。 當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
網路文庫里也有說明，詳見：http://wenku..com/view/51f3b202de80d4d8d15a4fa6.html
下面是一段測試程序：
用系統計時器算時間復雜度。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define LIST_INIT_SIZE 50000
int bj1,yd1,n;
clock_t start_t,end_t;
typedef struct
{
int key;
}ElemType;
typedef struct
{
ElemType *elem;
int length;
}SqList;
void addlist(SqList &L)
{
int i;
a: printf("請輸入你要輸入的個數:");
scanf("%d",&n);
if(n>50000)
{
printf("超出范圍重新輸入!!!\n");
goto a;
}
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(0);
L.length=0;
for(i=1;i<n+1;i++)
{
b: L.elem[i].key=rand();
if(L.elem[i].key>30000)goto b;
++L.length;
}
}
void SelectSort(SqList &L)//選擇
{
start_t=clock();
int i,j,k,bj=0,yd=0;
for(i=1;i<L.length;i++)
{
k=i;
for(j=i+1;j<L.length;j++)
{
bj++;
if(L.elem[j].key<L.elem[k].key)k=j;
}
if(i!=k)
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;
yd+=3;
}
}
end_t=clock();
printf("比較次數為 %d移動次數為 %d\n",bj,yd);
printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);
}
void qipao(SqList &L)//起泡
{
start_t=clock();
int i=1,j,bj=0,yd=0;
while(i<L.length)
{
for(j=1;j<L.length;j++)
{
bj++;
if(L.elem[j].key>L.elem[j+1].key)
{
L.elem[0].key=L.elem[j].key;
L.elem[j].key=L.elem[j+1].key;
L.elem[j+1].key=L.elem[0].key;
yd+=3;
}
}
i++;
}
end_t=clock();
printf("比較次數為 %d移動次數為 %d\n",bj,yd);
printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);
}
void InsertSort(SqList &L)//直接插入
{
start_t=clock();
int i,j,yd=0,bj=0;
for(i=2;i<=L.length;i++)
{
if(L.elem[i].key<L.elem[i-1].key)
{
L.elem[0].key=L.elem[i].key;
yd++;
j=i-1;
bj++;
while(L.elem[0].key<L.elem[j].key)
{
L.elem[j+1].key=L.elem[j].key;
j--;
yd++;
bj++;
}
L.elem[j+1].key=L.elem[0].key;
yd++;
}
}
end_t=clock();
printf("比較次數為 %d移動次數為 %d\n",bj,yd);
printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);
}
void xier(SqList &L)//希爾
{
start_t=clock();
int i,d=L.length/2,j,w=0,k,yd=0,bj=0;
while(w<d)
{
w=1;
for(i=w;i<L.length;i=i+d)
{
k=i;
for(j=i+d;j<L.length;j=j+d)
{
if(L.elem[i].key>L.elem[j].key)
{
k=j;
bj++;
}
}
if(i!=k)
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;
yd+=3;
}
w++;
}
d=d/2;
w=1;
}
end_t=clock();
printf("比較次數為 %d移動次數為 %d\n",bj,yd);
printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);
}
void BeforeSort()
{
yd1=0,bj1=0;
}
void display(int m,int n)
{
printf("比較次數為 %d移動次數為 %d\n",m,n);
}
int Partition(SqList &L,int low,int high)//快速排序
{
int pivotkey;
L.elem[0]=L.elem[low];
yd1++;
pivotkey=L.elem[low].key;
while (low<high)
{
yd1++;
while(low<high&&L.elem[high].key>=pivotkey)
--high;
L.elem[low]=L.elem[high];
bj1++;
yd1++;
while (low<high&&L.elem[low].key<=pivotkey)
++low;
L.elem[high]=L.elem[low];
bj1++;
yd1++;
}
L.elem[low]=L.elem[0];
yd1++;
return low;
}
void QSort(SqList &L,int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
start_t=clock();
BeforeSort();
QSort(L,1,L.length);
display(yd1,bj1);
end_t=clock();
printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);
}
void Merge(ElemType R[],ElemType R1[],int low,int m,int high)//歸並
{
int i=low, j=m+1, k=low;
while(i<=m&&j<=high)
{
if(R[i].key<=R[j].key)
{
bj1++;
R1[k]=R[i];
yd1++;
i++;
k++;
}
else
{
bj1++;
R1[k]=R[j];
yd1++;
j++;
k++;
}
}
while(i<=m)
{
R1[k]=R[i];
yd1++;
i++;
k++;
}
while(j<=high)
{
R1[k]=R[j];
yd1++;
j++;
k++;
}
}
void MergePass(ElemType R[],ElemType R1[],int length, int n)
{
int i=0,j;
while(i+2*length-1<n)
{
Merge(R,R1,i,i+length-1,i+2*length-1);
i=i+2*length;
}
if(i+length-1<n-1)
Merge(R,R1,i,i+length-1,n-1);
else
for(j=i;j<n;j++)
R1[j]=R[j];
}
void MSort(ElemType R[],ElemType R1[],int n)
{
int length=1;
while (length<n)
{
MergePass(R,R1,length,n);
length=2*length;
MergePass(R1,R,length,n);
length=2*length;
}
}
void MergeSort(SqList &L)
{
start_t=clock();
BeforeSort();
MSort(L.elem,L.elem,L.length);
display(yd1,bj1);
end_t=clock();
printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);
}
void main()
{
SqList L;
addlist(L);
printf("起泡排序: \n");
qipao(L);
addlist(L);
printf("直插排序: \n");
InsertSort(L);
addlist(L);
printf("選擇排序: \n");
SelectSort(L);
addlist(L);
printf("希爾排序: \n");
xier(L);
addlist(L);
printf("快速排續: \n");
QuickSort(L);
addlist(L);
printf("歸並排序: \n");
MergeSort(L);
}