根据长度对字符串数组进行排序

Question

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

例如

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

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

我想到的另一种方法是 - 使用TreeMap将每个字符串及其长度存储为值（假定字符串在给定数组中是唯一的）。然后根据它的值对它进行排序。运行时间为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; 
} 

Answer 1

有很多更好的方法来做到这一点。对于插入排序，我们正在谈论O（n^2）。一个好得多的排序算法就像mergesort（更好的最坏情况）或quicksort（平均更好）。由于这是基于长度的排序，因此可以采取多种方法。你将不得不计算每个字符串的长度。你可以做的是创建一个int数组，它们对应于相同索引处的单词长度。然后，您可以在整数上运行mergesort或quicksort，并确保同时翻转字符串。最终结果将是一个非递减的整数和非递减的字符串数组。

Answer 2

如果你可以使用一个集合，而不是（如一个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(); 
    } 
} 

Answer 3

试试这个。

你输入

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"} 

Answer 4

您可以使用比较如下：

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()); 

Answer 5

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(); 
     } 
    }); 

Answer 6

公共类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]); 
    } 

} 

}

Answer 7

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);