打你屁股，这么简单的问题都不认真研究一下。
冒泡排序是最慢的排序，时间复杂度是 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)。
学术论文格式要求
1 版式
纸张大小：纸的尺寸为标准 A4 复印纸（210mm×297mm） 页边距：上 2.54cm，下 2.54cm，左 3.17cm，右 3.17cm，页眉 2cm，页脚 2cm
2 论文撰写必须包括以下项目： 论文撰写必须包括以下项目：
2.1 文章题目 文章题目（一般不超过 20 字）
范例： 范例：
格式要求：三号字，黑体加粗，居中，段前 1 行，段后 1 行，行距为固定值 20 磅
快速排序算法的性能分析
2.2 中文摘要、关键词（3~5 个） 中文摘要、关键词（ （1）摘要按照目的、方法、结果、结论四要素来撰写。摘要是以提供论文内容梗概为 目的，简明、确切地记述论文重要内容，摘要不分段，字数以 100~200 字为宜。 （2）关键词的选择应规范。 范例： 范例： 五号字，黑体加粗 格式要求：五号字，汉字楷体-GB2312，外文、数字用 Time New Roman 体，段前 1 行，行距为 17 磅，两端对 齐
摘要： 它是否适应中国的实际是一个值得研 摘要 持有收入假说是弗里德曼提出的著名假说， 究的问题。本文从持久收入计算方法的探讨入手，分析了估算方法的科学性、合理性。以此 为基础，通过协整分析验证了消费与持久收入之间的长期均衡和短期动态关系。实证结果表 明，持久收入是影响中国农民消费的重要因素。 关键词：持久收入；协整分析；误差修正模型 关键词 格式要求：五号字，汉字楷体 -GB2312，外文、数字用 Time New Roman 体，行距为 17 磅，分号隔开
2.3 英文题目、摘要、关键词（3~5 个）等 英文题目、摘要、关键词（ 题目 英文题目、作者等内容应跟中文题目、作者等相对应。
范例： 范例：
格式要求： 号字， 16 Times New Roman， 加粗， 居中，段前 0.5 行，段后 1 行，如果两行标题 行距为 18 磅
A Cointegration Analysis On Chinese Rural Inhabitant
Lasting Income And Consumption
Abstract: The lasting income hypothesis is the famous hypothesis Friedman proposed, whether it does adapt China is the question actually which is worth studying. This article obtaining from the lasting income computational method discussion, has analyzed the estimate method scientific nature, the rationality. Taking this asthe foundation, through Cointegration analysis toconfirm between the consumption and lasting income long - term equilibrium and the short - term dynamic
relations. ……
格式要求：12 号字，Times New Roman，段前 0.5 行， 左缩进 2 字符，两端对齐，行距 17 磅。
格式要求：12 号字，Time New Roman 字体，段前段后各 0.5 行， 行距 17 磅。
Key Words: lasting income; Cointegration analysis; ……
2.4 正文、结语 正文、（1）汉字字体字号选小四号宋体，外文、数字字号与同行汉字字号相同，字体用 Time New Roman 体。 （2）正文中的图、表按出现的先后顺序进行编号，图务必清晰、精确，图名、表名必 须有中文表述，坐标图的横、纵坐标必须标明其对应的量及单位。 （3）文中的公式包括数学、物理和化学，采用 WORD 中的公式编辑器编辑。 （4）标题分级见下例中所示，此分级编号只分至第四级，分别是一，1， ，① （1）
范例： 范例：
格式要求： 一级标题， 小三号字， 汉字黑体加粗， 外文、 数字用 Time New Roman 体， 段前 0.5 行， 段后 0.5 行，行距为固定值 20 磅，左对齐
一、引言 引言 随着我国公路建设事业迅速发展，道路通车里程的迅速增加，道路的养护、 改造任务也越来越重，以往对破旧沥青路面的改造方法是:挖除、外运然后再重 新铺筑新路面，这样既浪费沥青资源也不利于环保。…… 二、原材料性质
1． 添加剂 ． 格式要求：正文小四号字，汉字宋体， 外文、数字用 Time New Roman 体，行 距为固定值 20 磅，两端对齐 格式要求：二级标题，四号字，汉字黑体 加粗，外文、数字用 Time New Roman 体， 段前 0.5 行，行距为固定值 20 磅
试验拟定水泥、二灰、水泥粉煤灰 3 种添加剂。 （1）添加剂的分类
…… ①……
表例： 表例： 表 1 车辙试验
混合料类型 1 铣刨料 铣刨料+新料 7875 2625 2 7000 2864 3 6980 3100
格式要求：五号字，汉字宋体，外文、 数字用 Time New Roman 体，行距为固 定值 20 磅，居中
动稳定度/（次·mm-1） 平均 7285 >800 2863 要求
格式要求：简明型 1 表格，五号字，汉字宋 体，外文、数字用 Time New Roman 体，行 距为固定值 20 磅，居中对齐
图例： 图例：
30
y=-1.0844+0.2615x
25
上面层变形量(mm)
R2=0.7567
20 15 10 5 0 0 10 20 30 40 50 60 70
总车辙深度 (mm)
图 4 总车辙深度与上面层变形的关系图
公式例： 公式例：
Qbe = Vbe ⋅ Gb G VMA − V = ⋅ b （%） Gmw 1 −0.01VMA Gsb
（1）
参考文献 （1）参考文献应不少于 5 个，采用顺序号编号体系，并注意尽量以近期文献为主。书 写要全面、规范、准确。 （2）参考文献的编排格式为： 如果是书： 作者名： 《书名》[M]，出版社，2004 年版，第 23 页 [4]傅丰林： 《数据库的发展》[M]，天津科学技术出版社， 2003 年第 2 版，第 2 页、6 页、 77 页 如果是期刊： 作者名： 《文章名》[J]， 《期刊名》 ，2005 年第 3 期，第 45 页 [3]王永信、王益进、萧阳： 《冒泡排序算法的改进》[J]， 《电脑学习》 2005 年第 4 期，第 ， 44 页—46 页
（3）专著（M） 、论文集（C） 、报纸文章（N） 、期刊文章（J） 、学位论文（D） 、报告（R） 、 标准（S）专刊（P）、未定义类型的文件（Z） 范例： 范例： 参考文献： 格式要求：五号字，汉字黑体，行距为 17 磅，左对齐
[1] 傅丰林： 《数据库的发展》[M]，天津科学技术出版社， 2003 年第 2 版，第 2 页、6 页、 77 页 [2] 王永信、王益进、萧阳： 《冒泡排序算法的改进》[J]， 《电脑学习》 2005 年第 4 期，第 ， 44 页—46 页
格式要求：五号字，汉字宋体，外文、 数字用 Time New Roman 体，行距为 17 磅，两端对齐
你百度一下会有很多的。
总括来说，世界上语言可分为两大类。一类是目前已经没有人使用的，已不通行的，或已被废弃了的，称为“死”语言（dead language）；另一类是目前仍然通行的称为“活”语言(living language)。希伯莱语、古拉丁语等属于前者；而汉、英、日、西、法、德、俄等语言俱属于后者，而且是其中最通行的几种。
“活”的语言有一个很重要的共通点，就是它们都随着时代的发展而变化。英语上这样，其他的语言也是如此。不过，由于英语在世界上的通行度和通行范围都胜于其他各种语言，所以其变化尤烈。
英语的变化主要表现于语法和词汇两方面，并籍这两种变化推动发展，构成现代英语的基础。近二十年来语言学理论最重大的进展之一是出现了“转换——生成语法”（Transformational-generative Grammar),这种语言学理论的诞生使英语进一步科学化。与此同时，大量新词汇的涌现使英语的表达力加强了，形式丰富了，因而使英语更趋生活化。
新词汇的产生
新词汇到底是怎样产生的？
当人们发现新事物，遇到新问题，总结了新经验，发展了新思想的时候，便需要新字和新词来表达，这是因为旧有的、沿袭使用的表达方法已经不适合或不敷应用了。另一方面，由于以英语作母语及第二语言的国家遍及全球各洲，而各地的风 土人情、生活习惯和社会环境大有区别，这就必然会出现不同的表达形式和用语，而这些语汇中不少会被逐渐吸收进经典的英语辞典中，成为语言的一部分。
在目前日益进步的社会里，科学和技术是新词汇的主要供应者，每当某一门科学发展到一个新阶段的时候，就有相当大一批新词涌现。在这些新词当中，很多是该等科学的专用词汇，鲜为外行人所知晓，只有专科字典及词典才有收栽；但是，其中也有不少常被应用和引用，结果成了一般人所喜闻乐道的用语。
例如，当美国太空人成功地登陆用于月球时，英语中出现了moonwalk（月球漫步），lunar rove(月球车)，moonrock（月球标本车）等一系列有关的用词。由于近年发射了不少人造卫星绕月运行，故此就很必要地创出了apolune(远月点)和perilune(近月点)二词。太空船与太空站在空间会合对接，使docking增添了一个新含义（靠泊），同义的还有linkup。发射太空船被视为人类科学发展的象征，故很受注意。因此，不少与太空船有关的用词已被广泛使用，如CM(command module:指令舱，指挥舱），splashdown （溅落），space sickness（宇航病），space age (太空时代）等。在谈到探索deep space(深空间，远空间）和其他太空现象时，quasar（类星射电源），pulsar（脉冲星），neutron srar （中子星）及神秘的black hole （太空黑洞）等已是耳熟能详的用语。
近二十年来，遗传学的迅速发展创造了许多使人耳目一新的词汇，如genetic code（遗传密码），codon（密码子），DNA（脱氧核糖核酸），transfa RNA（传输核糖核酸），messenger RNA（信使核糖核酸），transcription（信使核糖核酸的形成）等。这些新词流行日广，连到一般的书刊报道都有应用，故此早已广大读者所接受。
近年来发展迅猛的大了电脑工业带来的新词汇也着实不少。常听常用的包括FORTRAM（公式翻译程序语言），COBOL（面向商业的通用语言），ALGOL（算法语言），BASIC（初学者的通用符号指令码），absolute address（绝对地址），data bank（资料库，数据库），floppy dise（柔性塑料磁盘）pushdown（下推存储器）等等。旧有词如keyboard,terminal,memorym bit等也分别加添了新用法。
医学的飞跃发展同样带来了大批新词，包括了医学上的技术性用语及新制成的药品名称，新发现的病菌、病毒等。其中如hotoscanning（光扫描），open heart surgery(开心手术)，picornabirus(换心人)，microcirculation（微血管循环）等都是近期出现的。一些用词如the pill（口服避孕丸），test-tube baby（试管婴儿），transsexual operation（变性生术）等已成日常用语。
核物理学发展的结果，好象要把人们带进微观世界。kron（K介子），muon（μ介子），pion(π介子)等陆续发现，lepton（轻子），baryon(重子)的分别，当然还有引起轰动的quark(夸克)。假设上由各种antimatter(反物质)如antiproton(反质子),antineutrino(反中微子),antiquark(反夸克)等组成的antiworld(反物质世界)也备受重视。
数学和其他学科也在不停地发展。在通俗的教研、科普读物中,不难发现以下的名词术语:NOT("非"逻辑算子),parametric equation(变数方程),近年中小学推行的newmath(新数),artificial intelligence(人工智能),magmetocardiogram(磁性心动扫描记图)，IC (集成电路)，piscicide (鱼类灭绝)，hot mooner (热月学家),Sealab(海底实验室)，radiosterilization（放射性消毒）等。新的学科也在不断形成，例如bionics（仿生学），cryosurgery（冷冻手术），macrometereology（大气象学），ocean engineering（海洋工程学），phytochemistry（植物化学），biotelemetry（生物遥测学），astrionics（太空电子学）等数十种新的学科在发展和壮大。
军备竞争激烈，武器日新月异，自然也产生了不少新词汇。ABM(antiballistic missile:反弹道导弹),MIRV(multiple independently-targetedreentry vehicle:多弹头分导重返大气层运载工具),the Bomb(核威慑),helilift(使用直升机运输),Green Berets("绿色贝雷帽"特种部队),grunt(步兵,beam weapons(死光武器)等,几乎成了家喻户晓的用语。
交通工具的改进,也使人有瞠目结舌之感。天空上充斥着SST(supersonic transport:超音速运输机)，airbus（空中巴士），air-taxi（空中的士）；英法合制的Concorde（协调式飞机）在航空史上当然也占着重要地位。HST（hyper-sonic transport：特超音速飞机）的诞生，使飞机工业有了新发展。一些富裕的有闲人士经常乘搭喷气式飞机到各地旅游集会，成了一个特殊的阶层，称为jetset。喷气式飞机的乘客有时也会患上这样或那样的不适症状，统称为jetsyndrome。在水面和陆地上，新型的交通工具接连出现，包括ACV （air-cushion vehicle：气垫式运载工具），ATV（all-terrain vehicle:全地形车），hovercraft（气垫船），freight-liner（货柜火车），bullet train（子弹车），aerotrain（悬浮火车）等。
除了科学和技术之外，动荡的政局、日趋变革的社会环境和世界性的文化及各方面的交流，也是英文新字的来源。例如自六十年代初期“－in 运动”的兴起、转化和发展，使这个“家族”膨胀得使人吃惊。从第一代的sit-in（静坐示威）到第二代的teach-in （宣讲会），以至第三代的be-in（颓废派的社交集会），一共出现了数十个－in的用词，其演变之速，实令人咋舌。
近年来，世界政坛风云变幻。西欧诸国为加强团结，发展贸易，组织了EEC（European Economic Community:欧洲经济共同体）。中东和南美、非洲的石油输出国也组织了OPEC(Organization of Petroleum Exporting Countries:石油输出国组织）。在美国爆发了水门事件之后，Watergate一字被广泛应用以指任何的政治丑闻在政府内部，主张用武力解决争端的一派人被称为hawk（鹰派），主张和平手段的称为dove（鸽派)，而dawk是介乎鹰派),主张和平手段的称为dove(鸽派),而dawk是介乎鹰派与鸽派的消极反战者。其他的政治用词如establishment(政府),atomic club(原子俱乐部),advance man(先行人员,助选人员),pilitical animal(政治动物)等亦常见用于报刊之上。
世界性的经济危机,通货膨胀和工商业的发展也是新词的重要来源之一。ASP(American Selling Price美国售价),slumpflation(萧条膨胀),added-value tax(增值税),Eurodollar(欧洲美元),petrodollar(石油美元),revenue sharing(国库分享)等都是近期产物。
社会的变革在过去两个年代中造成了很大的影响,不少基本意识形态受到了冲击。女权运动的爆发产生了像Women'sLib(妇解运动),chairperson(主席),malechauvinist(大男子主义者),girlcott(抵制)等新用词,但也促成了Men's Lib(男子解放运动)的诞生。六十年代末期美国黑人运动Black Power(黑色权力)爆发后,不少表示"…运动"的用语即仿此而出现,计有:Brown Power(褐色权力),Flower Power(花癫派权力),student power(学生权力),Red Power(红色权力)等,更有人戏谑地创出green power一语，意指“金钱魔力”（因美元背面是绿色的）。
道德观念的转变造成了generation gap(代沟),而gap字的用途又在此基础上多样化,以致产生了credibility gap(信誉沟),culture gap(文化沟),communication gap(通信隔阂)等新词。西方青年的思想与旧习俗社会的脱离,迫使他们要寻找发泄的途径。于是Mary Jane(大麻),LSD(迷幻药),upper(兴奋剂),soft drug(软毒品),hard drug(硬毒品),headshop(迷幻商店),commune(嬉皮士公社),psychedelphia(迷幻村)等词又应运而生。一代一代的颓废派亦相继出现:hippie(嬉皮士),flower children(花癫派),Gentle People(温和人),street people(街头颓废派),teenybopper(少年颓废派),等等。
人们对环境污染的注视在近年特别显著,这可见诸环境学家的倡议设立EarthDay(地球清洁日)和Eargh Week(地球清洁周)。"污染"这一用词无日不见出现于报章杂志之中,较新的词汇包括environmental pollution(环境污染) ,heat/thermal pollution(热污染), internal pollution(体内污染),visual pollution(视觉污染),antipollutionist(反污染者),environmentalist(环境问题专家),dystrophication(河湖污染)等。
在教育和语言研究方面,也因教学方法和教学用具的改革而出现了一系列的新词,如schoolbook(教科书式的),pass-fail(取否法),CAI(computer-assisted instruction(电脑辅助教学),audiovisuals(视听教材),coedism(男女同校教育),preppie(预科学生),open classroom(开放教室),polyversity(多元大学),megaversity(超级大学),generative grammar(生成语法),kernel sentencd(核心句)和Chomskian(乔姆斯基理论的)等。
娱乐和体育亦是较大的新词汇供应者。电台和电视台的audience rating(视听率),call-in(电话节目),sitcom(长寿单元喜剧),soup opera(肥皂剧),prime time(黄金时间),imstant replay(即时重播),VTR(磁带录像),VCR(盒式录像)等都是人所共知的用语了。多姿多采的新体育运动也丰富了英语的词汇。近期新兴的玩意包括skate-boarding(滑板运动),skydive(缓张伞跳伞)。land/sand yacht(沙滩艇,陆地风帆),hang glider(飞行风筝)是较高级的玩物。一些组合词如cyclo -cross(自行车越野赛),roller hockey(滚轴冰球),demolition derby(撞车大赛)等也因新型运动的兴起而相继出现。体育家们还发明了slimnastics(减肥体操),isometrics(静力锻练)等健美身体、增强力量的方法,当然还有流行海外的中国kung fu(功夫)和日本的aikido(合气道)等。
很多的新词汇实际上已经进入人们的日常生活和每个家庭之中。现在,很多家庭里都有VCD(盒式录像机);而原来称为television set的电视机现被谑称为television set 的电视机现被谑称作box, gogglebox, idiot box, idiot'slantern。microwave oven(微波电锔炉),autotimer(自动开关器)等是科技的新产物。videophone/picturephone(电视电话)亦在大量生产中。音响领域中的新词也有quadraphony(四声道),sensurrornd(杜比系统)等。七十年代最后一年才出产的Polarvision System(宝丽视系统)现已流行世界。较早期出现的telex(用户电报)更是大公司和商行必设的通讯系统,当然还有IDDD(International DirectDistance Dialling:国际直通长途电话)。过去几年生产了一种拉盖即开的罐装饮品,这种引起浪费和制造废品的用完即丢的容器也有新名称:thrwaway 或diposable 。
为了加强表达的力量，不少新的日用词汇被创造出来了。这一类的用词近年来大行其道,若不弄懂实难秘英、美、人士交谈。举例而言，精神病医院的新名称是funny farm,而fat farm却是减肥中心;在停车场向违例停泊的车辆派告票的女警察被称为meter maid(老虎机女郎),用油特多的"大食车"是gas eater。容易到手、尤其是以不正当手段得来的金钱叫做quick buck等等。
事实上,新词汇产生的原因及其来源非常广泛,可以说是由世界上各式各样的变化促成的,故此无法尽量罗列。总而言之,大量新词的涌现说明了社会在变化,英语在变化。
新词汇的构成
根据研究和统计的结果，在六十年代和七十年代中，共出现了一万多新的英文词汇。然而，这个数目所包括的仅是已经确立并被广泛使用的字和词，一些被大多数人接纳、太专门化或罕用的词语尚不算在内。按这一万多的新词汇所做的研究，其构成法可以分为四大类。
<1>创新法—— 即创造出一个全新的英文字。据研究结果显示，用这一种方法创出的新字新词所占比例较小，因为到目前为止，英语已经有了相当雄厚而根基巩固的“班底”，新词汇可由旧字和原有的词根变化出来。用创新法构成的新词汇包括。
(a)少量的社会科学及自然科学用词,如:periapsis(近拱点),cladistics(遗传分类学),penetralium(核心组织),ekistics(城市与区域计划学),isomorphism(同构),quark(夸克);
(b)已通用的新产品的商标名(代表或用来指同一类产品)和已被用作普通名词的专有名称,如:lasercomp(激光电脑排版机),dolby system(杜比系统),miniteller(微型出纳机),Rent-a-Train出租列车).polarvision system(宝丽视系统——即影即有电影系统),sealab(海底实验室),watergate(政治丑闻),Frisbee(玩具飞碟);
(c)人名和地名等专有名词衍变出的普通词类,如:Hitchcockian(希治阁式的,悬疑的),Chandler wobble(钱德勒振荡),cocacolonization(美国化),a-go-go(阿哥哥舞厅),Mcluhanesque(麦克卢汉式的,电子化的);
(d)经常被使用的字首缩略词(acronym)和普通的缩写语(abbtreviation),如:STLT(Strategic Arms Limitation Talks:限制战略武器会谈),COBOL(Coommon business Oriented Language:面向商业的通用语言),BADGE(Base Air Defense Ground Environment:地域半自动防空警备体系),ACV(air-cushion vehicle:气垫式运载工具),EEC(European Economic Community:欧洲经济共同体,欧洲共同市场),comsat(communication satellite:通讯卫星);
(e)新的习语,包括以前未被收入正式词典中的俚语(slang)和口语(colloquialism),如:posh(非常时髦的),bonkers(疯狂的),easy meat(易辨的事),like a lead balloon(毫无作用),can of worms(一团糟),merchant of death(死亡贩子),go for broke(尽最大努力),carry the can(面对责备,负起责任),selllike T shirts(货如轮转)。
用这一种方法创成的新字新词中,还包括了一种把长字缩短而保持原义的新形式,如deli(delicatessen:熟食店),mod(modern:时髦的,摩登的),nat(mationalist:民族主义者),neut(neutron bomb:中子弹),divi(dividend:红利),disco (discotheque:迪斯科,唱片夜总会)等。这种新形式与原字同样流行,有睦甚而超过。
一部分商标名被接纳为普通用词后,用法、含意和词类属性上亦起了变化。如telex原为名词(用户电报,电报用户直通电路),现可作动词用,表示"以用户电报通知";xerox原为名词(乾式影印,静电影印),现可作动词;STP原为汽油附加剂,现指幻觉剂;Tom it一词中,表示"逆来顺受"。
<2>结合法——在旧有用词的基础上,加上前缀、后缀或其他构词成分构成新词,或使两个旧有用词或旧有用词的部分结合起来成为新词,或使两个构词成分结合成新词。利用这种方法构成的新词汇所占比例较大,词义亦较易理解推出。例如:microelectronics(micro+electronies:微电子学),antididnapping(anti +kidnapping:防绑架的),autocue(auto+cue:自动提示器),electrofishing (electro+fishing:电力捕鱼),photobotany(photo+botany:光植物学),educationese(education+ese:教育界术语),Pekingology(Peking+o+logy:北京学,北京问题研究),Dullesian(Dulles+ian:杜勒斯式的),robotesque(robot+esque:机械人似的);
Housrmanship(house+manship:英议员的雄辩),Americandom(American+dom:：美国人的世界),cryptosecurity(crypto+security:秘密安全部的),paint-in(paint+in:油漆示威),pedestrianization(pedestrian+ization:人行道化),peacenik(peace+nik:反战运动分子);
diet pill(减肥丸),easy meat(易辨的事;易得的东西),Great Society(大社会),hard science(硬科学,自然科学),landmark(陆标),cardcarrying(典型的),carbecue(烤车架),boatel(汽艇旅馆),chunnel(水底列车隧道);
electrophobia(electro+phobia:电气恐怖症),bionics(bio+onics:仿生学),quarkonics(quark+onics:夸克学)。
有一部分前缀、后缀及构词成分是特别多产或特别活跃的,其中包括anti-,auto,bio,electro-,Euro-,extra-,geo-,hyper-,-ian,immuno-,in-,-in,inter-,intra-,-logy,macro-,micro-,mini-,multi-,-nik,non-,prar-,-phobia-,photo-,poly-,psycho-等,此等构词成分在构成新词的过程中起着相当积极的作用.
<3>添义法---使旧词添上新释义.近年来,不少沿用的旧词增添了新的含义.这一类形旧义新的字为数不少,碰上和使用时宜加注意,例如:
Happening:旧用法指一次事件,新用法指“哈普宁艺术”（一种目的使观众意外、惊奇和投入的舞台或其它形式的演出等。
这一部分的新词还包括了一些过去只能作为某一种词类使用，现在却可作别一词类运用的旧字。如H-bomb过去是名词（氢弹），现在可作动词，表示“用氢弹袭击”；lookingglass过去是名词，指“镜子”，现在可作形容词用，表示“颠倒的”，“乱七八糟的”等意。又如soul一字既加添了新意，指“黑人文化”，更可作形容词，泛指“黑人的”，如soul music（黑人音乐，灵乐），soul food（黑人食物）等。
一个值得注意的构词形式是back-formation，即所谓“逆序造词”或“倒反构词”。这是把一个现存的词的真正后缀或貌似后缀的部分脱落而形成该词的另一种词类。例如先有 free association（自由发言，自由联想），才有freeassociate;one-up（胜人一筹的，占上风的）和 one-upman胜...一筹，占...的上风）是从one-upmanship 一词倒反构成的。laser（激光）本是一字首缩略词，但是由于像是从lase变出来的名词，故英、美人士又创出lase这个动词，表示“放射激光”，“使受激光照射”。
<4>外借法---借用或吸收外来语。这种方法由来已久，英语中不少字和词其实是从外国借来使用，最后成了英语中不可缺少的部分。这些外来语很多保留原来的样貌，有些拉丁化拼音拼写成英语，亦有些被改头换面或按义译成英语的。例如：
discothèque <法>:唱片夜总会
autostrada <意>:高速公路
autopista <西>:高速公路
mao tai <中>:茅台酒
sushi <日>:寿司
westpolitik <德>:(东欧国家的)西方政策
samizdat <俄>:地下出版(物)
favela <葡>:贫民窟,木屋区
haman <阿拉伯语>:海玛姆(伊朗公众浴堂)
又如black humor (黑幽默)原为法语humour noir,英美人士借用后按义改成正式英语;同样地,found object (拾得艺术品)来自法语objet trouve。kirin来自日语kylin，后者又源于汉语ch’i lin（麒麟的旧拼写法）。
（本文是作者为《10000英文新字字典》写的导言）
冒泡排序，在每一次比较的时候，如果发现相邻两数的次序不对，都会马上就把两数进行对调。
选择排序，则在比较过程中（内循环里面）并不进行对调，而是先记录下最小（大）数的下标，在一次扫描完成后再进行对调。所以它的效率会比冒泡的高一点。
但是冒泡排序是“稳定的”排序。就是说同样总分的若干名同学，排序前在前面的，排序后这些同学的相互位置不会发生改变。
而选择排序则是“不稳定的”排序。就是说同样总分的若干名同学，排序前原来相对排在前面的，排序后有可能会变到后面。
