Week 3.2 | Lecture 7 | JUnit、选择排序 | CS61B-Spring-2018

JUnit

• 每次修改都应该进行test确保方法的正确性。
• 将一个算法分为各个小方法，能够简化方法的实现。并且，每次对小方法的实现进行测试，能够确保每个小部分的正确性，从而减少组装整个算法时的错误。

JUnit文档

注意：

1. 若要使用@Test注解：必须将test方法改成非静态。且不用写main函数。（不使用@Test，可以写为static方法，并在main函数中调用）
2. 使用import可以省略掉@org.junit.Test和org.junit.Assert.assertEquals(expected2, actual2);

import org.junit.Test
import static org.junit.Assert.*
public class TestSort {
    ...
    @Test
    public void testFindSmallest() {
        String[] input = {"i", "have", "an", "egg"};
        String expected = "an";

        String actual = Sort.findSmallest(input);
        assertEquals(expected, actual);        
    }
}

ps.如果要在一定时间后使测试超时（以防止无限循环），则可以这样声明测试：
@Test(timeout = 1000)

测试驱动开发Test-Driven Development （TDD）

TDD是一个开发过程，其中我们在编写代码本身之前编写代码测试。步骤如下：

1. 识别新功能。
2. 为此功能编写一个单元测试。
3. 运行测试。它应该失败。
4. 编写通过测试的代码。好极了！
5. 可选：重构代码以使其更快，更干净等。

在这个课程中不需要测试驱动开发，它不一定是您的风格，但是一般而言，单元测试绝对是个好主意。

选择排序

以下是实现该算法的步骤

1.写出算法所需步骤

public class Sort {
    /** Sorts strings destructively. */
    public static void sort(String[] x) { 
           // find the smallest item
           // move it to the front
           // selection sort the rest (using recursion?)
    }
}

2. findSmallest

• 在开始写该方法之前，在TestSort.java中写一个testFindSmallest方法，用于test该方法正确与否。

• findSmallest

/** Returns the smallest string in x. 
  * @source Got help with string compares from https://goo.gl/a7yBU5. */
public static int findSmallest(String[] x) {
    int smallestIndex = 0;
    for (int i = 0; i < x.length; i += 1) {
        int cmp = x[i].compareTo(x[smallestIndex]);
        if (cmp < 0) {
            smallestIndex = i;
        }
    }
    return smallestIndex;
}

// the str1.compareTo(str2) method will return a negative number if str1 < str2, 0 if they are equal, and a positive number if str1 > str2.（字母顺序比大小）

• 运行test，看看是否成功。

3.swap

public static void swap(String[] x, int a, int b) {
    String temp = x[a];
    x[a] = x[b];
    x[b] = temp;
}

然后test it。

4. 递归sort

最后一步是递归排序剩下的数组，但是Java中无法直接取剩下的数组。

典型的解决方案是创建一个private helper方法，该方法具有一个或多个额外的参数，这些额外的参数用于描述要考虑的数组的哪一部分。例如，我们可以编写一个也称为sort的private帮助器方法，该方法只考虑以start参数开头的items。

当尝试在本来不是递归的数据结构（例如数组）上使用递归时，这种方法非常普遍。

/** Sorts strings destructively starting from item start. */
private static void sort(String[] x, int start) { 
   if (start == x.length) {
       return;
   }
   int smallestIndex = findSmallest(x);
   swap(x, start, smallestIndex);
   sort(x, start + 1);
}

在原sort方法中调用该辅助方法：

/** Sorts strings destructively. */
public static void sort(String[] x) { 
   sort(x, 0);
}

之所以还要多出一个sort(String[] x)方法而不是直接在main中使用sort(String[] x, int start)的主要原因是，sort(String[] x)更好理解，更易于使用，不需要了解sort(String[] x, int start)的实现原理和start是什么就可以使用。

5.修改findSmallest

在使用递归后，发现原findSmallest方法只返回整个数组中最小的，但是实际上应该是剩余数组中最小的，所以加入start参数来描述开始的索引。

public static int findSmallest(String[] x, int start) {
    int smallestIndex = start;
    for (int i = start; i < x.length; i += 1) {
        int cmp = x[i].compareTo(x[smallestIndex]);
        if (cmp < 0) {
            smallestIndex = i;
        }
    }
    return smallestIndex;
}

test it。

最终：

/** Sorts strings destructively starting from item start. */
private static void sort(String[] x, int start) { 
   if (start == x.length) {
       return;
   }
   int smallestIndex = findSmallest(x, start);
   swap(x, start, smallestIndex);
   sort(x, start + 1);
}

testSort.