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)