‘壹’ 算法怎么就这么难
广大码农同学们大多都有个共识，认为算法是个硬骨头，很难啃，悲剧的是啃完了还未必有用——除了面试的时候。实际工程中一般都是用现成的模块，一般只需了解算法的目的和时空复杂度即可。
不过话说回来，面试的时候面算法，包括面项目中几乎不大可能用到的算法，其实并不能说是毫无道理的。算法往往是对学习和理解能力的一块试金石，难的都能掌握，往往容易的事情不在话下。志于高者得于中。反之则不成立。另一方面，虽说教科书算法大多数都是那些即便用到也是直接拿模块用的，但不幸的是，我们这群搬砖头的有时候还非得做些发明家的事情：要么是得把算法当白盒加以改进以满足手头的特定需求；要么干脆就是要发明轮子。所以，虽说面试的算法本身未必用得到，但熟悉各种算法的人通常更可能熟悉算法的思想，从而更可能具备这里说的两种能力。
那么，为什么说算法很难呢？这个问题只有两种可能的原因：
算法本身就很难。也就是说，算法这个东西对于人类的大脑来说本身就是个困难的事儿。
讲得太烂。
下面会说明，算法之所以被绝大多数人认为很难，以上两个原因兼具。
我们说算法难的时候，有两种情况：一种是学算法难。第二种是设计算法难。对于前者，大多数人（至少我当年如此）学习算法几乎是在背算法，就跟背菜谱似的（“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);
}