哪一种C语言编写的程序运行速度最快

C语言只有一种，不过同一个C程序在不同的编译器中编译出来的结果是不一样的。速度我没做过比较，我想是和编译器的优化策略有关，选用“速度最优”的策略会比默认的"体积最小"要快吧。如果你需要加快程序的运行速度，把最占用时间的那些代码改用汇编来编写，另外可以考虑采用多线程，可以达到不错的效果。

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

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

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

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

当我撰写关于分治（divide-and-conquer）算法的论文时，我发现CAR 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有关，特别是对这个算法的性能分析。我将在下一节给出详细介绍。

22 事倍功半

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个元素进行排序时平均使用了14 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 += 2t[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 2667

4 7333 4833

5 17 74

6 318 103

7 524 13486

8 79371 16921

这张表中的第一行数字是用代码中的三个常量来进行初始化的。下一行（输出的第三行）的数值是通过以下公式来计算的：

A3 = A2+1 B3 = B2 + 2C2 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 += 2t

t = n-1 + sum/n

然后，我们可以插入一行代码来测试n的适应性，并且在必要时输出这些结果。

这个程序是我们漫长学习旅途的终点。通过本章所采用的方式，我们可以证明Alan Perlis的经验是正确的：“简单性并不是在复杂性之前，而是在复杂性之后” ("Epigrams on Programming," Sigplan Notices, Vol 17, Issue 9)。

分类: 电脑/网络 >> 程序设计 >> 其他编程语言

解析:

procedure sort(l,r:longint);

var i,j,x,y:longint;

begin

i:=l;

j:=r;

x:=b[(i+j) div 2];

repeat

while x>b[i] do inc(i);

while b[j]>x do dec(j);

if not (i>j) then

begin

y:=b[i];

b[i]:=b[j];

b[j]:=y;

inc(i);

dec(j);

end;

until i>j;

if i<r then sort(i,r);

if l<j then sort(l,j);

end;

这是我刚编的，这个过程是对于数组b进行快排。在主程序中sort(1,n）就可以排序了。

具体的思想嘛，我在网上找了一下，这个说得是对的：

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

假设要排序的数组是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+1N]，即在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]分别进行快速排序。

一：快速排序算法

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

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

算法步骤：

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

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

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

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

二：堆排序算法

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

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

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

十：朴素贝叶斯分类算法

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

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

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

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

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

假设要排序的数组是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；

详细过程举例如下：

原序： [26 5 37 1 61 11 59 15 48 19]

一： [19 5 15 1 11] 26 [59 61 48 37]

二： [11 5 15 1] 19 26 [59 61 48 37]

三： [1 5] 11 [15] 19 26 [59 61 48 37]

四： 1 5 11 [15] 19 26 [59 61 48 37]

五： 1 5 11 15 19 26 [59 61 48 37]

六： 1 5 11 15 19 26 [37 48] 59 [61]

七： 1 5 11 15 19 26 37 48 59 [61]

八： 1 5 11 15 19 26 37 48 59 61

快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：

var a:array[010] of integer；

n:integer;

procedure qsort(l,r:longint);{r，l表示集合的左右边界，即把第r到第l个数进行排序}

var i,j,m:longint;

begin

m:=a[l];{标准数}

i:=l; {I，J为指针}

j:=r;

repeat

while a[i]<m do inc(i);

while a[j]>m do dec(j);

if i<=j then begin

a[0]:=a[i];

a[i]:=a[j];

a[j]:=a[0];

inc(i);

dec(j);

end;

until i>j;

if l<j then qsort(l,j); {如果集合中不止一个数则进入下一层递归，l，J为新边界}

if i<rthen qsort(i,r); {如果集合中不止一个数则进入下一层递归，i，r为新边界}

end;

begin

for n:=1 to 10 do read(a[n]);

qsort(1,10);

for n:=1 to 10 do write(a[n]:4);

end

快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边。

然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述 *** 作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。

以下的代码中会常常使用交换数组中两个元素值的Swap方法，其代码如下

public static void Swap(int[] A, int i, int j){

int tmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

扩展资料：

快速排序算法 的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分 *** 作，直 到所有要进行排序的数据变为有序为止。

定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通 常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划 分序列的起始元素决定。

从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较 *** 作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较 *** 作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值 为 key。

参考资料:快速排序算法_百度百科

XScale体系结构是采用Intel Pentium技术实现的ARM兼容的嵌入式微处理器架构，并对ARM体系结构进行了增强，具有业界领先的高性能和低功耗特性被广泛应用于消费电子、无线通信、多媒体和网络交换等嵌入式应用领域。XScale引入了一系列高性能微处理器的设计技术，总体性能显著地超出同主频的ARM微处理器。然而，由于受功耗、成本和体积等因素的制约，嵌入式微处理器的处理能力与桌面系统相比仍存在较大差距。通常需要对嵌入式应用程序进行性能优化，以满足嵌入式应用的性能需求。

业界对嵌入式系统的性能优化进行了很多研究与实践。文献为XScale优化编译器的设计提供了多种优化技术，也可用于一些应用程序的手工优化；文献从应用程序编程的角度讨论了ARM嵌入式系统软件设计优化技术；文献讨论了提高C/C++嵌入式应用程序性能的一些技巧，其中多数技术可以由优化编译器中实现。

本文在总结XScale优化编译器设计和XScale嵌入式系统设计开发工作的基础上，从系统设计、开发工具选择、编译优化和编程开发等角度讨论和提出了XScale应用程序的优化策略和技术。

1 XScale体系结构

XScale微架构引入了Pentium处理器工艺和系统结构技术，实现了Pentium微处理器体系结构的一系列高性能技术，达到了高性能、低功耗和小体积等嵌入式系统要求的特性。

（1）超流水线

Xscale的超流水线（SuperPipeline）技术，如图1所示，由整数处理（integer）、乘加（MAC）和存储（memory）3条流水线组成。3条流水线的长度是6到9段，前4到5段共享，后面分支部分并行工作可有效提高处理器性能。

（2）高主频

采用Pentium工艺技术，XScale主频可以超出普通ARM微处理器主频数倍，在保持较低能量消耗的前提下，高达600MHz以上。如PXA27X的主频可高达724MHz。

（3）存储体系

XScale实现了一个高效的存储器体系结构，为其超流水线的高效运行提供数据资源。XScale存储体系功能主要包括32KB D-Cache、32KB I-Cache、2KB Mini Dcache、Fill Buffers、ending Buffers以及48GB/s带宽的存储总线，使处理器可以高效访问存储器。

（4）分支预测

XScale实现了基于统计分析的分支预测功能部件，减少由于分支转移冲刷指令流水线的次数，也有效地提高了处理器的性能。

（3）指令集体系结构

针对ARM数据处理能力的不足，XScale对ARM的乘加逻辑进行了增强，增加了8条DSP指令。XScale处理器还可集成Flash闪存和无线MMX逻辑功能。这些特性有效地提高了XScale数据处理能力。带有无线MMX的PXA27X在312MHz主频运行处理多媒体应用时，其性能与520MHz ARM处理器相当。

（6）省去不常用的逻辑功能

为了节省处理器芯片体积和降低运行功耗，XScale体系结构没有实现昂贵的浮点运算部件和除法部件。这些是嵌入式应用中不常用的运算。当需要这类运算时，可以通过软件方法实现。

XScale复杂的体系结构给嵌入式应用程序的优化带来了更大的困难。

2 性能优化技术

XScale处理器性能的发挥很大程度上依赖于应用程序的优化技术。XScale嵌入式应用系统的性能优化可以下几个方面考虑。

21 算法结构优化

实现某种应用功能通常可采用多种算法或方法，不同算法的复杂度和效率差别很大。选择一种高效的算法或对算法进行优化，可以使应用程序获得最大的优化性能。常用的优化技术有以下几种。

（1）选择高效算法

如果算法效率低下，再快的处理器也会显得不够有，而一个高效的算法却可以弥补处理器性能的不足。

考虑从已排序好的n个元素a[0:n-1]中找出某一特定元素x。如果采用顺序搜索方式，从a[0]到a[n-1]逐个比较这n个元素，需要O(n)次比较。而如果采用二分搜索方法，则仅需O（logn）次比较。当n为2 31时，前一算法平均需要比较2 31次，后一算法平均仅需比较31次。两者所需时间相差达10 8倍。

（2）递归算法非递归化

采用递归过程实现算法具有结构清晰、程序简练易读、正确性容易证明的特点；但递归算法通常需要执行大量的过程调用，并在堆栈中保存所有返回过程的局部变量，效率往往较低。当应用程序存在性能问题时，使用循不迭代方法将递归算法转换成非递归算法往往可以使程序性能提高数倍。文献对八皇后问题和Fibonacci数列的递归算法与非递归算法进行了性能比较试验，结果如表1所列。

表1 递归算法和非递归算法的性能对比

问题 递归算法时间/s 非递归算法时间/s 加速比/倍

八皇后问题（最大栈深度为12） 100 20 5

Fibonacci数列（n=40） 50 1 50

算法优化是首选的优化技术。

22 编译优化

随着编译技术的成熟，很多编译器都实现了较强的代码优化功能，可在编译过程中自动对应用程序进行优化，改进一些不合理的结构，生成效率较高的目标代码。

多数编译器都可基于数据流分析实现别名分析、常数拆叠、常数传播、公共子表达式消除、冗余代码和死码删除、循环不变量的移动、循环逆转、循环展开、函数嵌入等与体系结构无关的优化。

GNU gcc、WindRiverdiab、Intl XScale Compiler等常见编译器都针对XScale体系结构进行了优化设计，可以有效地利用XScale/ARM指令的条件执行、条件设置和 *** 作数移位等功能，使一条指令完成多个 *** 作，缩短指令序列的长度；减少跳转指令的数目，减少冲刷流水线的次数；按照XScale超流水线要求，利用3地址指令、多字传送指令、DSP乘加指令和MMX指令等，生成高效的指令序列，提高应用程序的性能。

一些优化编译器可借用并行程序设计技术，进行相关性分析，获得源程序的语义信息，采用软件流水线、数据规划、循环重构等技术，使应用程序呈现更好的局部性，提高Cache命中率，从而提高计算密集型应用程序的性能。对于矩阵计算等计算密集型程序，一些高性能优化编译器生成的代码可以高出普通编译器产生的代码十倍之多。

应用程序开发过程中应该充分利用编译器的代码优化功能，在编码时将主要精力集中在业务逻辑算法流程的设计上，提高编程效率和代码可读性。

23 编程优化

编译优化是静态优化。优化编译器可以自动完成程序段和代码块范围内的优化问题，但编译器很难获取程序语义信息、算法流程和程序运行状态信息。很多情况下也需要编译人员以某种方式将程序运行状态信息传递给编译器，或进行手工优化。以下是常用的编译优化技术。

（1）使用inline函数

多数编译器支持inline关键字。如果一个函数被设计成一个inline函数，那么在调用它们的地方将会用函数体来替代函数调用语句，这样将会彻底省去函数调用的开销。使用inline的最大缺点是函数在被多处调用时，代码量将增大。

（2）减少函数调用参数

根据ARM过程调用规范，4个以下的形参通过寄存器传递，第5个以上的形参通过存储器栈传递。显然，通过存储器栈传送参数的开销较大。函数调用形参限制在4个以内，可以降低函数调用的开销。

（3）在Switch是一种使用普通的编程技术。编译器为之产生if-else-if嵌套代码，并按照顺序进行比较，发现匹配则跳到满足条件的语句执行。编程时，根据发生的相对频率排序，将最可能发生的情况放在第一位，最不可能的情况放在最后一位，可以提高Switch语句块的执行速度。

实际上，程序中if条件的处理也有类似的特性。

（4）避免使用C++的昂贵功耗

C++在支持软件工程、面向对象程序设计、结构化对C进行卓有成效的改进，但在代码尺寸、执行速度等方面比C语言差一些。C++的类机制与C语言的结构差别不大，但C++的多重继承、虚拟基类、模板和运行类型识别等特性对代码尺寸和运行效率有负面影响。对这些功能要慎重使用，可以通过试验测试其影响的大小。

（5）减少或避免执行耗时的 *** 作

应用程序的主要执行时间通常花费在关键路径代码段或程序模块，关键路径程序模块往往包含循环或嵌套循环。减少循环或内层循环中昂贵 *** 作的执行频率可以显著地提高应用程序的效率。常见的耗时 *** 作有：I/O *** 作、文件访问、图形界面 *** 作和系统调用等。

表2列出了XScale常见的I/O处理、系统调用和文件访问等昂贵 *** 作的代价。

（2）避免浮点运算

XScale没有实现浮点部件。浮点运算是通过系统库实现的，代价很高，通常也应该避免，有时可以转换成整数运算。包含浮点运算的库例程有格式化输入输出（scanf/printf）等。XScale中常见浮点运算的代价如表3所列。

表3 XScale常见浮点运算的代价

运算类型 代价（时钟周期/个）

加法+ 400

乘法 400

除法/ 500

我 不知道这个能不能帮你`1你自己可以看看<参考资料>

C++程序，求任意整数的二进制倒序:

#include <iostream>

//#include<cmath>

#include <cstdlib>

using namespace std;

void dispBin(int n)

{

if(n==0)

{

//cout << 0;

return;

}

cout << (n & 0x1);

dispBin(n >> 1);

//cout << (n & 1);

}

int main()

{

int n;

cout << "输入一个整数：";

cin >> n;

if(n==0)cout << "0";

else cout << "二进制数倒序为：";

dispBin(n);

// puts(" ");

cout << endl;

system("pause");

return 0;

}

以上就是关于哪一种C语言编写的程序运行速度最快全部的内容，包括:哪一种C语言编写的程序运行速度最快、冒泡排序法和快速排序比较的算法、快速排序的PASCAL程序是什么啊最好有思想等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！