首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >插入排序算法对String[]排序

问插入排序算法对String[]排序
EN

Stack Overflow用户
提问于 2018-03-08 19:33:19
回答 3查看 6K关注 0票数 4

我有一个关于使用String[]插入排序算法排序数组的问题。我确实意识到,我的问题很可能很容易用不同的算法来完成,但我正在尝试首先学习如何处理这个问题。

基本上,我试图使用该算法对字符串数组进行排序。为此,我比较了字符串数组中的char值,因此我能够使用标准的>和==操作符,因为通过这种方式比较值(就像您与ints一样)自然非常简单。

我有一个我正在处理的解决方案,根据每个数组索引中找到的前2个字符值对字符串数组进行排序,但我开始意识到,我所做的并不是一个非常健壮的解决方案,因为数组中的字符串可以很容易地具有“更长”的值,这不会使我对具有类似值的较长字符串的排序非常准确。

考虑到这一点,有人能建议我如何动态地比较从各种字符串创建的char值,以排序原始的字符串值(与我下面编写的代码一起使用)吗?

所以.

A: ...I不会遇到比较不同大小字符串值的NullPointer异常

B: ...every char值与字符串进行比较,无论大小如何,这样我就可以准确地对原始字符串数组进行排序)

代码语言:javascript
复制
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 char检查而按预期工作的示例数组:

代码语言:javascript
复制
String[] arr = {"zz", "bb", "cb", "ba","za", "zb", "cz", "ab","aa"};

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

代码语言:javascript
复制
String[] arr = {"bbz", "bba", "abz","abc"};

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

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2018-03-08 21:50:57

如果您真的想使用chars比较来进行比较,最好的方法是创建单独的方法来比较这些String。

在isSmallerThan()中,循环增量currentIndex,直到它对任何参数都没有超出限制,和直到字符相同为止。然后,如果语句检查currentIndex是否超出了至少一个字符串的范围,那么它可以发生在输入例如:(aaa,aa),(aaabb,aaa),(aaa,aaa)。那么,我们必须通过长度比较来决定什么比较小。

对于插入排序算法,我们不关心(aaa,aaa)是相同的字符串,我们只需返回这是false,它就会中断sortArrayOfStrings方法中的while循环。

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

代码语言:javascript
复制
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);
}

但是,正如人们前面所说的,最好使用字符串库中的compareTo或compareToIgnoreCase方法。为了完成这项工作,将 isSmallerThan(value,arrayindex-1) 改为arrayindex-1。

票数 1
EN

Stack Overflow用户

发布于 2018-03-08 19:43:01

尝试使用String.CompareTo(String s)方法。它非常类似于您一直使用的比较运算符,除非它将计算为一个整数。

代码语言:javascript
复制
String str1 = "Cat";
String str2 = "Dog"; 

int sCompare = str1.CompareTo(str2);
  1. 如果sCompare == 0,则字符串是“相同的”。
  2. 如果sCompare > 0,则str1 > str2 (字母顺序)
  3. 如果sCompare < 0,则str2 > str1 (字母顺序)

编辑:

为了清楚起见,在上述示例中,sCompare将计算为负值。

票数 2
EN

Stack Overflow用户

发布于 2018-03-08 20:05:21

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

代码语言:javascript
复制
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;
    }
}

示例测试:

代码语言:javascript
复制
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"});
    }
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/49181083

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档