4

问题是根据字符串的长度对字符串数组进行排序。

例如

input = {"cat", "star", "act", "gid", "arts", "dog", "rats"}  
output = {"cat", "act", "gid", "dog", "star", "arts", "rats"}

我使用插入排序（使用字符串的长度而不是字符串本身）来做到这一点。我的问题：有更好的方法吗？

我想到的另一种选择是 - 使用 aTreeMap将每个字符串及其长度存储为值（假设字符串在给定数组中是唯一的）。然后根据其值对其进行排序。运行时间为O(nlogn)，空间复杂度为O(n)。您认为这是更好的方法吗？

编辑：很抱歉之前没有提到这一点 - 我想在不使用Arrays.sort()或自定义比较器的情况下执行此操作。

插入排序的代码示例：

public static String[] insertionSort(String[] arr) {
    for(int i=1;i<arr.length;i++) {
        int j = 0;
        for(;j<i;j++) {
            if(arr[j].length() > arr[j+1].length()) {
                String temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}
4

8 回答 8

5

试试这个。

您的意见

String[] input = {"cat", "star", "act", "gid", "arts", "dog", "rats"};

你的比较器

class SampleComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return new Integer(o1.length()).compareTo(o2.length());
   }
}

你的排序

Collections.sort(in, new SampleComparator());

你的输出

output = {"cat", "act", "gid", "dog", "star", "arts", "rats"}
于 2013-10-26T05:42:20.930 回答
3 
    String[] str={"umbrella","apple", "baby", "cat","rat","obnoxious"};
    Arrays.sort(str, new Comparator<String>() {

        @Override
        public int compare(String o1, String o2) {
            return o1.length()-o2.length();
        }
    });
于 2013-10-26T05:46:00.853 回答
2

有许多更好的方法可以做到这一点。对于插入排序，我们说的是 O (n^2)。一个更好的排序算法将是类似于合并排序（更好的最坏情况）或快速排序（平均更好）。由于这是基于长度的排序，因此可以采用多种方法。您将不得不在某个时候计算每个字符串的长度。您可以做的是创建一个整数数组，这些整数对应于同一索引处单词的长度。然后您可以对整数运行合并排序或快速排序，并确保同时翻转字符串。最终结果将是一个非递减的整数数组和一个非递减的字符串数组。

于 2013-10-26T05:35:44.527 回答
0

如果您可以使用 Collection 代替（例如 ArrayList 在您的情况下会很棒），您可以使用 Collections.sort 为您完成工作。它又快又干净。请参阅：java.util.List

您将需要一个自定义比较器。

public class StringComparator implements Comparator<String>
{
    @Override
    public int compare(String s1, String s2) 
    {
        return s1.length()-s2.length();
    }
}
于 2013-10-26T05:34:41.683 回答
0

您可以使用比较器，如下所示：

public static class OrderStringByLength implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        int c = s1.length() - s2.length();
        return (c != 0) ? c : s1.compareTo(s2);
    }
}

然后您可以按如下方式对数组进行排序：

Arrays.sort(input, new OrderStringByLength());
于 2013-10-26T05:44:56.723 回答
0

公共类 SortArrayOfStringOnLength {

public static void main(String[] args) {
    String[] strArray = new String[] { "cat", "star", "act", "gid", "arts",
            "dog", "rats" };

    printArray(strArray);

    String[] outputArray = getSortedArray(strArray);
    printArray(outputArray);

}

private static String[] getSortedArray(String[] strArray) {

    Map map = new TreeMap();
    for (int i = 0; i < strArray.length; i++) {
        String str = strArray[i];
        if (map.containsKey(str.length())) {
            List list = (List) map.get(str.length());
            list.add(str);
            map.put(str.length(), list);
        } else {
            List list = new ArrayList();
            list.add(str);
            map.put(str.length(), list);
        }
    }

    Set set = map.keySet();

    Iterator itr = set.iterator();
    int outArrayIndex = 0;
    String[] outputArray = new String[strArray.length];
    while (itr.hasNext()) {

        Integer intValue = (Integer) itr.next();
        List list = (List) map.get(intValue);
        for (int i = 0; i < list.size(); i++) {
            outputArray[outArrayIndex] = (String) list.get(i);
            outArrayIndex++;
        }
    }

    return outputArray;
}

private static void printArray(String[] strArray) {

    System.out.println("*****************");
    for (int i = 0; i < strArray.length; i++) {
        System.out.println(strArray[i]);
    }

}

}

于 2016-03-19T05:41:38.270 回答
0 
    String[] strArray = new String[] { "cat", "star", "act", "gid", "arts",
            "dog", "rats" };
    List<String> strings = Arrays.asList(strArray);
    strings.sort((s1, s2) -> Math.abs(s1.length()) - Math.abs(s2.length()));
    System.out.println(strings);
于 2016-03-19T06:13:03.057 回答
0

问题：根据字符串长度对字符串数组进行排序。我们可以在 Java 8 中使用 Streams

public class SortStringsAccordingToLength {

    public static void main(String[] args) {
        List<String> sampleStrings = Arrays.asList("Protijayi", "Gina", "Gini", "Soudipta");

        System.out.println(lengthSortUsingSorted1(sampleStrings));

        System.out.println(lengthSortUsingSorted2(sampleStrings));
        System.out.println(lengthSortUsingSorted3(sampleStrings));
        System.out.println(lengthSortUsingSorted4(sampleStrings));
    }

    private static List<String> lengthSortUsingSorted4(List<String> list) {

        list.sort((a, b) -> Long.compare(a.length(), b.length()));
        System.out.println(list);

        return list;
    }

    private static List<String> lengthSortUsingSorted3(List<String> sampleStrings) {
        List<String> list1 = sampleStrings.stream()
                .sorted(Comparator.comparingLong(String::length).thenComparing(Comparator.naturalOrder()))
                .collect(Collectors.toList());
        return list1;
    }

    private static List<String> lengthSortUsingSorted2(List<String> sampleStrings) {
        List<String> list1 = sampleStrings.stream().sorted(Comparator.comparingInt(String::length))
                .collect(Collectors.toList());
        return list1;
    }

    public static List<String> lengthSortUsingSorted1(List<String> sampleStrings) {
        List<String> list1 = sampleStrings.stream().sorted((s1, s2) -> s1.length() - s2.length())
                .collect(Collectors.toList());
        return list1;
    }

}
于 2019-03-21T06:48:43.587 回答