红魔咖啡馆

头发越掉越多，头发越掉越少

0%

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 2 分钟

Project0 - 2048

Hard Mode

项目结构

1
2
3
4
5
6
7
8
9
10
proj0_hardmode
├── game2048logic
|   ├── GameLogic.java
|   ├── MatrixUtils.java
├── game2048rendering
    ├── Board.java
    ... (some other files) ...
    ├── Main.java
    ├── Side.java
    ├── Tile.java

分为了两个包：负责逻辑与负责渲染的，主要更改在负责逻辑的包中

Task1：游戏原理

2048的核心规则为Tilting，项目需要主要实现该功能

当两个方格发生融合时，遵循以下规则

  1. 两相同值的方格融合为一个，数值翻倍

  2. 由合并产生的新方块在该次移动中不会再次合并。例如，当[X, 2, 2, 4]（X 代表空格）向左移动时，结果应为[4, 4, X, X]而非[8, X, X, X]。这是因为最左侧的 4 已参与过合并，故不应二次合并

  3. 当融合方向上有三个相邻同值方块时，仅该方向最前方的两个方块会合并，第三个方块保不变。例如[X, 2, 2, 2]左移后应为[4, 2, X, X]，而非[2, 4, X, X]。

  4. 推论：若有四个相邻同值方块，则会合并出两个同值方块，如[2, 2, 2, 2]左移后应该为[4, 4, X, X]，但合并出的两个同值方块不会合并

Task2：实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static void compress(int[][] board, int c){
    int n = board.length;
    int[] comp = new int[n];
    int index = 0;
    for (int[] ints : board) {
        if (ints[c] != 0) {
            comp[index++] = ints[c];
        }
    }
    for (int i = 0; i<n; i++){
        board[i][c] = comp[i];
    }
}
public static void merge(int[][] board, int c){
    int n = board.length;
    for (int i = 0; i<n-1; i++){
        if(board[i][c]!=0 && board[i][c]==board[i+1][c]){
            board[i][c] *= 2;
            board[i+1][c] = 0;
            i++;

        }
    }

}
public static void moveColumn(int[][] board, int c){
   compress(board, c);
   merge(board, c);
   compress(board, c);


}
public static void moveUp(int[][] board){
    for (int i = 0; i<board.length; i++){
        moveColumn(board, i);
    }
}

compress函数用于压缩，即将所有数都移动到顶上，而不进行合并

merge函数用于将相邻的数进行合并

每次移动一列，然后循环处理每列，处理一列时移动后合并，合并后可能会出现中间合并剩下的空位置，需要再进行压缩

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 4 分钟

Lec16 - Extends, Sets, Maps, and BSTs

Extends

从前，若一个类是接口的下位词，我们使用implements来书写方法的实现

但若想实现一个类是另一个类的下位词，我们需要使用extends

extends可以用于类与类、接口与接口之间

例：实现RotatingSLList

即让最后一个元素右旋到第一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package Lec16;

public class RotatingSLList<Item> extends SLList<Item> {
    public void rotateRight(){
        Item x = removeLast();
        addFirst(x);
    }
    public static void main(String[] args){
        RotatingSLList<Integer> rsl = new RotatingSLList<>();
        rsl.addLast(10);
        rsl.addLast(11);
        rsl.addLast(12);
        rsl.addLast(13);

        rsl.rotateRight();
        rsl.print();
    }
}

extends继承了SLList中的所有成员：

  • 所有实例与静态变量
  • 所有方法（除了构造函数）
  • 所有嵌套类

但若成员是私有的就无法访问了

例：实现VengefulSLList

记录被删除的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package Lec16;


import java.util.ArrayList;
import java.util.List;

public class VengefulSLList<Item> extends SLList<Item>{
    private SLList<Item> deletedItems ;
    public VengefulSLList(){
        deletedItems = new SLList<Item>();
    }

    @Override
    public Item removeLast(){
        Item removedItem = super.removeLast(); // 使用父类的方法
        deletedItems.addLast(removedItem);
        return removedItem;
    }
    public void printLostItems(){
        deletedItems.print();
    }
    public static void main(String[] args){
        VengefulSLList<Integer> vsl = new VengefulSLList<>();
        vsl.addLast(1);
        vsl.addLast(5);
        vsl.addLast(10);
        vsl.addLast(15);

        vsl.removeLast();
        vsl.removeLast();

        vsl.printLostItems();
    }
}

这里我们实现了对继承方法的重写

其中，我们可以使用super来调用父类中的方法

BST

随机表

链表的搜索效率较慢，我们可以在不同节点间随机额外添加一些链接，这样可以依赖随机性获得更好的效率

二叉搜索树的原理

若我们将每次搜索都折半，就能大幅提高效率，一个链表可以进行如下改造：

BST

这是一棵二叉搜索树

二叉搜索树是一个有根的二叉树，对于书中的每个节点

  • 左子树中的每个节点的值都小于该节点的值
  • 右子树中的每个节点的值都大于该节点的值
BST

寻找特定元素

  • 若待寻找元素等于当前元素，返回
  • 若待寻找元素小于当前元素，前往左子树寻找
  • 若待寻找元素大于当前元素，前往右子树寻找

时间复杂度：\(\Theta(\log n)\)

因此搜索一颗完全BST的速度是很快的

1
2
3
4
5
6
7
8
9
10
static BST find(BST T, key sk){
    if (T==null)
        return null;
    if (sk.equals(T.key))
        return T;
    else if (sk<T.key)
        return find(T.left, sk);
    else
        return find(T.right, sk);
}

添加元素

首先寻找待插入元素

  • 若找到了就不进行操作
  • 若没找到
    • 创建一个新节点
    • 创建合适链接

使用递归书写

1
2
3
4
5
6
7
8
9
static BST insert(BST T, key ik){
    if (T==null) 
        return new BST(ik);
    if (ik<T.key)
        T.left = insert(T.left, ik);
    else if (ik>T.key)
        T.right = insert(T.right, ik);
    return T;
}

删除元素

删除没有孩子的节点：

直接删除，即将其父节点对应的左/右节点置空

删除一个孩子的节点：

要在维持BST性质的前提下删除：可以发现该节点的孩子一定大于（右侧）或小于（左侧）该节点

故我们可以寻找该节点的孩子，将指向它的节点指向他的孩子即可

删除两个孩子的节点：

找到左子树最大的节点或右子树最小的节点，替代待删除节点即可

发表于 分类于
本文字数： 555 阅读时长 ≈ 1 分钟

Lec15 - Disjoint Sets

解决连通性问题

较好的方法是只需要记录每个相连元素属于哪个集合，至于如何连接不必关心

数据结构的选择

sets

过于复杂并且耗时高

arrays

另一个想法是：起始将每个元素设置为不同id，只需要记录每个元素所在集合的id，连通只需要将该元素所在集合id改变为目标id即可；检查是否连通只需要检查id是否一致

时间复杂度：

连通方法复杂度还是高了一些

trees

想法是：给每一个元素分配一个父节点来代替id

  • 对于连通操作：可以找到要连通的两个集合的根节点，将一个的根节点设置为另一个

  • 对于检查连通操作：从待检查节点向上寻找父节点，一直找到根节点看是否相同即可

操作本质即寻根并操作根节点

时间复杂度：

优化树结构

我们需要最小化树高

  • 将较短的树连接到较长的树下
  • 若高度相同，则需要打破相同

规定：总是将更小的树根连接到更大的树上

注意：使用权重衡量才能最小化平均步数，而使用高度衡量只能最小化最坏步数

时间复杂度：

再次进行优化：

查找后将所有节点都连接到根节点上，这样再次查找不必再遍历

这样，随着操作继续，我们的树会变得越来越矮，直到树高为1，这样所有操作都很快

其中\(\alpha(N)\)为逆阿克曼函数，该函数的增长速度特别缓慢，对于具有意义的值x，\(\alpha(x)\)的值始终不大于4，故可以看作常数时间

发表于 分类于
本文字数： 705 阅读时长 ≈ 1 分钟

Lec13 - Asymptotics II

大\(\Theta\)

对于一个表达运行时间的式子\(R(N)\in \Theta(f(N))\)

意味着存在两个整数\(k_1\)与\(k_2\)使得\(k_1\cdot f(N)\leq R(N)\leq k_2 \cdot f(N)\)

对于所有\(N\geq N_0\)

常用该表示法描述函数的增长顺序与运行时长的增长率

大O

\(R(N)\in O(f(N))\)

意味着存在整数与\(k_2\)使得\(R(N)\leq k_2 \cdot f(N)\)

对于所有\(N\geq N_0\)

即大O表示仅被上界约束，描述小于等于\(f(N)\)

大\(\Omega\)

\(R(N)\in \Omega(f(N))\)

意味着存在两个整数\(k_1\)与\(k_2\)使得\(k_1\cdot f(N)\leq R(N)\)

对于所有\(N\geq N_0\)

常用该表示法描述函数的增长顺序与

即大\(\Omega\)表示仅被下界约束，描述大于等于\(f(N)\)

关系证明

证明若\(f(x)\in O(g(x))\)且\(f(x)\in \Omega(g(x))\)，则\(f(x)\in \Theta(g(x))\)

另一种表示形式

将\(g(x)\)除到\(f(x)\)下面，有\(a\leq \frac{f(x)}{g(x)}\leq b\)

  • 若\(\frac{f(x)}{g(x)}\)有上界，则\(f(x)\in O(g(x))\)

  • 若\(\frac{f(x)}{g(x)}\)有下界，则\(f(x)\in \Omega(g(x))\)

  • 若\(\frac{f(x)}{g(x)}\)有界，则\(f(x)\in \Theta(g(x))\)

发表于 分类于
本文字数： 384 阅读时长 ≈ 1 分钟

Lec11 - Asymptotics I

衡量计算花费的方法

使用客户端程序测量执行时间

优点：易测量，意义明显

缺点：可能需要大量计算时间，结果可能因机器、编译器、数据不同而不同

计算可能的操作数

对于输出的大小为N的数组，计算可能的操作数

优点：独立于机器，输入基于给到的模型，显示了算法如何进行拓展

缺点：很难计算

对给定N大小数组，选择一个特定输入来代表输入规模，计算该操作数

特定输入包括：

  • 最差情况
  • 最好情况

渐进表现

大多数情况下，对于很大的数据N，我们只关心其渐进表现

具有较好规模（如线性）的算法会比具有相对差规模（如抛物线型）有着更好的运行时间表现

简化等式

  1. 将表格用多个变量的等式表示

  2. 忽略低阶项

  1. 将所有系数转换为一个常数，即\(CN^2\)，将拥有这些常数的函数归到一类，称为\(\Theta(N^2)\)

即\(\Theta(N^2)\)是包含了最坏运行时间的函数集合，用于表达运行时间

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 3 分钟

Lec10 - Iterators, Object Methods

Iterators

使用迭代器可以让自己的数据类型可以被迭代（支持for-each loop）

  • 需要让对应类实现Iterable接口
  • 具有Iterator方法来返回迭代器对象（实现一个嵌套类）
  • 迭代器需要具有hasNext()和next()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package Lec10;

import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    private T[] items;
    private int size;

    public ArraySet(){
        items = (T[]) new Object[100];
        size = 0;
    }
    private class ArraySetIterator implements Iterator<T>{

        private int pos;
        ArraySetIterator(){
            pos = 0;
        }
        @Override
        public boolean hasNext() {
            if (pos<size){
                return true;
            }
            return false;
        }

        @Override
        public T next() {
            T itemToReturn = items[pos];
            pos++;
            return itemToReturn;
        }
    }
    public Iterator<T> iterator(){
        return new ArraySetIterator();

    }
    
}

（注：仅有迭代器部分，没有其他具体实现）

Object Method

Java中所有类都是Object的子类

toString()

给予一个object的字符串表示

println方法也调用了toString()方法

该方法类似于python中的repr方法，可以给类一个自定义的字符串输出形式

1
2
3
4
5
6
7
8
9
10
@Override
public String toString(){
    StringBuilder stringToReturn = new StringBuilder("{");
    for(T x: this){
        stringToReturn.append(x);
        stringToReturn.append(", ");
    }
    stringToReturn.append("}");
    return stringToReturn.toString();
}

this

this是当前对象的一个引用，可以使用this来访问自己的实例变量和方法

但java中this是不必须的

若方法中的局部变量和实例变量重名，此时必须要用this加以区分

equals()

equals()方法通过判断两个对象的地址来判断是否相同

当然，可以通过重写方法来改变其他判断相同的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public boolean equals(Object o){
    if (o instanceof ArraySet uSet){
        if (this.size != uSet.size()){
            return false;
        }
        for (T x: this){
            if (!uSet.contains(x)){
                return false;
            }
        }
        return true;
    }
    return false;
}

其中，关键字A instanceof B的用处如下

  • 检查o是否指向类B，若不是返回false
  • 若是，返回true并将A作为B类并命名为B后面的名字
  • o是null也可以运行

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 2 分钟

Lec9-Subtype Polymorphism, Comparators, Comparables, Generic Functions

Subtype Polymorphism

Java中没有重载运算符，故我们需要使用Comparable接口来实现类似功能

Java源码中对该接口的描述如下：

我们需要实现该接口

e.g. 定义Dog类，通过size属性比较两只狗的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package Lec9;

public class Dog implements Comparable<Dog>{
    public String name;
    public int size;
    public Dog(String n, int s){
        name = n;
        size = s;
    }
    @Override
    public int compareTo(Dog o) {
        if (size < o.size){
            return -1;
        }
        else if (size > o.size){
            return 1;
        }
        return 0;
    }
}

另一种写法

java规定了若更小则返回负数

1
2
3
4
@Override
public int compareTo(Dog o) {
    return size - o.size;
}

这种操作被称为子类型多态

  • 超类指定了可以干什么（如Comparable接口指定了比较功能）
  • 子类通过重写超类的抽象方法，来使java根据调用方法的对象来决定运行时该做什么

Comparator

Java提供了接口Comparator用来比较其他对象

语法：

1
2
3
4
public interface Comparator<T>{
    int compare(T o1, T o2);
    ...
}

Dog类中

1
2
3
4
5
6
7
public static class NameComparator implements Comparator<Dog> {

    @Override
    public int compare(Dog a, Dog b) {
        return a.name.compareTo(b.name);
    }
}

其中Dog.NameComparator()的数据类型为Comparator<Dog>

更现代的方式是使用lambda表达式定义comparator

1
2
Comparator<Dog> dc =(d1, d2) -> d1.name.compareTo(d2.name);
Dog maxNameDog = Collection.max(dogs,dc);

泛型函数

如何编写自己的方法

e.g. 实现一个方法，从数组中随机选择一个元素，并且接受各种类型

在这里，选择随机元素的方法是静态的，正确方式是让方法本身变为泛型，而非让类变为泛型

即声明了一个公共静态函数，用于处理类型T的对象

因为如果让整个类泛型化，你需要实例化那个类来获得泛型行为，但把该方法作为一个静态方法来看，并不需要实例化

1
2
3
4
5
6
7
publicc class RandomPicker{
    public static <T> T pickRandom(T[] x){
        Random random = new Random();
        int randomIndex = random.nextInt(x.length);
        return x[randomIndex];
    }
}

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 3 分钟

Interface & Inheritance

重载

Java允许多个方法拥有相同名称，只要他们的参数不同，这就是Java中的重载

重载的优缺点：

  • 代码基本一样
  • 对其余猎豹不适用，需要增加重载
  • 难维护

Hypernym and Hyponym

上位词与下位词

如Dog与poodle、malamute等狗的品种，前者为后者的上位词，后者为前者的下位词

Java中也有类似的概念，如我们可以把List作为SLList与ArrayList的上位词

在Java中表示这种属性：

  1. 给上位词定义一个引用属性
  2. 指定某些词为该上位词的下位词
  • 使用关键词interface来定义上位词
  • 使用关键词implements来定位下位词

接口内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package lec8;

public interface List61B<T> {
    public void addFirst(T x);

    public void addLast(T x);

    public T getFirst();

    public T getLast();

    public T get(int i);

    public T removeLast();

    public int size();
}

下位词部分修改：

1
2
3
4
public class ArrayList<T> implements List61B<T>
    ...
public class SLList<T> implements List61B<T>
    ...

这样在使用时我们只需要以该接口作为类型定义即可

重写

若你有一个子类实现接口，其方法与超类的签名相同，则可以在子类中重写来覆盖该方法

有相同名称而不同签名的方法叫做重写

在要重写的方法上面添加@override标签，当该方法不是一个重写方法时，该代码不会被编译

使用该标签的优点：

  • 主要优点：防止拼写错误，当标记了@override，但方法并没有被重写，就会爆CE
  • 提醒程序员方法来自于更高级的继承

Interface Inheritance

使用implements关键字来指定子类所具备的能力叫作接口继承

  • 接口：所有方法签名的列表
  • 继承：子类继承了来自超类的接口
  • 接口继承指定了子类可以做什么，而没有指定怎么做
  • 子类必须重写所有方法，否则会CE

Implementation Inheritance

接口继承只继承了签名，而没有继承实现

Java允许另一种继承：实现继承，使得子类可以继承签名与实现

使用default关键字来指定一个子类可以从接口继承的方法

1
2
3
4
5
6
7
// implementation inheritance
    default public void print(){
        for (int i = 0;i<size();i++){
            System.out.print(get(i)+" ");
        }
        System.out.println();
    }

（在接口文件中写默认的print方法，子类可以继承该方法）

1
2
3
4
5
6
7
8
9
// 重写接口中的print方法
   @Override
   public void print(){
       IntNode p = sentinel.next;
       while(p!=null){
           System.out.print(p.item+" ");
           p = p.next;
       }
   }

（针对特定子类，可以对default方法进行重写）

Abstract Data Type

抽象数据类型(ADT)仅由其操作定义，而不由其实现定义

发表于 分类于
本文字数： 1.6k 阅读时长 ≈ 3 分钟

ArrayList

Array中的随机访问

根据指定位置获取a数组中的元素是很快的，原因如下：

  • 与数组大小无关
  • 内存空间其实都是相同的大小

实现

添加删除元素

观察发现：

  • 元素个数可以用size表示
  • 在结尾添加元素时，添加的位置其实是第size位
  • 而获得结尾元素时，结尾元素位于size-1的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void addLast(int x){
        items[size] = x;
}

public int getLast(){
    return items[size-1];
}

public int get(int i){
    return items[i];
}

public int removeLast(){
    int itemToReturn = getLast();
    size -=1;
    return itemToReturn;
}

扩容

当列表满了以后，还想扩容并且增加容量，需要创建一个新数组，并调整size，将新元素加入数组

1
2
3
4
5
6
7
8
9
10
11
12
13
private void resize(int capacity){
        int[] a = new int[capacity];
        System.arraycopy(items, 0, a, 0, size);
        items = a;
}

public void addLast(int x){
    if (items.length == size){
        resize(size+1);
    }
    items[size] = x;
    size++;
}

这里将resize作为一个private方法，即调用addLast时，若发现空间不够，则会自动调用resize扩容，而不用手动调用

但每次扩容都会复制一份数组，扩容次数多了，创建的数组空间就会变大，导致性能下降

我们可以在每次扩容时在原大小基础上乘一个常量以一次性扩大大量空间，可以有效解决性能问题（Python的列表就是这样的原理）

但有时候不需要那么多空间，会造成空间浪费，故在发现利用率不够时，我们需要缩小数组尺寸：

  • 定义一个使用比率：\(R = \frac{\text{size}}{\text{items.length}}\)
  • 常用方案位当\(R<0.25\)时，将size减半

泛型化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package lec7;

public class ArrayList<T> {
    private T[] items;
    private int size;
    public ArrayList(){
        size = 0;
        items = (T[]) new Object[100];
    }

    private void resize(int capacity){
            T[] a = (T[])new Object[capacity];
            System.arraycopy(items, 0, a, 0, size);
            items = a;
    }

    public void addLast(T x){
        if (items.length == size){
            resize(size+1);
        }
        items[size] = x;
        size++;
    }

    public T getLast(){
        return items[size-1];
    }

    public T get(int i){
        return items[i];
    }

    public T removeLast(){
        T itemToReturn = getLast();
        items[size-1] = null;
        size -=1;
        return itemToReturn;
    }
}

有一个问题：在创建泛型T的数组引用时，会用到(T[]) new Object[100]这样的创建方法，即对类型进行了强制类型转换，IDEA会报warning：未检查的转换，此时可以忽略

在泛型的情况下，对于删除元素最好在减小size的同时将数组对应位置设置为null，这样垃圾回收器可以发现并回收内存，因为泛型导致了存入数组的数据类型大小可能会很大，从而浪费空间

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 4 分钟

Testing

Unit Tests

测试库

可以使用一些库中的语句进行测试，如：Truth库、JUnits库等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package lec6;
import static com.google.common.truth.Truth.assertThat;

public class TestSort {
    public static void testSort(){
        String[] input = {"bob", "luka", "C++"};
        String[] expected = {"bob", "C++", "luka"};
        Sort.sort(input);

        assertThat(input).isEqualTo(expected);
    }
    public static void main(String[] args){
        testSort();
    }
}

@test

使用标识符@test可以实现在文件中直接写入测试，而不需要在main函数中调用

IDEA中，使用该测试可以使用其自带的单元测试框架，可观列出测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package lec6;
import org.junit.jupiter.api.Test;

import static com.google.common.truth.Truth.assertThat;

public class TestSort {
    @Test
    public void testSort(){
        String[] input = {"bob", "luka", "C++"};
        String[] expected = {"bob", "C++", "luka"};
        Sort.sort(input);

        assertThat(input).isEqualTo(expected);
    }
}

Example: Building Selection Sort

原理：

  • 选择最小的元素
  • 移至表头
  • 对剩下n-1个元素进行选择排序

思路：

代码：测试部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package lec6;
import org.junit.jupiter.api.Test;

import static com.google.common.truth.Truth.assertThat;

public class TestSort {
    @Test
    public void testFindSmallest(){
        String[] input = {"bob", "luka", "c++"};
        int expected = 0;
        int actual = Sort.findSmallest(input, 0);
        assertThat(actual).isEqualTo(expected);
    }

    @Test
    public void testSwap(){
        String[] input = {"bob", "luka", "c++"};
        String[] expected = {"luka", "bob", "c++"};

        Sort.swap(input, 0, 1);
        assertThat(input).isEqualTo(expected);
    }
}

实现部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package lec6;

public class Sort {
    public static void sort(String[] x){
        sort(x, 0);
    }
    public static void sort(String[] x, int s){
        if (s == x.length){
            return ;
        }
        int smallest = findSmallest(x, s);
        swap(x, s, smallest);
        sort(x,s+1);

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

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

综上，测试可以增强代码的鲁棒性

  • 在单元测试中增加信心
  • 确保之后的改变不会破坏代码
  • 辅助代码的重构