java使用InsertionSort算法对包含空元素的字符串数组进行排序

Question

这里提出的算法具有O（n^2）（插入排序）的复杂性。不过，由于String数组中有null个元素，因此该算法会获得一个NullPointerException。如何让我的算法对包含空元素的数组进行排序？算法如下：

private void sortFlowers(String flowerPack[]) {
    // TODO: Sort the flowers in the pack (No need to display
    // them here) - Use Selection or Insertion sorts
    // NOTE: Special care is needed when dealing with strings!
    // research the compareTo() method with strings

    String key;

    for (int j = 1; j < flowerPack.length; j++) { //the condition has changed
        key = flowerPack[j];
        int i = j - 1;

        while (i >= 0) {
            if (key.compareTo(flowerPack[i]) > 0) { //here too
                break;
            }

            flowerPack[i + 1] = flowerPack[i];

            i--;
        }

        flowerPack[i + 1] = key;
    }
}

Answer 1

compareTo()是Comparable接口的一部分。它没有将null与任何东西进行比较的定义行为。它实际上不可能有这种行为，因为a.compareTo(b)和b.compareTo(a)需要一致。你可以：

1）实现一个定制的Comparator，它知道如何比较空值，然后用myComparator.compare(key, flowerPack[i])替换key.compareTo(flowerPack[i])

2 Not use nulls

3）因为这看起来像是家庭作业，所以重写whilelook中的位，如果和flowerPace[i]都不为空，则只使用compareTo()。如果其中一个（或两个）为空，则需要特殊情况

Answer 2

如果key可以为空，则应更改此条件：

key.compareTo(flowerPack[i]) > 0

比如：

compareKeys(key, flowerPack[i]) > 0

然后添加一个null-safe检查，比如：

private int compareKeys(final String first, final String second) {
    if (first == null || second == null) {
        return 0; // TODO: 0, here?
    } else {
        return first.compareTo(second);
    }
}