Сортировка массива строк по длине

Question

Вопрос заключается в сортировке массива строк, основанных на длине строк.

Например

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

Я сделал это с помощью сортировки вставками (используя длину строк, вместо самих строк). Мой вопрос: есть ли лучший способ сделать это?

Альтернатива, о которой я думал, - использовать TreeMap для хранения каждой строки и ее длины как значения (предположим, что строки уникальны в данном массиве). Затем сортируйте его на основе его значений. Время работы будет O(nlogn), а пространственная сложность - O(n). Считаете ли вы, что это лучший подход?

EDIT: Извините, что не упомянул об этом раньше - я хочу сделать это, не используя 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 в ints и не задумываться о том, чтобы перевернуть строки в одно и то же время. Конечным результатом будет не уменьшающийся массив ints и неубывающий массив строк.

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