Java быстрый способ добавления и сортировки списков

Question

У меня есть следующий код для сортировки ходов в настольной игре. Она смотрит на меня, как это может быть оптимизированная:

private List<Move> sortMoves(List<Move> moves, int depth) 
    { 
     List<Move> sorted = new ArrayList<Move>(); 

     if (moves.size() == 0) 
      return sorted; 

     List<Move> primary = new ArrayList<Move>(); 
     List<Move> rest = new ArrayList<Move>(); 

     for(int i = 0; i < moves.size(); i++) 
     { 
      if (killers.primary[depth] != null && moves.get(i).equals(killers.primary[depth])) 
       primary.add(moves.get(i));   

      else 
       rest.add(moves.get(i)); 
     } 

     sorted.addAll(primary); 
     sorted.addAll(rest); 

     return sorted; 
    } 

Есть лучше и более эффективный способ выше (т.е. пересекаются два списка и возвращает отсортированный список.)?

Примечание. Целью этой функции является удаление перемещений (первичных) убийцы, найденных в списке перемещений, а затем возврат нового списка с перемещением убийцы, а затем список того, что находится в списке исходных перемещений.

Answer 1

Если moves не слишком большая текущая реализация выглядит нормально. Его сложность - O (n). Только здесь сложность пространства из-за трех дополнительных списков, а именно. primary, rest и sorted.

С помощью Collections.sort(List<T> list, Comparator<? super T> c) вы можете сэкономить немного места.

Это не использует дополнительное пространство, но имеет временную сложность O (nlog (n)). Кроме того, его реализация краткая.

ОБНОВЛЕНИЕ: Следующее - это еще одно элегантное решение без дополнительной сложности пространства и сложности времени O (n).

private void sortMoves(final List<Move> moves, final int depth) 
{ 

    int i = 0; 
    int j = moves.size() - 1; 

    while(i < j) { 

     while(equalsKillersPrimary(moves.get(i), depth)) 
      i++; 

     while(!equalsKillersPrimary(moves.get(j), depth)) 
      j--; 

     swap(moves, i, j); 
    } 
} 

private boolean equalsKillersPrimary(Move move, int depth) { 

    return killers.primary[depth] != null && move.equals(killers.primary[depth]); 
} 

Я оставил из реализации swap() для краткости. Он просто меняет элементы на данные знаки.

Answer 2

Чтобы отсортировать список быстро попробовать

Collections.sort(List list);

или

Collections.sort(List list,Comparator c)