排序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

要快速排序列表，请尝试

Collections.sort(List list);

或者

Collections.sort(List list,Comparator c)

Answer 2

如果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()的实现。它只是在给定的标记上交换元素