java - 使用可比较的类进行选择排序

Question

这个问题已经有答案了:

What is a NullPointerException, and how do I fix it? (12 个回答)

已关闭 4 年前。

我使用 Comparable 类、文件扫描器进行了 java 选择排序。

在此代码中，我们获取 txt 文件的名称并将所有单词存储在 String[] 列表中，并显示索引和存储的单词。

最后，我们使用选择排序对此 String[] 列表进行排序，并检查花费了多少时间。但有一些错误代码。

这是一个 AbstractSort 类

abstract class AbstractSort
{
    public static void sort(Comparable[] a) { };

    protected static boolean less(Comparable v, Comparable w )
    {
        return v.compareTo(w) < 0; // This Line is Error
    }

    protected static void exch(Comparable[] a, int i, int j)
    {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    protected static void show(Comparable[] a)
    {
        for(int i = 0; i < a.length; i++)
            System.out.println(a[i] + " ");
        System.out.println();
    }

    protected static boolean isSorted(Comparable[] a)
    {
        for(int i = 1; i < a.length; i++)
        {
            if(less(a[i], a[i - 1])) // This Line is also Error
                return false;
        }
        return true;
    }
}

这是一个扩展了 AbstractSort 类的选择排序类

class Selection extends AbstractSort {
    public static void sort(Comparable[] a) {
        int n = a.length;

        for(int i = 0; i < n - 1; i++) {
            int min = i;

            for(int j = i + 1; j < n; j++) {
                if(less(a[j], a[min]))
                    min = j;
            }
            exch(a, i, min);
        }
        assert isSorted(a);
    };
}

这是主要功能

public class HW1{
    static String[] resize(int idx, String[] arr) {
        String[] temp = new String[idx * 2];

        for(int i = 0; i < idx; i++)
            temp[i] = arr[i];

        return temp;
    }

    public static void main(String args[]) {
        int INIT_LEN = 10000;
        long start, end, time;
        String[] list = new String[INIT_LEN];
        Scanner sc = new Scanner(System.in);
        int idx = 0;

        try {
            System.out.println("File Name?");
            String src = sc.nextLine();
            sc = new Scanner(new FileInputStream(src));

            while(sc.hasNext()) {
                String word = sc.next().toString();

                if(idx == list.length)
                    list = resize(idx, list);

                list[idx++] = word;
            }
            System.out.println("1. Total Word = " + idx);
            for(int i = 0; i < idx; i++)
                System.out.println(i + "idx:" + list[i]);

            start = System.currentTimeMillis();
            Selection.sort(list); // This Line is also Error            
            end = System.currentTimeMillis();
            time = end - start;
            System.out.println("2. Selection Sorted? = true, Time = " + time + "ms");
        }catch (FileNotFoundException fnfe) {
            System.out.println("No File");
        }catch (IOException ioe) {
            System.out.println("Can't Read File");
        }
    }
}

当我运行此代码时，我可以看到所有单词都存储在 int String[] 列表中，但也有错误代码在一起。

Exception in thread "main" java.lang.NullPointerException
at AbstractSort.less(HW1.java:8)
at Selection.sort(HW1.java:40)
at HW1.main(HW1.java:84)

我不知道为什么会出现这个错误代码...

Answer 1

当您在 main 中调用 Selection.sort(list) 时，list 的长度似乎为 10000。

每个元素默认为 null。

因此，如果您用三个单词阅读，您的列表将如下所示:

word1,word2,word3,null,null,null......null

快速破解，这样您就不需要调整数组大小 - 尝试在 Selection::sort 中创建内部循环:

    for (int j = i + 1; j < n; j++) {
        if (a[j] == null) {
            break;
        }

        if (less(a[j], a[min]))
            min = j;
    }

或者 - 在处理之前适当调整数组大小。

或者 - 如果您绝对必须使用数组，则使用 ArrayList 将单词推送到然后转换为数组。