按组对列表进行排序的效率如何？

Question

我需要通过一些给定的“块”或“组”元素对给定的排序列表进行分组。例如：给定一个列表：[A, B, C, D, E, F, G, H, I, J]和团体[A, C, D][F, E][J, H, I]结果应该是[A, C, D, B, F, E, G, J, H, I]元素块不能与非组元素混合。块应该具有相同的顺序。列表的其他元素应保持其顺序。我已经找到了解决方案。但这不是您将看到的最有效的代码。我也在使用java 6 ...

Answer 1

从您提交的代码中，我无法弄清楚您的算法是如何完全工作的。

我可以编写另一个算法来完成这项任务。

1. 标记每个组的第一个元素

   [A,C,D] -> A

2. list(to_be_sorted)从未标记的组中的所有元素中删除

   [A,C,D] -> remove [C,D]

3. 对列表执行排序

   result ([A,B,F,G,J])

4. 根据 Mark 放置移除的元素

Initial Sorted List [A,B,F,G,J]

A->add [C,D]

List is [A,C,D,B,F,G,J]

B->as it is

F->add [E]

List is [A,C,D,B,F,E,G,J]

G->as it is

J->add [H,I]

Final Sorted List [A,C,D,B,F,E,G,J,H,I]

时间复杂度与排序算法相同

Answer 2

根据您的定义，合并给定列表和“组”（数组）中的结果的条件并不完全清楚。但是，这是使用断言根据您的要求的解决方案

“您希望列表的第一个元素不包含在组之间插入的任何组中......”

public class MergeArrays {

    private static final List<String> FIRST = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E", "F", "G", "H", "I", "J"));

    private static final List<String> SECOND = new ArrayList<>(Arrays.asList("A", "C", "D"));

    private static final List<String> THIRD = new ArrayList<>(Arrays.asList("F", "E"));

    private static final List<String> FOURTH = new ArrayList<>(Arrays.asList("J", "H", "I"));

    public static List<String> merge(List<String> source, List<String>... lists) {

        List<String> result = new ArrayList<>();

        for (List<String> list : lists) {

            for (String value : list) {

                source.remove(value);

            }

        }

        for (List<String> list : lists) {

            String value = null;

            if (source.size() > 0) {

                value = source.get(0);

                source.remove(0);

            }

            result.addAll(merge(value, list));

        }

        return result;

    }

    public static List<String> merge(String value, List<String> list) {

        List<String> result = new ArrayList<>(list);

        if (value != null) {

            result.add(value);

        }

        return result;

    }

    public static void main(String[] args) {

        List<String> result = merge(FIRST, SECOND, THIRD, FOURTH);

        System.out.println(result);

    }

}

//结果

[A, C, D, B, F, E, G, J, H, I]