cs61b-sort

2023-09-25 09:11:40

第三节课-sort（testing）

这节课的主要目的：写一个给字符串数组自动排序的方法。
所写的内容包括：排序和检验代码的测试

1:先从测试入手

/** tests the sort class*/
public class testsort {
    public static void  testsort() {
        String[] input={"I","eat","an","apple"};
        String[] expected={"eat","I","an","apple"};
        Sort.sort(input);
        if(input!=expected){//行8——注意这一行
            System.out.println("error!these seem to be a problem with sort.sort.");
        }
    }
    public static void main(String[] args) {
        testsort();
    }
}

第一次写的代码如上，但是这里显然是行不通的，因为在sort类里什么都没有做。
但是除此之外，还有一个很大的BUG存在。
【行8里，此处滥用了不等号】
在这里，不等号的比较，比较的是地址，即使他们有一样的内容，但是地址不同，这里输出的结果就是不等的

那么我们可以用另一个方法/工具替换这句语句。

  if(!java.util.Arrays.equals(input,expected)){
            System.out.println("error!these seem to be a problem with sort.sort.");
        }

【这个方法会自动检索两个进行比较的字符串】
此时改进这个方法之后，只剩下了sort类没有编写的问题。
但是由于这里的代码不够详细，需要再补充改进一下。

代码如下：


/** tests the sort class*/
public class testsort {
    public static void  testsort() {
        String[] input={"I","eat","an","apple"};
        String[] expected={"eat","I","an","apple"};
        Sort.sort(input);

        for(int i=0;i<input.length;i++){
            if (!input[i].equals(expected[i])){
                System.out.println("Mismatch in position"+"i"+",expected:"+expected[i]+",but got:"+input[i]);
                return;
            }
        }
        /**if(!java.util.Arrays.equals(input,expected)){
            System.out.println("error!these seem to be a problem with sort.sort.");
        }*/
    }
    public static void main(String[] args) {
        testsort();
    }
}

2:用一行junit代码代替冗余代码

其实上述代码是我们利用特殊目标代码来写的测试sort方法。
真正意义上冗杂的就是我刚刚补充的那段代码

 for(int i=0;i<input.length;i++){
            if (!input[i].equals(expected[i])){
                System.out.println("Mismatch in position"+"i"+",expected:"+expected[i]+",but got:"+input[i]);
                return;
            }
        }

所以，可以利用一些工具来帮我们完成这个工作。
可以使用【Junit库来自动编写这样的代码】
一开始我按照课堂上写的是

org.junit.Assert.assertArrayEquals(expected,input);

但是系统一直报错Cannot resolve symbol ‘Assert’
于是我查阅了一下资料，我的external libraries里面是junit5.7.0，这个版本的assert断言方法是这样用的：

org.junit.jupiter.api.Assertions.assertArrayEquals(expected,input);

果然改了以后就没报错了。

3：着手解决sort问题

到目前为止，我只是写了一个测试。然而我实际上要解决的问题比这个要大得多。
现在重点放到排序sort上面。
以选择排序（selection sort）为例：cs61b-sort
对于解决这个排序，有三个步骤：
1:找出最小项
2:进行交换swap
3:对余下的进行排序（可能会使用到recursion递归的思想）

之前的课堂上介绍了使用辅助函数的方法，所以在这里我们继续使用辅助函数来解决问题。

现在来到sort类：
【1：找到最小项】

public class sort {
    /**sorts string destructively*/
    public static void sort(String[]x){
        //find the smallest item
        //move it to the front
        //selection sort the rest(using recursion
    }
    private String findSmallest(String[]x){
        return x[2];//假设返回位置为2的数据
    }
}
然后在测试类里面写测试：

```java
/**Test the Sort.findSmallest method*/
        public static void testfindsmallest(){
            String[] input={"I","eat","an","apple"};
            String expected="an";/这里期望的不再是像上面一样暴力排序的句子，而是一个特定的对象。
            String actual=sort.findSmallest(input);
            org.junit.jupiter.api.Assertions.assertEquals(expected,actual);//比较的对象发生了变化
        }

在main里调用：

 public static void main(String[] args) {
        testfindsmallest();
    }

最后结果：
cs61b-sort
代码没有问题，说明结果一致。
但是这个结果是我们刻意为之，我可以在sort类的findsmallest方法在改写返回的下标以及改写返回类型。
如改为null：
结果如下：
cs61b-sort

因此我们需要利用一些代码来实现sort类里自动索引：

 public static String findSmallest(String[] x){
       int smallestIndex=0;
       for(int i=0;i<x.length;i++){
           if(x[i]<x[smallestIndex]){
               smallestIndex=i;

           }
       }
       return x[smallestIndex];
    }

但是这时候会报错，因为小于运算不能被应用在两个字符串之间。
因此修改：

  public static String findSmallest(String[] x){
       int smallestIndex=0;
       for(int i=0;i<x.length;i++){
           int cmp=x[i].compareTo(x[smallestIndex]);
           //如果x[i]<x[smallestIndex]，cmp将会返回-1
           if (cmp<0){
               smallestIndex=i;
           }
       }
           /**if(x[i]<x[smallestIndex]){
               smallestIndex=i;

           }
       }*/
       return x[smallestIndex];
    }

然后再去testsort类中改变expected为I，显然此时已输出最小字符。
这时已经完成了其中一项：【找出最小项】。

【2:对A和B进行交换】
首先在sort类里编写了swap方法，实现交换需要引入第三个量来做缓存作用：

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

其次，在testsort类中编写testSwap方法：

public static void testSwap(){
            String[] input={"I","eat","an","apple"};
            int a=0;
            int b=2;
            String[] expected={"an","eat","I","apple"};
            sort.swap(input,a,b);
            org.junit.jupiter.api.Assertions.assertEquals(expected,input);
        }

然后在main函数中调用testswap看是否成功

public static void main(String[] args) {
        testSwap();
    }

结果如下：

expected: [Ljava.lang.String;@2e0fa5d3<[an, eat, I, apple]> 
but was: [Ljava.lang.String;@5010be6<[an, eat, I, apple]>

然后我去搜了一下为什么在输出中会出现前面一堆，了解：“[” 表示一维数组
"[["表示二维数组
"L"表示一个对象
"java.lang.String"表示对象的类型
"@"后面表示该对象的HashCode
啥是HashCode
hashCode:散列码是由对象导出的一个整型值。散列码是没有规律的。类的hashCode()方法继承自Object类，因此每个对象都有一个默认的散列码，他的值为对象的存储地址（由对象的物理存储地址通过散列转换来的）。

实现这两个功能后，要做的就是把它们合到一起：
【3:结合】
在sort方法里写结合调用语句：

int smallestIndex=findSmallest(x);
        swap(x,0,smallestIndex);

其实一开始写的是string但是是有问题的，因为不匹配。
改成int类型，相应的findsmallest方法的返回类型也改为int。
在测试方法中也将输入的数据变为下标所表示的int类型。
更改如下：

public static void testfindsmallest(){
            String[] input={"I","eat","an","apple"};
            int expected=2;
            int actual=sort.findSmallest(input);
            org.junit.jupiter.api.Assertions.assertEquals(expected,actual);
        }

public static int findSmallest(String[] x){
       int smallestIndex=0;
       for(int i=0;i<x.length;i++){
           int cmp=x[i].compareTo(x[smallestIndex]);
           //如果x[i]<x[smallestIndex]，cmp将会返回-1
           if (cmp<0){
               smallestIndex=i;
           }
       }
           /**if(x[i]<x[smallestIndex]){
               smallestIndex=i;

           }
       }*/
       return smallestIndex;
    }

【4:最后一步，弄清楚对数组的其余部分如何排序】
考虑递归
代码如下：

/**sorts x starting at position start*/
    public static void sort(String[] x,int start){
     if(start==x.length){
            return;
        }
        int smallestIndex=findSmallest(x);
        swap(x,start,smallestIndex);
        sort(x,start+1);
    }
上一篇：开发记录：涉及到日期时间以及星期转换


下一篇：[leetcode] 557. Reverse Words in a String III