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

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

从您提交的代码中，我无法弄清楚您的算法是如何完全工作的。我可以编写另一个算法来完成这项任务。标记每个组的第一个元素[A,C,D] -> Alist(to_be_sorted)从未标记的组中的所有元素中删除[A,C,D] -> remove [C,D]对列表执行排序result ([A,B,F,G,J])根据 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 isF->add [E]List is [A,C,D,B,F,E,G,J]G->as it isJ->add [H,I]Final Sorted List [A,C,D,B,F,E,G,J,H,I]时间复杂度与排序算法相同

Answer 2

根据您的定义，合并给定列表和“组”（数组）中的结果的条件并不完全清楚。但是，这是使用断言根据您的要求的解决方案“您希望列表的第一个元素不包含在组之间插入的任何组中......”public class MergeArrays {&nbsp; &nbsp; private static final List<String> FIRST = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E", "F", "G", "H", "I", "J"));&nbsp; &nbsp; private static final List<String> SECOND = new ArrayList<>(Arrays.asList("A", "C", "D"));&nbsp; &nbsp; private static final List<String> THIRD = new ArrayList<>(Arrays.asList("F", "E"));&nbsp; &nbsp; private static final List<String> FOURTH = new ArrayList<>(Arrays.asList("J", "H", "I"));&nbsp; &nbsp; public static List<String> merge(List<String> source, List<String>... lists) {&nbsp; &nbsp; &nbsp; &nbsp; List<String> result = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; for (List<String> list : lists) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (String value : list) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; source.remove(value);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for (List<String> list : lists) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String value = null;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (source.size() > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; value = source.get(0);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; source.remove(0);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.addAll(merge(value, list));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; }&nbsp; &nbsp; public static List<String> merge(String value, List<String> list) {&nbsp; &nbsp; &nbsp; &nbsp; List<String> result = new ArrayList<>(list);&nbsp; &nbsp; &nbsp; &nbsp; if (value != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.add(value);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; List<String> result = merge(FIRST, SECOND, THIRD, FOURTH);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(result);&nbsp; &nbsp; }}//结果[A, C, D, B, F, E, G, J, H, I]