Сортировка списка дженериков в Java?

Question

Я пытаюсь реализовать сортировку для Generics в Java. Вот это абстрактный класс Function (T мой «ключ» для сортировки):

public abstract class Function<T extends Comparable<T>, S> { 

    abstract public T compute(S o); 
} 

Вот класс для наложения, метод которого «применить» сортирует список в соответствии с результатом «вычислений»:

import java.util.ArrayList; 
import java.util.Iterator; 

public class Applier<T extends Comparable<T>, S> { 

    ArrayList<S> apply(ArrayList<S> input, Function<T, S> function) { 
     ArrayList<T> output = new ArrayList<>(); 
     for(Iterator<S> it = input.iterator(); it.hasNext();){ 
      output.add(function.compute(it.next())); 
     } 
     T tmpTi, tmpTj; 
     S tmpSi, tmpSj; 
     for(int i=0; i<input.size(); i++) { 
      for(int j=i+1; j<input.size(); j++) { 
       if(output.get(i).compareTo(output.get(j))>0) { 
        tmpTi = output.get(i); 
        tmpTj = output.get(j); 
        output.remove(j); 
        output.remove(i); 
        output.add(i, tmpTi); 
        output.add(i, tmpTj); 

        tmpSi = input.get(i); 
        tmpSj = input.get(j); 
        input.remove(j); 
        input.remove(i); 
        input.add(i, tmpSj); 
        input.add(j, tmpSi); 
       } 
      } 
     } 
     return input; 
    } 

} 

Мой вопрос: есть ли более разумный способ сделать эту сортировку, может быть, не с помощью пузырьков? Здесь также основной класс:

public static void main(String[] args) { 
    Applier a = new Applier<>(); 
    StringLength strlen = new StringLength(); 

    ArrayList<String> array = new ArrayList<>(); 

    array.add("Hola"); 
    array.add("Man"); 
    array.add("randomstufff"); 
    array.add("Zerrone"); 
    array.add("Info3a"); 

    System.out.println("Order by length"); 
    System.out.print("before: "); 
    System.out.println(array); 
    a.apply(array, strlen); //works on original object 
    System.out.print("After: "); 
    System.out.println(array); 

Answer 1

Обратите внимание, что есть ошибка в том, как вы обменим элементы в Bubble Сортировка: При повторной вставке элементов в output, вы неуместны i и j. Кроме того, вместо удаления и повторной установки элементов просто используйте set(index, element), чтобы перезаписать предыдущую запись.

Кроме того, вместо использования двух списков и сохранения этих списков лучше всего использовать Map.

public static class Applier<T extends Comparable<T>, S> { 
    ArrayList<S> apply(ArrayList<S> input, Function<T, S> function) { 
     Map<S, T> compareBy = new HashMap<>(); 
     for (S s : input) { 
      compareBy.put(s, function.compute(s)); 
     } 
     for(int i=0; i<input.size(); i++) { 
      for(int j=i+1; j<input.size(); j++) { 
       if (compareBy.get(input.get(i)).compareTo(compareBy.get(input.get(j))) > 0) { 
        S tmpS = input.get(j); 
        input.set(j, input.get(i)); 
        input.set(i, tmpS); 
       } 
      } 
     } 
     return input; 
    } 
} 

И, конечно, сортировка уже реализована на Java. Поэтому, помимо обучения методу кодирования, вы всегда должны использовать встроенные функции. В Java 8, это только одна строка:

Collections.sort(array, Comparator.comparing(String::length)); 

Однако следует отметить, что Comparator.comparing будет вызывать функцию компаратора для каждого парного сравнения (т.е. порядка 2nlogn раз для алгоритма приличной сортировки). Если эта функция является вычислительной очень дорогой, вы можете захотеть ее кешировать самостоятельно, используя Map.

Map<String, Integer> compareBy = array.stream().collect(Collectors.toMap(s -> s, s -> s.length())); 
Collections.sort(array, Comparator.comparing((String s) -> compareBy.get(s))); 

Answer 2

В принципе, вы хотите отсортировать массив на основе другого массива. Вы сможете использовать Collections.sort, если вы представите объект-оболочку, содержащий как значения, так и результаты функции, и отсортируйте их.

Вот решение с использованием Java 8 потокового API:

public class Applier<T extends Comparable<T>, S> { 

    static class Wrapper<T extends Comparable<T>,S> implements Comparable<Wrapper<T,S>> { 
     T key; 
     S value; 
     Wrapper(S s, Function<T, S> function) { 
      this.key = function.compute(s); 
      this.value = s; 
     } 
     public int compareTo(Wrapper<T,S> that) { 
      return key.compareTo(that.key); 
     } 
    } 
    ArrayList<S> apply(ArrayList<S> input, Function<T, S> function) { 
     S[] sorted = (S[]) IntStream.range(0, input.size()) 
      .mapToObj(i -> new Wrapper<T,S>(input.get(i), function)) 
      .sorted() 
      .map(b -> b.value).toArray(); 
     input.clear(); 
     input.addAll(Arrays.asList(sorted)); 
     return input; 
    } 

}