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)可以节省一些空间复杂性。

private void sortMoves(final List<Move> moves, final int depth) 
{ 
    Collections.sort(moves, new Comparator<Move>() { 
     @Override 
     public int compare(Move o1, Move o2) { 

      if(killers.primary[depth] != null && moves.get(i).equals(killers.primary[depth])) { 

       return 0; 
      } else { 

       return 1; 
      } 
     } 
    });  
} 

这不使用任何额外的空间，但有时间复杂度O（n日志（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)