题记：本文是对《Beautiful Code》一书的读书笔记与原创翻译，首发于慕课网。此书由Greg Wilson和Andy Oram共同撰写，由O'Reilly Media, Inc.于2007年出版。
何为最漂亮的代码？很多人对此表示好奇，而这本独特的书籍《Beautiful Code》正是探讨这个问题的最佳选择。作者在这本书中阐述了他们对于漂亮代码的理解和认识。漂亮的代码，它的存在犹如一种美感，其本质是简洁美与优雅美。
这些代码追求极致的改进，通过删除冗余部分来增强功能。它们就像艺术品一样，多一点则多余，少一点则欠缺。在不断地打磨与修正中，逐渐趋于完美。在计算机领域，没有所谓最便宜、最快、最可靠的组件。真正优秀的代码应当追求事半功倍，力求简单至极。在简单中找寻真正的美。
让我们一同欣赏书中第三章的一些精彩片段。
我曾听闻一位高级程序员赞叹：“他通过删除代码来增加功能。”法国作家兼飞行员安东尼·德·圣埃克苏佩里（Antoine de Saint-Exupery）也曾表达过类似的观点：“设计师们明白，只有在没有什么可以添加或删除的时候，他们才认为这项工作已经完美。”在软件领域，最漂亮的代码、最漂亮的函数和最漂亮的程序往往难以言表，有时甚至并不存在。
当Greg Wilson初次提及这本书的概念时，我反思了自己写过的代码，问自己最漂亮的代码是什么。这个问题在我脑海中盘旋了许久。我意识到答案很简单：那就是快速排序。从不同的角度来看，这个问题其实有三个不同的答案。
我曾撰写了一篇关于分治算法的论文，在其中C.A.R. Hoare的快速排序算法无疑是众多算法中的佼佼者。它对于基础问题提供了优雅的解决方案，是一个真正的漂亮算法。我对这个算法怀有浓厚兴趣，但对其最内层的循环始终难以理解。曾有一次，我花费了两天时间调试一个基于这个循环的复杂程序。每当遇到类似的任务时，我都会谨慎地参考那段代码。它解决了问题，但我并未真正理解它。
后来，我从Nico Lomuto那里学习到了一个优雅的分块方案，并终于能够编写一个我能理解甚至证明正确的快速排序。我遵循了William Strunk Jr.的忠告：“良好的写作风格应是简洁的。”这一原则同样适用于编程。我努力将大约40行的代码缩减至12行。那么，如果问到我写过的最漂亮的一小段代码是什么？那就是用C语言实现的快速排序函数，如下所示：
```c
void quicksort(int l, int u) {
int i, m;
if (l >= u) return;
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的奥秘时，开发者曾认为它过于简单，甚至不值得发表。在深入探究其预期的运行时之后，他撰写了经典的“Quicksort”论文，为我们揭示了这一排序算法的精髓。
尽管在最坏的情况下，快速排序可能需要NN的时间来排序包含n个元素的数组，但在最佳情况下，其选择中值作为分区元素，使得数组的比较次数大约为nlogn。那么，对于包含n个不同值的随机数组，其平均需要多少次比较呢？
Hoare对于这个问题的分析极具洞察力，这种分析对于许多程序员来说，其数学难度超出了理解范围。在教授本科生快速排序时，我时常感到沮丧，因为许多学生即使经过努力也难以理解证明过程。为了解决这个问题，我们现在采用实验的方法，从Hoare的程序出发，最终以其分析作为结尾。
我们的任务是修改随机快速排序的示例代码3-1，分析其对不同输入数组排序的平均比较次数。我们将以尽可能少的代码、运行时和内存空间来获得最佳的效果。
为了确定平均比较次数，我们首先在程序中增加了一个计数器来计算它们。为此，我们在内部循环的每个比较之前增加变量comps（参见示例3-2）。
示例3-2展示了如何在循环中增加比较计数。如果我们运行此程序并给定一个值n，我们可以看到程序需要进行多少次比较来完成排序。如果我们多次运行程序并对结果进行统计分析，我们会发现平均而言，快速排序需要对n个元素进行大约1.4 n log n次的比较。
通过了解程序的行为并进行实验，我们可以深入了解程序的性能。虽然只有短短的13行代码和一些实验就能揭示许多信息，但我们仍有提升空间。正如Blaise Pascal 和 T. S. Eliot等作家所言，“如果我有更多的时间，我会给你写一封更短的信。”我们有足够的时间来试验代码并尝试创建一个更简洁、更高效的程序。
我们将加快实验的速度并努力提高统计准确性和编程水平。由于内部循环总是进行精确的(u-l)次比较，我们可以通过在循环外部的一个操作中计算这些比较来稍微加快程序的速度。这个改进产生了示例3-3中的快速排序算法。
如果我们仅关注统计比较而不是排序本身，那么我们实际上不需要对数组进行完整的排序操作。示例3-4中省略了对元素的排序操作，仅保留了程序的基本框架。这个程序能够运行是因为Quicksort以随机方式选择分区元素，并且假设所有元素都是唯一的。这个简化版的程序现在与n成比例运行，并且只需要与lgn成比例的平均递归堆栈空间。虽然在实际程序中数组的索引（l和u）至关重要，但在当前这个版本中它们并不重要。我们可以用一个表示要排序的子数组大小的整数（n）来替换这两个索引（参见示例3-5）。
我们将这个过程重新定义为一个比较计数函数，该函数返回随机快速排序运行所使用的比较次数。这个函数的形式如示例3-6所示。
示例3-4、示例3-5和示例3-6都解决了相同的核心问题，并且使用了相同的运行时和内存。每个后续函数都改进了函数的形式，使其更加简洁明了。在解决这个问题的过程中，我们将利用“发明家的悖论”，不断尝试和改进，以期在快速排序的分析中获得更多的成功机会。自提出“快速排序在一次大小为n的运行中做了多少比较？”的问题后，我们现在更深入地探索了一个更具挑战性的问题：“对于大小为n的随机数组，Quicksort平均进行了多少次比较？”让我们通过扩展示例3-6来生成新的思考路径。
例3-7
=====
假设我们有一个函数 `float c(int n)`，它计算了对于大小为n的随机数组，Quicksort的平均比较次数。如果输入只有一个元素，那么无需比较。对于较大的n值，我们需要考虑每一个可能的分区值m，从第一个元素到最后一个元素。每个元素被选为分区值的概率是相等的。我们需要计算每个分区值的成本，然后求和并取平均值。这个过程涉及到递归地解决两个子问题：一个大小为m-1的问题和一个大小为n-m的问题。这种计算方法的复杂度与n的三次方成正比。
为了优化这个过程，我们可以引入一个表t[N+1]，其中t[N]存储的是c(N)的值。这样我们可以避免重复计算子问题。我们让N代表我们想要排序的数组的最大大小。接下来是例3-8的实现。
例3-8
=====
首先初始化t[0]为0。然后，对于每一个n从1到N，我们计算所有可能的分区值的成本并求和，然后取平均值，将这个值存储在t[n]中。这个程序的运行时间与N的平方成正比。值得注意的是，当程序结束时，数组t包含了真正的平均值，而不仅仅是样本均值的估计。这些值可以为我们提供关于预期比较次数的深刻洞察。
我们可以进一步优化这个程序。我们可以将表达式n-1移出循环，如例3-9所示。然后，我们可以利用对称性来简化计算。例如，当n=4时，我们可以观察到内部循环中的计算模式，并利用这个模式来减少计算量，如例3-10所示。这个程序仍然会一次又一次地重新计算相同的总和。我们可以通过在循环外部初始化sum并添加下一项来优化它，而不是添加所有前面的项，从而生成例3-11。
例3-11
======
这个小程序是漫长编程之路上的一个里程碑。正如Alan Perlis所言：“简单并不先于复杂，而是在它之后。”我们的旅程从复杂的算法开始，最终回到简单的代码。这是一个从复杂到简单，从算法到性能分析的过程，每一步都让我们受益匪浅。
那么，让我们来看看最后的惊喜吧！运行下面的代码，你会发现一个有趣的输出：
```c
include
int main() {
int i = 3;
int arr[] = {85, 3, 73};
while (i--) {
printf("%c ", arr[i]);
}
return 0;
}
```
执行结果是什么呢？欢迎在评论区分享你的答案！希望你在这个编程之旅中收获满满，同时也享受到了编程的乐趣。 |
