根據長度對字符串數組進行排序

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