我有以下代码用于对棋盘游戏中的移动进行排序。我觉得它可以被高度优化：
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; }有没有更好的、更有效的方法来实现上述功能（例如，交叉两个列表并返回一个排序后的列表）？
注意：该函数的目标是从移动列表中移除杀手移动（primary），然后返回一个新列表，其中杀手移动在前，其余的移动在后。
回答：
如果你的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(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()的实现。它只是交换给定索引上的元素。
