【reading】【中文】 3.1 A New Way
测试和选择排序
中高级程序员最重要的技能之一是能够判断代码是否正确。在本章中，我们将讨论如何编写测试来评估代码的正确性。同时，我们还将介绍一种称为选择排序的排序算法。
一种新的方法
当你编写程序时，它可能会有错误。在课堂环境中，你通过用户交互、代码分析和自动测试（在许多情况下最重要的）来增强代码的正确性。当然，自动评分系统并不是魔法。它们是由教师编写的代码，其本质上与你自己编写的代码并没有太大区别。在真实世界中，这些测试是由程序员自己编写的，而不是由像乔·休格这样的善良的第三方编写的。
在本章中，我们将探讨如何编写我们自己的测试。我们的目标是创建一个名为 Sort 的类，该类提供了一个 sort(String[] x) 方法，以对数组 x 中的字符串进行排序。
作为一种全新的思考方式，我们将首先编写 testSort()，仅在完成测试之后，才开始编写实际的排序代码。
特定目的的测试
为 Sort.sort 编写测试相对简单，尽管可能有些乏味。我们只需要创建一个输入，调用 sort 方法，并检查方法的输出是否正确。如果输出不正确，我们会输出第一个不匹配项并终止测试。例如，我们可以创建一个如下所示的测试类：
我们可以通过创建一个空的 Sort.sort 方法来测试我们的测试，如下所示：
如果我们在这个空的 Sort.sort 方法中运行 testSort() 方法，我们将得到：
我们得到了一个错误消息，这是一件好事！这意味着我们的测试有效。这非常有趣的一点是，我们现在为自己创造了一个小游戏，目标是修改 Sort.sort 中的代码，使得这个错误消息不再出现。这有点像一个心理游戏，许多程序员发现为自己设计这些小迷题几乎会上瘾。
事实上，这非常类似于为课程的自动评分系统而努力，你发现自己迷恋于让自动评分系统给予你它的喜爱和赞赏。现在，你有了为代码创建一个评委的能力，只有通过正确完成代码，才能赢得它们的崇敬。
重要说明：你可能会问，为什么要遍历整个数组？为什么不使用 == 检查数组是否相等呢？原因是，当我们测试两个对象是否相等时，不能简单地使用 == 运算符。== 运算符比较的是内存中的字面位，例如 input == expected 检查 input 和 expected 的地址是否相同，而不是数组中的值是否相同。因此，在 testSort 中，我们使用了一个循环，并打印出第一个不匹配项。你也可以使用内置的 java.util.Arrays.equals 方法来代替循环。
虽然上面的单个测试并不是太多工作，但是编写一套这样的特定目的的测试将非常乏味，因为这将涉及到编写大量不同的循环和打印语句。在下一节中，我们将看到如何使用 org.junit 库节省大量的工作。
JUnit 测试
org.junit 库提供了许多有用的方法和实用的功能，可简化测试的编写。例如，我们可以使用以下方法替换上面简单的特定目的的测试：
这段代码更简单，并且基本上完成了相同的工作，即如果数组不相等，则会告诉我们第一个不匹配项。例如，如果我们在一个什么都不做的 Sort.sort 方法上运行 testSort()，我们将得到：
虽然这个输出比我们特定目的的测试有点丑陋，但我们将在本章的最后看到如何使其更好看。
选择排序
在编写 Sort.sort 方法之前，我们需要一些排序算法的思路。也许最简单的排序算法是“选择排序”。选择排序由三个步骤组成：
找到最小的项。
将其移到最前面。
对剩下的 N-1 个项进行选择排序（不会改动前面的项）。
例如，假设我们有数组 {6, 3, 7, 2, 8, 1}。该数组中最小的项是 1，因此我们将 1 移到开头。有两种自然的方法可以实现这一点：一种是将 1 放在开头并将所有数字往后移动，即 {1, 6, 3, 7, 2, 8}。然而，更高效的方法是将 1 与旧的第一个项（在本例中为 6）进行交换，得到 {1, 3, 7, 2, 8, 6}。
我们只需要重复相同的过程，即可对剩下的数字进行排序，即 {1, 3, 7, 2, 8, 6} 的最小项是 2。将其移到开头，我们得到 {1, 2, 7, 3, 8, 6}。继续重复这个过程，直到我们得到一个排序好的数组，我们将得到 {1, 2, 3, 7, 8, 6}，然后是 {1, 2, 3, 6, 8, 7}，最后是 {1, 2, 3, 6, 7, 8}。
我们可以通过使用第 2.4 章介绍的不变量的概念，在任何数组上对这个排序算法的正确性进行数学证明，但在本教程中我们不会这样做。在继续之前，试着自己写下一组短数字数组，并对其执行选择排序，以确保你理解了思路。
现在我们知道选择排序是如何工作的，我们可以在我们空白的 Sort.sort 方法中添加一些简短的注释来指导我们的思考：
在接下来的几节中，我将尝试完成选择排序的实现。我会像学生一样逐步完成，并会有一些故意的错误。这些故意的错误是有益的，因为它们将帮助演示测试的有用性。如果你在阅读时注意到任何错误，不要担心，我们最终会对其进行更正。
寻找最小项
最自然的开始地方是编写一个在列表中查找最小项的方法。与 Sort.sort 一样，我们将在完成方法之前先编写一个测试。首先，我们将创建一个简单的 findSmallest 方法，它只是返回某个任意的值：
显然，这不是一个正确的实现，但我们选择在编写测试之前先不考虑 findSmallest 的实现。使用 org.junit 库，我们很容易将此测试添加到我们的 TestSort 类中，如下所示：
和 TestSort.testSort 一样，我们运行我们的 TestSort.testFindSmallest 方法，以确保它失败。当我们运行这个测试时，我们会看到它实际上通过了，即没有出现任何消息。这是因为我们刚好硬编码了正确的返回值 x[2]。让我们修改我们的 findSmallest 方法，使其返回一个明显不正确的值：
进行了这个更改后，当我们运行 TestSort.testFindSmallest 时，我们将得到一个错误，这是一件好事：
和以前一样，我们给自己设了一个小游戏，我们的目标现在是修改 Sort.findSmallest 的代码，以使这个错误不再出现。这个目标比使 Sort.sort 工作更容易一些，可能也更容易上瘾。
注意：我好像故意硬编码了正确的返回值 x[2]，这看起来有些别扭。但当我录制这个讲座视频时，我确实做了这个无意识的错误！
接下来，我们将解决真正编写 findSmallest 方法。这似乎应该相对简单。如果你是一个 Java 初学者，你可能会写出类似下面这样的代码：
然而，这将导致编译错误 "无法将 < 运算符应用于 'java.lang.String'"。问题在于 Java 不允许使用 < 运算符比较字符串。
当你在编程过程中遇到这种容易描述的问题时，最好使用搜索引擎。例如，我们可以使用谷歌搜索“java 字符串比较小于”，这样的搜索结果可能会包含像 这个: https://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java 的 Stack Overflow 帖子。
这篇帖子中的一个受欢迎答案解释了 str1.compareTo(str2) 方法的工作原理：如果 str1 < str2，该方法将返回一个负数；如果它们相等，则返回0；如果 str1 > str2，则返回一个正数。
将这一点融入到我们的代码中，我们可能得到：
注意我们在代码中使用了 @source 标签，以引用我们的来源。我为那些正式学习 61B 的人使用这个例子，这不是真实世界的典型做法。
由于我们在使用全新的语法功能，我们可能对 findSmallest 方法的正确性缺乏自信。幸运的是，我们刚刚写了那个测试不久之前。如果我们尝试运行它，我们会发现没有任何输出，这意味着我们的代码可能是正确的。
为了增加我们的信心，可以通过添加更多的测试用例来增加我们的信心。例如，我们可以更改 testFindSmallest 如下所示：
重新运行测试，我们将看到它仍然通过了。虽然我们并不能完全确定它是否正确，但我们比没有任何测试时更有把握了。
Swap 交换
看一下下面的sort方法，我们需要写的下一个辅助方法是将一个元素移到数组前面，我们称之为swap。
写一个swap方法非常简单，你可能之前已经做过了。一个正确的实现可能如下所示：
然而，为了展示测试的作用，让我们引入一个有意的错误。一个不太熟悉的程序员可能会这样写：
通过使用JUnit辅助方法，编写一个针对这个方法的测试非常容易。下面是一个样例测试。需要注意的是，我们还修改了主方法，让它调用testSwap而不是testFindSmallest或testSort。
对我们这个有错误的swap方法运行这个测试，会得到一个错误，这是我们预期的。
值得注意的是，我们只调用了testSwap而没有调用testSort，如果我们的main方法如下所示，当testSort失败时，整个main方法都会终止执行，testSwap将永远不会运行：
在本章的最后，我们将学习一种更优雅的处理多个测试的方法，它将避免手动指定要运行的测试的需要。
现在我们有了一个失败的测试，我们可以用它来帮助我们调试。一种方法是在swap方法内设置一个断点，并在IntelliJ中使用可视化的调试功能。如果你想要了解更多关于调试的信息和实践，可以参考<a href="https://sp19.datastructur.es/materials/lab/lab3/lab3">Lab3:</a> 。通过逐行调试代码，很容易理解出问题所在（可以观看视频或自己尝试），然后我们可 以通过在这一节开始时添加一个临时变量来修复代码：
再次运行测试，我们将会看到测试通过了。
修改findSmallest
现在我们已经有了多个方法的片段，我们可以开始尝试将它们连接在一起以创建Sort方法。
很明显，我们可以使用findSmallest和swap方法，但当我们这样做时就会立即意识到存在一个不匹配的问题：findSmallest返回一个字符串，而swap方法需要两个索引。
换句话说，findSmallest应该返回的是最小字符串的索引，而不是字符串本身。出现这种错误是很正常的，而且很容易发生，所以如果你发现自己也这样做了，不要担心。在编写代码的过程中，反复修改设计是很正常的。
幸运的是，这个新设计可以很容易地修改。我们只需要调整findSmallest，让它返回一个int，如下所示：
由于这是一个非常重大的改变，我们还应该更新testFindSmallest，并确保findSmallest仍然有效。
在修改TestSort以便运行这个测试，并运行TestSort.main后，我们看到我们的代码通过了测试。现在，我们可以继续修改sort方法，填入排序算法的前两个步骤。
现在只剩下一步了，即如何使用递归选择排序剩下的元素。我们将在下一节中解决这个问题。
回顾我们已经完成的工作，值得注意的是，我们在实际方法之前创建了测试，并在使用这些测试之前用它们来建立对实际方法的信心。这是一个非常重要的思想，如果你决定采用这种方式，它将对你有很大的帮助。
递归辅助方法
在本节开始时，考虑一下如何进行递归调用，以完成sort方法：
对于你们中那些习惯了使用类似Python这样的语言的人来说，可能会尝试使用类似切片表示法的方法，比如
然而，在Java中没有一个可以引用一个子数组的概念，也就是说，我们不能只传递数组的下一个项的地址。
需要考虑的是，需要考虑一个较大数组的子集是一种非常常见的问题。一个典型的解决方法是创建一个私有的辅助方法，这个方法有一个额外的参数（或多个参数），用来确定需要考虑的数组的哪一部分。例如，我们可以编写一个称为sort的私有辅助方法，该方法只考虑从位置start开始的项。
与我们的公共sort方法相比，现在使用递归会相对简单一些，因为我们多了一个名为start的额外参数。下面是一个使用递归的示例。在下一节中，我们将对这个方法进行测试。
现在我们有了一个辅助方法，我们需要设置正确的原始调用。如果我们将开始位置设置为0，我们就可以对整个数组进行排序。
当你在试图对一个本质上不是递归的数据结构使用递归时，这种方法非常常见，比如数组。
调试和完成Sort方法
运行我们的testSort方法，我们立即遇到了一个问题：
使用Java调试器，我们可以看到问题是start不断增加，变成了4。仔细地逐行调试代码（参见上面的视频），我们发现问题在于我们在递归sort方法中忘记了包含一个基本情况。修复这个问题非常简单：
重新运行这个测试，我们再次得到一个错误：
再次使用IntelliJ调试器进行恰当的调试（请参见视频），我们可以确定一行代码的结果与预期不符。需要注意的是，我在比你可能更高级的抽象层次上调试代码，这是通过使用“跳过”比“进入”更多地使用Step Over来实现的。如在Lab 3中讨论的，以更高的抽象级别进行调试可以节省大量的时间和精力，因为这样你可以比较整个函数调用的结果与你的预期值。
具体来说，我们发现在对输入{"an", "have", "i", "egg"}进行排序时，当排序剩下的3个（共4个）项时，findSmallest方法给出的是第0个项（"an"），而不是第3个项（"egg"）。仔细看看findSmallest的定义，不难发现，由于findSmallest看的是整个数组而不只是从start位置开始的项，所以这个行为并不令人意外。这种设计缺陷非常常见，编写测试并使用调试器来修复它们是一个很好的方法。
为了修复我们的代码，我们将findSmallest修改为接受第二个参数start，即findSmallest(String[] x, int start)。这样，我们确保只在未排序的项中找到最小项。修改后的代码如下所示：
由于我们对一个基本模块进行了重大更改，即findSmallest，我们应该确保我们的更改是正确的。
首先，我们修改了testFindSmallest，使它使用我们的新参数，如下所示：
然后，我们修改了TestSort.main，以便运行testFindSmallest。这个测试通过了，强烈暗示我们对findSmallest的修改是正确的。
接下来，我们修改了Sort.sort，使它在findSmallest中使用新的start参数：
然后，我们修改了TestSort，使它运行TestSort.sort，好了，这个方法可以工作了。我们完成了！你现在已经看到了这节讲座一开始的“新方法”，我们将在本章的剩余部分反思这个方法。
开发过程反思
当你编写和调试程序时，你经常会发现自己在不同的上下文之间切换。试图一次记住太多的东西，最终会导致灾难性的后果，或者最好情况下进展缓慢。
拥有一组自动化测试有助于减少这种认知负担。例如，当我们意识到findSmallest中存在一个bug时，我们可以切换到考虑findSmallest并使用我们的testFindSmallest方法来确定它是否正确，然后再切换回sort。这与一种更幼稚的方法形成了鲜明对比，你只会一遍又一遍地调用sort，然后尝试推断出findSmallest方法是否正确。
打个比方，你可以通过上飞机、起飞、跳伞、拉动降落伞绳索并看看降落伞是否打开来测试降落伞绳索是否有效。然而，你也可以在地面上拉一下绳索看看会发生什么。同样地，使用sort来尝试findSmallest是不必要的。
正如本章的开头所提到的，测试还可以帮助您对程序的基本部分建立信心，所以如果出现问题，您就可以更好地了解从哪里开始解决。
最后，测试使得重构代码变得更容易。假设您决定重写findSmallest，使其更快或更易读。我们可以安全地进行修改，然后查看测试是否仍然工作。
更好的JUnit
首先，让我们回顾一下我们今天所见到的新语法，即 org.junit.Assert.assertEquals(expected, actual)。这个方法（有一个非常长的名字）测试 expected 和 actual 是否相等，如果它们不相等，则用一个详细的错误消息终止程序。
JUnit 除了 assertEquals 之外还有许多类似的方法，比如 assertFalse、assertNotNull、fail 等等，它们可以在官方的 JUnit文档中找到。JUnit 还有许多其他复杂的功能，在61B中我们不会描述或教授，但你可以自由使用它们。
虽然JUnit无疑改进了很多问题，但我们之前的测试代码在几个方面都有些笨拙。在本节的剩余部分，我们将讨论两个主要的增强功能，以使您的代码更清晰、更易于使用。从语法的角度来看，这些增强功能似乎非常神秘，所以现在只需复制我们所做的，以后我们会在后面的章节中解释其中的一些（但不是全部）。
第一个增强功能是使用被称为 "测试注释 "的功能。为此，我们需要：
一旦我们完成了这三步，如果我们使用 Run->Run 命令在 JUnit 中重新运行我们的代码，所有的测试都将自动执行，无需手动调用。这种基于注释的方法有几个优点：
第二个增强功能允许我们为一些非常冗长的方法名称以及注释名称使用较短的名称。具体来说，我们将使用被称为 "导入语句 "的功能。
首先，在文件的顶部添加导入语句 import org.junit.Test;。这样做后，我们可以将所有的 @org.junit.Test 替换为简单的 @Test。
然后，我们添加第二个导入语句 import static org.junit.Assert.*。这样做后，我们可以省略任何地方的 org.junit.Assert.。例如，我们可以将 org.junit.Assert.assertEquals(expected2, actual2); 替换为简单的assertEquals(expected2, actual2);。
关于导入语句的原因我们将在以后的课程中详细解释。现在，只需要使用和享受它。
测试哲学
正确性工具1: 自动打分机
让我们回到零点。自动打分机很可能是你接触到的第一个正确性工具。实际上，我们的自动打分机是基于 JUnit 加上一些额外的自定义库。
自动打分机有一些很大的好处。可能最重要的是，它为你验证了正确性，为你节省了写测试的繁琐和无指导性的任务。它还通过给予丰厚的分数作为正确性的激励来使评估过程充满乐趣。不过，如果学生花费过多的时间追逐最后的分数，这可能也会适得其反，因为这些分数实际上并不会影响他们的成绩或学习。
然而，自动打分机在现实世界中是不存在的，依赖于自动打分机可能会养成不好的习惯。通过偶尔上传你的代码并等待自动打分机运行来妨碍了你的工作流程。自动打分机驱动的开发（Autograder Driven Development） 就是这种情况的一个极端版本，在这种情况下，学生在写所有的代码、修复编译错误之后再提交到自动打分机。在收到错误后，学生可能会尝试进行一些更改，添加一些打印语句，然后再次提交。然后再重复以上步骤。如果你依赖于自动打分机，你既不能控制你的工作流程，也不能控制你的代码。
正确性工具2: JUnit 测试
正如我们所见，JUnit 测试为您打开了一个新的世界。与依赖于其他人编写的自动打分机不同，您为程序的每个部分编写测试。我们把这些部分称为一个单元。这样可以让您对代码的每个单元都有信心-您可以依赖它们。这也有助于减少调试时间，因为您可以将注意力集中在一段代码（通常是一个方法）上。单元测试还可以迫使您澄清每个代码单元应该完成什么任务。
然而，单元测试也有一些不足之处。首先，编写全面的测试需要时间。很容易编写不完整的单元测试，这给您的代码带来虚假的信心。编写依赖于其他单元的单元测试也很困难（考虑一下您的 LinkedListDeque 中的 addFirst 方法）。
*测试驱动开发（TDD）*
TDD 是一种在编写代码之前先编写代码测试的开发过程。步骤如下：
在本课程中，不要求使用测试驱动开发，也许这不是你的风格，但是总的来说，单元测试绝对是一个好主意。
正确性工具3: 集成测试
单元测试非常好，但我们也应该确保这些单元正确地一起工作。集成测试验证组件之间的正确交互。实际上，JUnit 就可以用于这个目的。你可以将单元测试看作是最详细的测试，而集成测试则是对此的抽象水平。
集成测试的挑战在于它很繁琐，手动进行测试很繁琐，但自动化测试又很具有挑战性。在高度抽象的水平上，很容易忽略细微或罕见的错误。
总结一下，你应该一定要编写测试，但只有当它们可能是有用的时候才编写！从 TDD 中获得灵感，先编写测试，然后再编写代码，在某些情况下这也是非常有帮助的。
下一步是什么？
Project1b
