程序员快速排序方法

⑴ 数据结构一道排序题怎么排啊我想知道思路 答案已经有请告诉帮我分析一下

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

A[1] A[2] A[3] A[4] A[5] A[6] A[7]：

49 38 65 97 76 13 27

进行第一次交换后： 27 38 65 97 76 13 49

( 按照算法的第三步从后面开始找

进行第二次交换后： 27 38 49 97 76 13 65

( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后： 27 38 13 97 76 49 65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后： 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态 {49 38 65 97 76 13 27}

进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

分别对前后两部分进行快速排序 {13} 27 {38}

结束 结束 {49 65} 76 {97}

49 {65} 结束

结束

图6 快速排序全过程

1）、设有N（假设N=10）个数，存放在S数组中；

2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；

3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下，那么第一躺快速排序的过程是：

数组下标： 1 2 3 4 5 6 7 8 9 10

45 36 18 53 72 30 48 93 15 36

I J

（1） 36 36 18 53 72 30 48 93 15 45

（2） 36 36 18 45 72 30 48 93 15 53

（3） 36 36 18 15 72 30 48 93 45 53

（4） 36 36 18 15 45 30 48 93 72 53

（5） 36 36 18 15 30 45 48 93 72 53

通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。

一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法，我不知道它是不是现有排序方法中最快的，但它是我见过的最快的。排序同样的数组，它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

“快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。

我这样讲你们是不是很胡涂，不要紧，我下面给出实现的两个函数：

/*
n就是需要排序的数组，left和right是你需要排序的左界和右界，
如果要排序上面那个数组，那么left和right分别是0和9
*/

void quicksort(int n[], int left,int right)
{
int dp;
if (left<right) {

/*
这就是下面要讲到的函数，按照上面所说的，就是把所有小于53的数放
到它的左边，大的放在右边，然后返回53在整理过的数组中的位置。
*/
dp=partition(n,left,right);

quicksort(n,left,dp-1);

quicksort(n,dp+1,right); //这两个就是递归调用，分别整理53左边的数组和右边的数组
}
}

我们上面提到先定位第一个数，然后整理这个数组，把比这个数小的放到它的左边，大的放右边，然后

返回这中间值的位置，下面这函数就是做这个的。
int partition(int n[],int left,int right)
{
int lo,hi,pivot,t;

pivot=n[left];
lo=left-1;
hi=right+1;

while(lo+1!=hi) {
if(n[lo+1]<=pivot)
lo++;
else if(n[hi-1]>pivot)
hi--;
else {
t=n[lo+1];
n[++lo]=n[hi-1];
n[--hi]=t;
}
}

n[left]=n[lo];
n[lo]=pivot;
return lo;
}

这段程序并不难，应该很好看懂，我把过程大致讲一下，首先你的脑子里先浮现一个数组和三个指针，第一个指针称为p指针，在整个过程结束之前它牢牢的指向第一个数，第二个指针和第三个指针分别为lo指针和hi指针，分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近，在逼近的过程中不停的与p指针的值比较，如果lo指针的值比p指针的值小，lo++，还小还++，再小再++，直到碰到一个大于p指针的值，这时视线转移到hi指针，如果 hi指针的值比p指针的值大，hi--，还大还--，再大再--，直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面，这时把p指针的值和碰面的值做一个调换，然后返回p指针新的位置。

⑵ C语言快速排序算法问题

快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。
一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。
附上快速排序代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<stdio.h>
void quicksort(int a[],int left,int right)
{
int i,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp&&j>i)
i++;
if(j>i)
a[j--]=a[i];

}
a[i]=temp;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
void main()
{
int a[]={53,12,98,63,18,72,80,46,32,21};
int i;
quicksort(a,0,9);
/*排好序的结果*/
for(i=0;i<10;i++)
printf("%4d\n",a[i]);
}

⑶ 一个优秀的程序员应该学完哪些计算机理论的知识

1、循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

2、入队运算：在循环队列的队尾加入一个新元素。上溢：当循环队列非空，且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。

3、退队运算：在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进一，然后将排头指针指向的元素赋给指定的变量。下溢：当循环队列为空时，不能进行退队运算。

⑷ 快速排序mpi算法进程为2时为什么加速不明显

2012年偶决定开始写博客了，不为别的，就希望可以通过博客记录我的成长历程同时也希望可以帮助一些刚毕业，刚入行业的兄弟姐们们。我们是一群充满浮躁、抱怨、迷茫的程序猿，想一想3年就这么过去了，社会变得更浮躁了，鸭梨也越来越大，房?车?女人?… 抓狂… 决定写这样一篇文章，再次明确自己的职业规划，也送给浮躁的你，踏上程序猿这条路可谓是路途艰辛，乏味，枯燥，在这里把自己的学习心得，目前正在计划的规划，列出来。希望对你有所帮助。 1、多动手，多思考 不要怕做不好，刚毕业或者刚入行最缺的就是工作经验，没有别的途径，只有做，做，做，多做经验就来了。项目做多了自然而然你就有了多种不同项目的业务逻辑，这些可是在大学根本无法学到的东西，也是企业最需要的。 任何一个企业需要的是一个快速上手，马上解决业务任务的员工。面对现在层出不穷的新技术，各种复杂的业务逻辑需求，你是如何去应对呢?很简单：做，做，做，我的学习过程就一个字：做! 截止目前从0 到 1 真的很辛苦，大大小小做了上百个(包括接的大大小小单子需求，之前公司各种业务需求解决)，总结就一句话：做的多了 沟通就多了，沟通多了就更好的理解客户需求和用户展示的一些基本经验。 2、少抱怨，多学习 当你刚进公司时，难免会做很多杂事，这个是无法避免。我刚进这个行业做了大半年的杂事，什么DIV，CSS，JS 调个模板 改个小东西，等等。一切都是熬出来的，只有当你的经验，技术积累到了足够 应付业务需求的时候，你自然会被赏识，当然如果还是无法赏识，建议你可以立马跳槽。对于程序员来说偶尔的跳槽也是成长的一部分，不知道对被人是否是这样，但对我来说我的每次跳槽都会 一次快速成长。 作为程序猿我觉得如果真想做好，必须要有兴趣，写代码会让你疯狂，让你疯癫，这样你才能写好它。如果你只是为了工作而去做，那么你只是一个工具而非程序猿，那么你也就 不要过于频繁跳槽，因为每次跳槽对你来说都是一个大的挑战。有了兴趣，支持以恒，不要在乎任务多，压力大，能做就做，你的目的就是提高自己，让自己在明天比昨天更有价值，当价值积累到了足够 的资本，很多公司会抢着要你，相信这个社会肯定会有识才的公司。耐心+机遇+坚定不移的信念，这就是我!一个简单的程序猿。 3、制定有效的学习计划 当你制定了计划，就一定要坚持的完成，如果不能，请你不要制定计划，因为这样会让你很痛苦。在公司或者各类技术社区尽量多认识大牛，多加群，多交流、讨论，多帮助别人。 在制定计划时，不要过于盲目。根据自身情况制定各个阶段计划，最好的计划是短期计划并且可以保证顺利完成的计划，如果制定一个飘渺无期的计划，你更适合当一个演说家。 请不要吝啬，在你计划学习的过程中尽量写到博客，比如CSDN博客 就是很不错的选择。这样你即可以帮助新手，也可以让自己更深入的熟悉学习的知识，并在需要是最快的速度查找到。 废话基本说完了，下面介绍下我近期整理的计划和一些学习心得，希望我们可以一起进步，一起提升，一起为了明天的更多薪资而努力。 PHP程序员突破成长瓶颈?(整理于网上，并自己也在逐条实施中) 对PHP的掌握不精(很多PHP手册都没有看完，库除外) 知识面比较窄(面对需求，除开使用PHP和mysql ，不知道其它的解决办法) PHP代码以过程为主，认为面向对象的实现太绕，看不懂 这些PHPer 在遇到需要高性能，处理高并发，大量数据的项目或业务逻辑比较复杂(系统需要解决多领域业务的问题)时，缺少思路。不能分析问题的本质，技术判断力比较差，对于问题较快能找出临时的解决办法，但常常在不断临时性的解决办法中，系统和自己一步步走向崩溃。那怎么提高自己呢?怎么可以挑战难度更高的系统? 高性能系统的挑战在哪里? 如何选择WEB服务器?要不要使用fast-cgi 模式 要不要使用反向代理服务?选择全内存缓存还是硬盘缓存? 是否需要负载均衡?是基于应用层，还是网络层? 如何保证高可靠性? 你的PHP代码性能如何，使用优化工具后怎么样? 性能瓶颈在那里? 是否需要写成C的扩展? 用户访问有什么特点，是读多还是写多?是否需要读写分离? 数据如何存储?写入速度和读出速度如何? 数据增涨访问速读如何变化? 如何使用缓存? 怎么样考虑失效?数据的一致性怎么保证? 高复杂性系统的挑战在哪里? 能否识别业务所对应的领域?是一个还是多个? 能否合理对业务进行抽象，在业务规则变化能以很小的代价实现? 数据的一致性、安全性可否保证? 是否撑握了面向对象的分析和设计的方法 当我所列出的问题，你都能肯定的回答，我想在技术上你基本已经可能成为架构师了。 怎么样提高，突破瓶颈? 分析你所使用的技术其原理和背后运行的机制，这样可以提高你的技术判断力，提高你技术方案选择的正确性; 学习大学期间重要的知识， 操作系统原理，数据结构和算法。知道你以前学习都是为了考试，但现在你需要为自己学习，让自己知其所以然。 重新开始学习C语言，虽然你在大学已经学过。这不仅是因为你可能需要写PHP扩展，而且还因为，在做C的应用中，有一个时刻关心性能、内存控制、变量生命周期、数据结构和算法的环境。 学习面向对象的分析与设计，它是解决复杂问题的有效的方法。学习抽象，它是解决复杂问题的唯一之道。 “这么多的东西怎么学，这得学多久呀” ? 如果你努力的话，有较好的规划，估计需要1~2年的时间，怎么学习的问题，我们后续再谈。 PHP学习的过程网上已经有很多教程了，就不列举了。基础+数据结构+算法(PHP这个比较弱) 不断重复的学习使用 其次是设计模式，尤其复杂的业务需求设计模式非常有帮助，我博客也会不断地学习，讲解各种设计模式的用法。 积累：把常用的一些库(用过的，自己写的)都收集起来，挡在用到时拿出来用即可，非常方便。如：分页，图片处理，上传，下载，EMAIL等等这些常用到的。 多方位动手：不光要写代码，把代码片段分析放到博客 也是进步提升的一个重要的环节，加深记忆不错的方法。 1.PHP基础入门(语法，常用函数和扩展) 2.面向对象的PHP(书籍：《深入PHP，面向对象、模式与实践》) 3.网站软件架构设计(设计模式、框架等) 4.网站物理层次架构设计(分布式计算、存储、负载均衡、高可用性等) 引用：一个不错的网上找到的学习建议 如何有效的学习是一个大问题。 自己有些实践但很零散，不好总结。昨天晚上睡觉前，突然想到了RUP的核心，“以架构为中心，用例驱动，迭代开发”，借用这个思想，关于有效的学习的方法，可以这样来表述： 以原理、模型或机制为中心，任务驱动，迭代学习 目的：学习如何提高处理性能。 可迭代驱动的任务：通过IP找到所在地域。 这是WEB应用常见的任务，IP数据库是10左右万行的记录。 第一次迭代：不考虑性能的情况下实现功能(通过PHP来实现) 因为无法直接通过KEY(IP)进行查找地域，所以直接放到数据或通过关联数组这种简单的方法都是不行的。思路还是先把数据进行排序，然后再进行查找 1. 如何通过IP查找? 已序的数据，二分查找是最快的。 2. 如何排序?用库函数sort当然 是可以，但是即然是学习，那还是自己实现快速排序吧。 学习目标：排序算法，查找算法 PHPer 数据结构和算法基础比较差，平时也没有这方面的任务，自己也不学习，因此这方面的知识很缺乏。 但是，编程解决的问题，最终都会归结到数据结构和对这种数据结构操作的算法。 如果数据结构算法常在心中，那遇到问题就能清晰认识到它内在的结构，解决方法就会自然产生。 第二次迭代：优化数据的加载与排序 如果做到第一步，那基本上还是不可用，因为数据每次都需要的加载和排序，这样太耗时间。 解决的思路是，数据一次加载排序后，放到每个PHP进程能访问到的地方 放到memcache 这是大家容易想到问题。 其实放到共享内存(EA等加速器都支持)中是更快的方式，因为memcache还多了网络操作。 数据是整体放入到共享内存，还是分块放入，如何测试性能? 如何分析瓶颈所在(xdebug)? 在这些问题的驱动下你会学习到 学习目标：检测、定位、优化PHP性能的方法; PHP实现结构对性能的影响。 第三次迭代：编写PHP的扩展 怎么确定需要学习的机制和原理呢? 怎么找到驱动学习任务呢? 从这个技术的定位来找出需要学习的重点，即它怎么做到(机制)的和它为什么能这样做到 (模型或原理) 列出这个技术最常见的应用，做为学习的任务，从简到难进行实践。 如果完全自学，找到需要学习的要点(机制、模型、原理) 设定学习任务的确不是那么容易把握。如果找到一个有经验的人来指导你或加一个学习型的团队，那学习的速度的确会大大提高。 最后简单总结下： 1、一定要有耐心，制定好计划一定要实施 2、PHP基础比较吃透，手动多了自然就会记得更深(PHP手册一定要多次反复的阅读) 3、PHP设计模式并在实际场景中尝试应用，不断地加强记忆和理解设计模式 4、现在新东西真的太快，所以为了适应就必须要多下功夫。内存缓存，文件缓存，静态缓存，高并发处理，这些必须要熟练应用。 5、加强计算机系统原理的了解，熟悉常用数学知识，练习算法应用。计算机科学本质上讲是数学的一个学科。好的数学家中间会产出优秀的程序员。不要让你的数学能力丧失殆尽。 逻辑学、离散数学、微积分、概率论、统计学、抽象代数、数论、范畴论、偏序理论这些数学知识尽量多练习，多熟悉下。 6、关注PHP安全，了解最新PHP，MYSQL版本更新和BUG动态。 7、深入学习数据结构和算法，不论是什么语言 最核心的就是数据结构和算法。 8、开始学习C，或者同步和PHP进行也可以，看你的时间和学习强度计划了。C是必须要学，如果你想走程序猿这条道路的话。PHP也是C写的，而且 PHP运行机制也是通过编译器编译成C在电脑上运行，所以C学好了对你的开发之路只有益处。你的money 也会 赚的比以前 更多! 最后：认真做好每一项，学扎实，重复的去学。不知不觉中你的能力会得到很快的提升。 最后想说，没什么可以烦心的，不是所有人都是千里马，也不是所有人都是伯乐。如果你是千里马你可以慢慢寻找能赏识你的伯乐，如果你是伯乐也希望你早点找到属于你的千里马。 文章来源：刘昕明的博客

⑸ 谁能帮我讲解一下 作业排序的一个更快算法的思想～

快速排序是一种分割处理式的排序算法，它将一个复杂的排序问题分解为若干较容易处理的排序问题，然后逐一解决。在快速排序算法中，首先要从数据集的数据中选择一个数据作为分割值，然后将数据分成以下3个子集：
(1) 将大于分割值的数据移到分割值前面，组成子集1；
(2) 分割值本身为子集2；
(3) 将小于分割值的数据移到分割值后面，组成子集3。
等于分割值的数据可以放在任意一个子集中，这对快速排序算法没有任何影响。由于子集2已经是有序的，所以此后只需对子集1和子集3进行快速排序。

需要注意的是，当数据集很小时，无法进行快速排序，而要使用其它排序算法。显然，当数据集中的数据只有两个或更少时，就不可能将数据集再分割成三个子集。实际上，当数据集比较小时，程序员就应该考虑是否仍然采用快速排序算法，因为在这种情况下另外一些排序算法往往更快。

⑹ 作为程序员提高编程能力的几个基础算法

一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1从数列中挑出一个元素，称为“基准”（pivot），

2重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

二：堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

创建一个堆H[0..n-1]

把堆首（最大值）和堆尾互换

3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4.重复步骤2，直到堆的尺寸为1

三：归并排序

归并排序（Mergesort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4.重复步骤3直到某一指针达到序列尾

5.将另一序列剩下的所有元素直接复制到合并序列尾

四：二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

五：BFPRT(线性查找算法)

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。

1.将n个元素每5个一组，分成n/5(上界)组。

2.取出每一组的中位数，任意排序方法，比如插入排序。

3.递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

4.用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

5.若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。

六：DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤：

1.访问顶点v；

2.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

上述描述可能比较抽象，举个实例：

DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

七：BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。

BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

1.首先将根节点放入队列中。

2.从队列中取出第一个节点，并检验它是否为目标。

如果找到目标，则结束搜寻并回传结果。

否则将它所有尚未检验过的直接子节点加入队列中。

3.若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

4.重复步骤2。

八：Dijkstra算法

戴克斯特拉算法（Dijkstra’salgorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E表示G中所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负权重（weight）。边的权重可以想象成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

1.初始时令S=,T=，T中顶点对应的距离值

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>，d(V0,Vi)为∞

2.从T中选取一个其距离值为最小的顶点W且不在S中，加入S

3.对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

九：动态规划算法

动态规划（Dynamicprogramming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

关于动态规划最经典的问题当属背包问题。

1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

十：朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

尽管是带着这些朴素思想和过于简单化的假设，但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

通过掌握以上算法，能够帮你迅速提高编程能力，成为一名优秀的程序员。

⑺ 求编程领域上一些经典算法同时也是程序员必须掌握的算法

这是我在一个论坛里看到的，你也参考参考吧。C++的虚函数
======================
C++使用虚函数实现了其对象的多态，C++对象的开始四个字节是指向虚函数表的指针，其初始化顺序是先基类后派生类，所以该虚函数表永远指向最后一个派生类，从而实现了相同函数在不同对象中的不同行为，使得对象既有共性，又有其个性。

内存池分配、回收之伙伴算法
=======================
伙伴算法是空闲链表法的一个增强算法，依次建立2^0\2^1\2^2\2^3...2^n大小的 内存块空闲链表，利用相邻内存块的伙伴性质，很容易将互为伙伴的内存块进行合并移到相应的空闲链表或将一块内存拆分成两块伙伴内存，一块分配出去，另一块挂入相应空闲链表，使得内存的分配和回收变得高效。

AVL树
=======================
AVL树是一个平衡二叉树，其中序遍历是从小到大排序的，该结构插入节点和检索非常高效，被广泛应用

快速排序
=======================
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。效率非常高

密码学之非对称加密协议（公钥、私钥加密协议）
======================
非对称加密算法需要两个密钥，用其中一个加密产生的密文，只能通过另外一个密钥解密，密钥持有者A可以将其中一个公开，称为公用密钥，另外一个秘密保存称为私钥，这样当某人B想给A传一封秘信时，只要将密信使用A的公钥加密后，就可以放心使用各种信道将迷信传给A了，因为该密信只有A可以解密，第三者截取因为无法解密而毫无意义。
该算法很好地解决了密钥的安全传递的问题，因为公钥和加密算法都是公开的，私钥不需要传输。

密码学之数字签名协议（身份鉴别、防抵赖）
======================
数字签名也是建立在非对称加密基础之上的，如果A君用它的私钥将文件加密后在发布，A君就无法抵赖该文件是其发布的，因为其他人能通过A君的公钥将文件解密就说明，如果算法可靠，该文件一定是A君用其私钥加密的。
由于非对称加密算法的加密和解密很慢，现在的数字签名并非是将其要发布的信息用其私钥加密，而是先用一个单项散列算法如（MD5）产生一个该信息的比较短的指纹（hash值），对其指纹用其私钥加密后和信息一并发布，同样达到了防抵赖的作用。

无回溯字符串模式匹配-kmp算法
======================
他是根据子串的特征，当匹配失败时，不需要回溯，而是直接将字串向后滑动若干个字节，继续匹配，极大提高了匹配速度。该算法被广泛使用。详细请参考数据结构教程。

最小路径选路-迪杰斯特拉算法、弗洛伊德算法
======================
学习数据结构的时候，印象最深的就要算kmp算法和最小路径算法了，因为理解他们比较费脑子，我是不可能发明这些算法了，发明他们的都是天才，呵呵。
使用最短路径的算法曾经帮人写过一个小东西，还是很有效的，记得是使用的弗洛伊德算法的一个变种，要详细了解的朋友可以查找相关资料，想将他们使用在你的项目中，代码直接从教科书上抄就可以了，不需要理解。

tcp协议之-nagle算法
======================
tcp、ip中令人叫绝的想法很多，印象最深的要算nagle算法了。
tcp出于效率和流量控制的考虑，发送端的数据不是产生多少就马上发送多少，一般是等到数据集聚到发送缓冲区长度的一半或者数据达到最大tcp数据包数据部分长度（好像是65515）才启动发送，而且还要看接受端可用缓冲区的大小，如果接受端产生一个回应报文通知发送端没有接受空间了，发送端哪怕缓冲区已经满了，也不会启动发送，直到接受端通告发送端其已经有了接受数据的空间了。
这样就有一个问题，假如发送端就是要发送一个小报文（比如10个字节），然后等待对方的回应。按照上面的方案，tcp会一直等数据收集到一定量才发送，于是矛盾就产生了。应用层不再发数据，tcp等不到足够的数据不会将10个字的数据发送到网卡，接收端应用层收不到数据就不会回应发送端。
你也可能说，可以让修改发送端发送条件，不一定要等到足够的数据再发送，为了效率考虑，可以考虑延时一定的时间，比如说1秒，如果上层还没有数据到来，就将发送缓冲中的数据发出去。当然这样也是可行的，尽管应用端白白等了1秒钟啥也没干，呵呵。
其实nagle算法很好解决了该问题，它的做发是链接建立后的第一次发送不用等待，直接将数据组装成tcp报文发送出去，以后要么等到数据量足够多、要么是等到接受方的确认报文，算法及其简单，而且很好解决了上面的矛盾。

socket之io模型设计
======================
windows下socket有两种工作方式：
1）同步方式
2）异步方式

同步socket又有两种工作模式：
1）阻塞模式
2）非阻塞模式

阻塞模式是最简单的工作模式，以tcp的发送数据为例，如果发送缓冲区没有空间，send调用就不会返回，一直要等到能够发出一点数据为止，哪怕是一个字节，但是send返回并不表示我要发送的数据已经全部提交给了tcp，所以send返回时要检查这次发送的数量，调整发送缓冲指针，继续发送，直到所有数据都提交给了系统。
由于其阻塞的特性，会阻塞发送线程，所以单线程的程序是不适合使用阻塞模式通信的，一般使用一个连接一个线程的方法，但是这种方式对于要维护多个连接的程序，是个不好的选择，线程越多，开销越大。

同步非阻塞模式的socket不会阻塞通信线程，如果发送缓冲区满，send调用也是立刻返回，接受缓冲区空，recv也不会阻塞，所以通信线程要反复调用send或recv尝试发送或接收数据，对cpu是很大的浪费。
针对非阻塞的尴尬，接口开发人员发明了三种io模型来解决该问题：
1）选择模型（select）
2）异步选择模型（AsyncSelect）
3）事件选择模型（EventSeselect）
其思想是根据io类型，预先查看1个或n个socket是否能读、写等。
其select本身来说，select是阻塞的，可以同时监视多个socket，只要所监视的其中一个socket可以读、写，secect调用才返回
异步选择模型其select是异步的（异步是不会阻塞的），是将监视任务委托给系统，系统在socket可读、写时通过消息通知应用程序。有一点需要说明，假如应用程序已经有很多数据需要发送，当收到可写通知时，一定要尽量多地发送数据，直到发送失败，lasterror提示“将要阻塞”，将来才可能有新的可写通知到来，否则永远也不会有。
事件选择模型也是将监视socket状态的工作委托给系统，系统在适当的时候通过事件通知应用程序socket可以的操作。

除了同步工作方式外，还有一种叫异步工作方式
异步工作方式是不会阻塞的，因为是将io操作本身委托给系统，系统在io操作完成后通过回调例程或事件或完成包通知应用程序
异步工作方式有两种io模型和其对应，其实这两种模型是window是异步io的实现：
1）重叠模型
2）完成端口

重叠模型通过事件或回调例程通知应用程序io已经完成
完成端口模型比较复杂，完成端口本身其实是一个io完成包队列。
应用程序一般创建若干个线程用来监视完成端口，这些线程试图从完成端口移除一个完成包，如果有，移除成功，应用程序处理该完成包，否则应用程序监视完成端口的线程被阻塞。

select模型是从UNIX上的Berkeley Software Distribution(BSD)版本的套接字就实现了的，其它四种io模型windows发明的，在windows中完成端口和异步选择模型是使用比较广泛的，一般分别用于服务端和客户端开发。
这五种io模型设计还是比较巧妙的：三种选择模型很好解决了“同步非阻塞”模式编程的不足；重叠模型和完成端口是windows异步io的经典实现，不局限于网络io，对文件io同样适用。

说点题外话，socket的send完成仅仅是将数据（可能是部分）提交给系统，而不是已经发送到了网卡上，更不是已经发送到了接收端。所以要知道你的数据已经发送到了对方的应用层的唯一方法是，让对方给你发送一个应对包。
发送数据要注意，对应tcp，要防止发送和接收的乱序，对于发送，一般应该为每一个链接建立一个发送队列，采用类似nagle的算法启动数据发送。
一次发送可能是你提交数据的一部分，一定要当心，否则出问题没处找去。

⑻ 快速排序算法的排序演示

假设用户输入了如下数组： 下标 0 1 2 3 4 5 数据 6 2 7 3 8 9 创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。
我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较： 下标 0 1 2 34 5 数据 3 2 7 6 8 9 i=0 j=3 k=6
接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表： 下标 0 1 2 3 4 5 数据 3 2 6 7 8 9 i=2 j=3 k=6
称上面两次比较为一个循环。
接着，再递减变量j，不断重复进行上面的循环比较。
在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大： 下标 0 1 2 3 4 5 数据 3 2 6 7 8 9 如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。
然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。
注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。 在c++中可以用函数qsort（）可以直接为数组进行排序。
用 法:
void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
参数：1 待排序数组首地址2 数组中待排序元素数量3 各元素的占用空间大小4 指向函数的指针，用于确定排序的顺序

⑼ C语言中快速排序法的原理及应用

“快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。

一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。

附上快速排序代码：

#include<stdio.h>
voidquicksort(inta[],intleft,intright)
{
inti,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp&&j>i)
i++;
if(j>i)
a[j--]=a[i];

}
a[i]=temp;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
voidmain()
{
inta[]={53,12,98,63,18,72,80,46,32,21};
inti;
quicksort(a,0,9);
/*排好序的结果*/
for(i=0;i<10;i++)
printf("%4d
",a[i]);
}

⑽ 冒泡排序法和快速排序比较的算法

打你屁股，这么简单的问题都不认真研究一下。

冒泡排序是最慢的排序，时间复杂度是 O(n^2)。

快速排序是最快的排序。关于快速排序，我推荐你看看《代码之美》第二章：我编写过的最漂亮的代码。作者所说的最漂亮，就是指效率最高的。

--------------------------------摘自《代码之美》---------------

当我撰写关于分治（divide-and-conquer）算法的论文时，我发现C.A.R. Hoare的Quicksort算法（“Quicksort”，Computer Journal 5）无疑是各种Quicksort算法的鼻祖。这是一种解决基本问题的漂亮算法，可以用优雅的代码实现。我很喜欢这个算法，但我总是无法弄明白算法中最内层的循环。我曾经花两天的时间来调试一个使用了这个循环的复杂程序，并且几年以来，当我需要完成类似的任务时，我会很小心地复制这段代码。虽然这段代码能够解决我所遇到的问题，但我却并没有真正地理解它。
我后来从Nico Lomuto那里学到了一种优雅的划分（partitioning）模式，并且最终编写出了我能够理解，甚至能够证明的Quicksort算法。William Strunk Jr.针对英语所提出的“良好的写作风格即为简练”这条经验同样适用于代码的编写，因此我遵循了他的建议，“省略不必要的字词”（来自《The Elements of Style》一书）。我最终将大约40行左右的代码缩减为十几行的代码。因此，如果要回答“你曾编写过的最漂亮代码是什么？”这个问题，那么我的答案就是：在我编写的《Programming Pearls, Second Edition》(Addison-Wesley)一书中给出的Quichsort算法。在示例2-1中给出了用C语言编写的Quicksort函数。我们在接下来的章节中将进一步地研究和改善这个函数。
【示例】 2-1 Quicksort函数
void quicksort(int l, int u)
{ int i, m;
if (l >= u) return; 10
swap(l, randint(l, u));
m = l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
如果函数的调用形式是quicksort(0, n-1)，那么这段代码将对一个全局数组x[n]进行排序。函数的两个参数分别是将要进行排序的子数组的下标：l是较低的下标，而u是较高的下标。函数调用swap(i,j)将会交换x[i]与x[j]这两个元素。第一次交换操作将会按照均匀分布的方式在l和u之间随机地选择一个划分元素。
在《Programming Pearls》一书中包含了对Quicksort算法的详细推导以及正确性证明。在本章的剩余内容中，我将假设读者熟悉在《Programming Pearls》中所给出的Quicksort算法以及在大多数初级算法教科书中所给出的Quicksort算法。
如果你把问题改为“在你编写那些广为应用的代码中，哪一段代码是最漂亮的？”我的答案还是Quicksort算法。在我和M. D. McIlroy一起编写的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原来Unix qsort函数中的一个严重的性能问题。随后，我们开始用C语言编写一个新排序函数库，并且考虑了许多不同的算法，包括合并排序（Merge Sort）和堆排序（Heap Sort）等算法。在比较了Quicksort的几种实现方案后，我们着手创建自己的Quicksort算法。在这篇文章中描述了我们如何设计出一个比这个算法的其他实现要更为清晰，速度更快以及更为健壮的新函数——部分原因是由于这个函数的代码更为短小。Gordon Bell的名言被证明是正确的：“在计算机系统中，那些最廉价，速度最快以及最为可靠的组件是不存在的。”现在，这个函数已经被使用了10多年的时间，并且没有出现任何故障。
考虑到通过缩减代码量所得到的好处，我最后以第三种方式来问自己在本章之初提出的问题。“你没有编写过的最漂亮代码是什么？”。我如何使用非常少的代码来实现大量的功能？答案还是和Quicksort有关，特别是对这个算法的性能分析。我将在下一节给出详细介绍。
2.2 事倍功半
Quicksort是一种优雅的算法，这一点有助于对这个算法进行细致的分析。大约在1980年左右，我与Tony Hoare曾经讨论过Quicksort算法的历史。他告诉我，当他最初开发出Quicksort时，他认为这种算法太简单了，不值得发表，而且直到能够分析出这种算法的预期运行时间之后，他才写出了经典的“Quicksoft”论文。
我们很容易看出，在最坏的情况下，Quicksort可能需要n2的时间来对数组元素进行排序。而在最优的情况下，它将选择中值作为划分元素，因此只需nlgn次的比较就可以完成对数组的排序。那么，对于n个不同值的随机数组来说，这个算法平均将进行多少次比较？
Hoare对于这个问题的分析非常漂亮，但不幸的是，其中所使用的数学知识超出了大多数程序员的理解范围。当我为本科生讲授Quicksort算法时，许多学生即使在费了很大的努力之后，还是无法理解其中的证明过程，这令我非常沮丧。下面，我们将从Hoare的程序开
11
始讨论，并且最后将给出一个与他的证明很接近的分析。
我们的任务是对示例2-1中的Quicksort代码进行修改，以分析在对元素值均不相同的数组进行排序时平均需要进行多少次比较。我们还将努力通过最短的代码、最短运行时间以及最小存储空间来得到最深的理解。
为了确定平均比较的次数，我们首先对程序进行修改以统计次数。因此，在内部循环进行比较之前，我们将增加变量comps的值（参见示例2-2）。
【示例2-2】 修改Quicksort的内部循环以统计比较次数。
for (i = l+1; i <= u; i++) {
comps++;
if (x[i] < x[l])
swap(++m, i);
}
如果用一个值n来运行程序，我们将会看到在程序的运行过程中总共进行了多少次比较。如果重复用n来运行程序，并且用统计的方法来分析结果，我们将得到Quicksort在对n个元素进行排序时平均使用了1.4 nlgn次的比较。
在理解程序的行为上，这是一种不错的方法。通过十三行的代码和一些实验可以反应出许多问题。这里，我们引用作家Blaise Pascal和T. S. Eliot的话，“如果我有更多的时间，那么我给你写的信就会更短。”现在，我们有充足的时间，因此就让我们来对代码进行修改，并且努力编写出更短（同时更好）的程序。
我们要做的事情就是提高这个算法的速度，并且尽量增加统计的精确度以及对程序的理解。由于内部循环总是会执行u-l次比较，因此我们可以通过在循环外部增加一个简单的操作来统计比较次数，这就可以使程序运行得更快一些。在示例2-3的Quicksort算法中给出了这个修改。
【示例2-3】 Quicksort的内部循环，将递增操作移到循环的外部
comps += u-l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
这个程序会对一个数组进行排序，同时统计比较的次数。不过，如果我们的目标只是统计比较的次数，那么就不需要对数组进行实际地排序。在示例2-4中去掉了对元素进行排序的“实际操作”，而只是保留了程序中各种函数调用的“框架”。
【示例2-4】将Quicksort算法的框架缩减为只进行统计
void quickcount(int l, int u)
{ int m;
if (l >= u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
12
这个程序能够实现我们的需求，因为Quichsort在选择划分元素时采用的是“随机”方式，并且我们假设所有的元素都是不相等的。现在，这个新程序的运行时间与n成正比，并且相对于示例2-3需要的存储空间与n成正比来说，现在所需的存储空间缩减为递归堆栈的大小，即存储空间的平均大小与lgn成正比。
虽然在实际的程序中，数组的下标（l和u）是非常重要的，但在这个框架版本中并不重要。因此，我们可以用一个表示子数组大小的整数(n)来替代这两个下标（参见示例2-5）
【示例2-5】 在Quicksort代码框架中使用一个表示子数组大小的参数
void qc(int n)
{ int m;
if (n <= 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
现在，我们可以很自然地把这个过程整理为一个统计比较次数的函数，这个函数将返回在随机Quicksort算法中的比较次数。在示例2-6中给出了这个函数。
【示例2-6】 将Quicksort框架实现为一个函数
int cc(int n)
{ int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
在示例2-4、示例2-5和示例2-6中解决的都是相同的基本问题，并且所需的都是相同的运行时间和存储空间。在后面的每个示例都对这些函数的形式进行了改进，从而比这些函数更为清晰和简洁。
在定义发明家的矛盾（inventor's paradox）(How To Solve It, Princeton University Press)时，George Póllya指出“计划越宏大，成功的可能性就越大。”现在，我们就来研究在分析Quicksort时的矛盾。到目前为止，我们遇到的问题是，“当Quicksort对大小为n的数组进行一次排序时，需要进行多少次比较？”我们现在将对这个问题进行扩展，“对于大小为n的随机数组来说，Quichsort算法平均需要进行多少次的比较？”我们通过对示例2-6进行扩展以引出示例2-7。
【示例2-7】 伪码：Quicksort的平均比较次数
float c(int n)
if (n <= 1) return 0
sum = 0
for (m = 1; m <= n; m++)
sum += n-1 + c(m-1) + c(n-m)
return sum/n
如果在输入的数组中最多只有一个元素，那么Quichsort将不会进行比较，如示例2-6
13
中所示。对于更大的n，这段代码将考虑每个划分值m（从第一个元素到最后一个，每个都是等可能的）并且确定在这个元素的位置上进行划分的运行开销。然后，这段代码将统计这些开销的总和（这样就递归地解决了一个大小为m-1的问题和一个大小为n-m的问题），然后将总和除以n得到平均值并返回这个结果。
如果我们能够计算这个数值，那么将使我们实验的功能更加强大。我们现在无需对一个n值运行多次来估计平均值，而只需一个简单的实验便可以得到真实的平均值。不幸的是，实现这个功能是要付出代价的：这个程序的运行时间正比于3n（如果是自行参考（self-referential）的，那么用本章中给出的技术来分析运行时间将是一个很有趣的练习）。
示例2-7中的代码需要一定的时间开销，因为它重复计算了中间结果。当在程序中出现这种情况时，我们通常会使用动态编程来存储中间结果，从而避免重复计算。因此，我们将定义一个表t[N+1]，其中在t[n]中存储c[n]，并且按照升序来计算它的值。我们将用N来表示n的最大值，也就是进行排序的数组的大小。在示例2-8中给出了修改后的代码。
【示例2-8】 在Quicksort中使用动态编程来计算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += n-1 + t[i-1] + t[n-i]
t[n] = sum/n
这个程序只对示例2-7进行了细微的修改，即用t[n]来替换c(n)。它的运行时间将正比于N2，并且所需的存储空间正比于N。这个程序的优点之一就是：在程序执行结束时，数组t中将包含数组中从元素0到元素N的真实平均值（而不是样本均值的估计）。我们可以对这些值进行分析，从而生成在Quichsort算法中统计比较次数的计算公式。
我们现在来对程序做进一步的简化。第一步就是把n-1移到循环的外面，如示例2-9所示。
【示例2-9】 在Quicksort中把代码移到循环外面来计算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += t[i-1] + t[n-i]
t[n] = n-1 + sum/n
现在将利用对称性来对循环做进一步的调整。例如，当n为4时，内部循环计算总和为：
t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]
在上面这些组对中，第一个元素增加而第二个元素减少。因此，我们可以把总和改写为：
2 * (t[0] + t[1] + t[2] + t[3])
我们可以利用这种对称性来得到示例2-10中的Quicksort。
【示例2-10】 在Quichsort中利用了对称性来计算
t[0] = 0
14
for (n = 1; n <= N; n++)
sum = 0
for (i = 0; i < n; i++)
sum += 2 * t[i]
t[n] = n-1 + sum/n
然而，在这段代码的运行时间中同样存在着浪费，因为它重复地计算了相同的总和。此时，我们不是把前面所有的元素加在一起，而是在循环外部初始化总和并且加上下一个元素，如示例2-11所示。
【示例2-11】 在Quicksort中删除了内部循环来计算
sum = 0; t[0] = 0
for (n = 1; n <= N; n++)
sum += 2*t[n-1]
t[n] = n-1 + sum/n
这个小程序确实很有用。程序的运行时间与N成正比，对于每个从1到N的整数，程序将生成一张Quicksort的估计运行时间表。
我们可以很容易地把示例2-11用表格来实现，其中的值可以立即用于进一步的分析。在2-1给出了最初的结果行。
表2-1 示例2-11中实现的表格输出
N Sum t[n]
0 0 0
1 0 0
2 0 1
3 2 2.667
4 7.333 4.833
5 17 7.4
6 31.8 10.3
7 52.4 13.486
8 79.371 16.921
这张表中的第一行数字是用代码中的三个常量来进行初始化的。下一行（输出的第三行）的数值是通过以下公式来计算的：
A3 = A2+1 B3 = B2 + 2*C2 C3 = A2-1 + B3/A3
把这些（相应的）公式记录下来就使得这张表格变得完整了。这张表格是“我曾经编写的最漂亮代码”的很好的证据，即使用少量的代码完成大量的工作。
但是，如果我们不需要所有的值，那么情况将会是什么样？如果我们更希望通过这种来方式分析一部分数值（例如，在20到232之间所有2的指数值）呢？虽然在示例2-11中构建了完整的表格t，但它只需要使用表格中的最新值。因此，我们可以用变量t的定长空间来替代table t[]的线性空间，如示例2-12所示。
【示例2-12】 Quicksoft 计算——最终版本
sum = 0; t = 0
15
for (n = 1; n <= N; n++)
sum += 2*t
t = n-1 + sum/n
然后，我们可以插入一行代码来测试n的适应性，并且在必要时输出这些结果。
这个程序是我们漫长学习旅途的终点。通过本章所采用的方式，我们可以证明Alan Perlis的经验是正确的：“简单性并不是在复杂性之前，而是在复杂性之后” ("Epigrams on Programming," Sigplan Notices, Vol. 17, Issue 9)。