插入排序算法对 String[] 进行排序

Question

我有一个关于在 Java 中使用 插入排序算法 对 String[] 数组进行排序的问题。我确实意识到我的问题可能更容易使用不同的算法来完成，但我正在尝试先了解一切如何与这个算法一起工作。

基本上，我正在尝试使用该算法对字符串数组进行排序。为此，我比较了字符串数组中的 char 值，因此我能够使用标准的 > 和 == 运算符，因为以这种方式比较值（就像使用 ints 一样）自然非常简单。

我有一个正在使用的解决方案，我通过在每个数组索引处找到的前 2 个字符值对字符串数组进行排序，但我开始意识到我所做的并不是一个非常可靠的解决方案，因为数组中的字符串很容易具有彼此 'longer' 的值，这不会使我对具有相似值的较长字符串的排序非常准确。

考虑到这一点，有人可以建议（连同我在下面编写的代码）我将如何动态比较从各种 创建的 char 值strings 来排序原来的 string 值？

所以...

A: ...我不运行比较来自不同大小字符串的值的 NullPointer 异常

B: ...每个字符值都是从字符串中比较的，不管大小，所以我可以准确地对原始字符串数组进行排序）

public String[] sortArrayOfStrings(String[] array){
        //NOT COMPLETE, ONLY SORTS BASED ON FIRST & SECOND CHAR OF STRING INDEX
        //BASED ON INSERTION SORT ALGORITHM
        int length = array.length;

        String value;
        int index;

        for(int a = 1; a < length; a++){
            char currentCharValue = array[a].charAt(0);//USE '[a]' not '[index]'
            value = array[a];
            index = a;

            if(currentCharValue == array[a - 1].charAt(0) ){//IF FIRST CHAR == PREVIOUS
                while (index > 0 && array[index - 1].charAt(1) > array[index].charAt(1)){
                    array[index] = array[index - 1];
                    index = index - 1;
                }
            }else{

                while (index > 0 && array[index - 1].charAt(0) > currentCharValue){
                    array[index] = array[index - 1];
                    index = index - 1;
                }
            }
            array[index] = value;
        }

        return array;
}

由于 2 个字符检查而按预期工作的示例数组：

String[] arr = {"zz", "bb", "cb", "ba","za", "zb", "cz", "ab","aa"};

由于额外字符而无法正确排序的示例数组：

String[] arr = {"bbz", "bba", "abz","abc"};

我知道上面的数组由于 2 个字符的硬编码 'check' 而无法正确排序，我试图消除对检查进行硬编码的需要。

Answer 1

尝试使用 String.CompareTo(String s) 方法。它很像您一直在使用的比较运算符，只是它的计算结果是一个整数。

String str1 = "Cat";
String str2 = "Dog"; 

int sCompare = str1.CompareTo(str2);

如果 sCompare == 0，则字符串是 "same"
如果 sCompare > 0，则 str1 > str2（按字母顺序）
如果 sCompare < 0，则 str2 > str1（按字母顺序）

编辑：

为清楚起见，在上述示例中，sCompare 的计算结果为负值。

Answer 2

使用compareTo()方法，insertion sort算法的实现如下所示：

class InsertionSorter {

    public String[] sortArrayOfStrings(String[] array) {
        for (int i = 1; i < array.length; i++) {
            String element = array[i];
            int j;
            for (j = i - 1; j >= 0 && element.compareTo(array[j]) <= 0; j--)
                array[j + 1] = array[j];

            array[j + 1] = element;
        }
        return array;
    }
}

示例测试：

public class InsertionSorterTest {

    @Test
    public void shouldSortTwoLetterWords() {
        String[] arr = {"zz", "bb", "cb", "ba", "za", "zb", "cz", "ab", "aa"};
        String[] sortedArray = new InsertionSorter().sortArrayOfStrings(arr);
        Assert.assertEquals(sortedArray, new String[]{"aa", "ab", "ba", "bb", "cb", "cz", "za", "zb", "zz"});
    }

    @Test
    public void shouldSortLongerWords() {
        String[] arr = {"bbz", "bba", "abz", "abc"};
        String[] sortedArray = new InsertionSorter().sortArrayOfStrings(arr);
        Assert.assertEquals(sortedArray, new String[]{"abc", "abz", "bba", "bbz"});
    }
}

Answer 3

如果你真的想用字符比较来做，最好的方法是创建单独的方法来比较这些字符串。

在 isSmallerThan() 内部 while 循环递增 currentIndex 直到它不超出任何参数的范围和直到字符相同。然后 if 语句检查 currentIndex 是否超出至少一个字符串的范围，它可能发生在输入中，例如：（aaaaa，aa）， (aaabb, aaa), （aaa，aaa）。那么我们必须通过长度比较来决定什么是更小的。

对于插入排序算法，我们不关心 (aaa, aaa) 是相同的字符串，我们可以 return 这是假的，它会中断 sortArrayOfStrings 方法中的 while 循环.

否则我们知道字符是不同的，我们只是比较它们。

String[] sortArrayOfStrings(String[] array){
    int length = array.length;
    String value;
    int index;

    for(int a = 1; a < length; a++){
        value = array[a];
        index = a;
        while(index > 0 && isSmallerThan(value, array[index-1])) {
            array[index] = array[index - 1];
            --index;
        }
        array[index] = value;
    }
    return array;
}

boolean isSmallerThan(String left, String right) {
    int curIndex = 0;
    while (curIndex < left.length()
            && curIndex < right.length()
            && left.charAt(curIndex) == right.charAt(curIndex)){
        ++curIndex;
    }

    if (curIndex == left.length() || curIndex == right.length())
        return left.length() < right.length();
    else
        return left.charAt(curIndex) < right.charAt(curIndex);
}

但正如人们在我之前所说的那样，最好使用 String 库中的 compareTo or compareToIgnoreCase 方法。只需更改即可完成这项工作 isSmallerThan（值，数组[index-1]）进入 array[index-1].compareToIgnoreCase(value) > 0.

插入排序算法对 String[] 进行排序

Insertion Sort Algorithm to Sort String[]

java

arrays

sorting

algorithm

insertion-sort