Java接口实现插入和冒泡排序

0x01 要求

对整型数组排序的静态方法代码如下：

class SortedInts {

public static void newsort(int[] numbers, SortMethod s) {

​ s.sort(numbers);

​ for (int n : numbers) {

​ System.out.printf(“%d “, n);

​ }

​ System.out.println();

}

}

其中SortMethod是一个接口，请定义该接口，并定义2个类InsertSort和BubbleSort实现该接口，分别在这两个实现类中使用直接插入排序和冒泡排序实现 sort 方法。

对数组 a 进行直接插入排序的算法如下：

for (int i = 1; i < a.length; i++) {

​ int key = a[i];

​ int j = i - 1;

​ while (j >= 0 && a[j] > key) {

​ a[j+1] = a[j];

​ j–;

​ }

​ a[j+1] = key;

}

对数组 a 进行冒泡排序的算法如下：

for (int i = 0; i < a.length - 1; i++) {

​ for (int j = 0; j < a.length - 1 - i; j++) {

​ if (a[j] > a[j + 1]) {

​ int temp;

​ temp = a[j];

​ a[j] = a[j + 1];

​ a[j + 1] = temp;

​ }

​ }

}

然后在main方法中输入一个长度为8的数组，分别用两个实现类的对象作为实际参数调用newsort方法进行排序。例如：

public class Main {

public static void main(String[] args) {

​ int[] ns = new int[8];

​ …… // 输入数组

​ InsertSort is = new InsertSort();

​ SortedInts.newsort(ns, is);

​ BubbleSort bs = new BubbleSort();

​ SortedInts.newsort(ns, bs);

}

}

输入样例：

9 3 5 2 1 7 23 8

输出样例：

1 2 3 5 7 8 9 23

1 2 3 5 7 8 9 23

提示：本次上机需要定义1个接口，4个类。必须将类 Main 定义为 public 并放在最前面，其他类和接口不能定义为 public。类 SortedInts 的代码不能更改。

0x02 代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int[] ns = new int[8];
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < ns.length; i++) {
            ns[i] = scanner.nextInt();
        }
        InsertSort is = new InsertSort();
        SortedInts.newsort(ns, is);

        BubbleSort bs = new BubbleSort();
        SortedInts.newsort(ns, bs);
    }
}
interface SortMethod {

    void sort(int[] numbers);
}

class SortedInts {
    public static void newsort(int[] numbers, SortMethod s) {

        s.sort(numbers);

        for (int n : numbers) {

            System.out.printf("%d ", n);

        }

        System.out.println();

    }
}

class InsertSort implements SortMethod {

    @Override
    public void sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }
}

class BubbleSort implements SortMethod {

    @Override
    public void sort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int temp;
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }
}