Java: 将一个列表分解成 "Chunks" 个已排序的列表，对列表进行完全排序

Question

好的，先post到这里，还请多多包涵。

所以我尽可能地尝试自己解决这个问题，但我在这里有点不知所措。我得到了一个包含 12 个整数的列表（并且还会给出更多的列表来测试，但我正在使用这个列表）。名单如下：

18 21 9 12 99 4 101 8 14 7 112 98

并且块被定义为已经排序的整数分组。这意味着有 6 个块。由于这是递归块合并排序，我需要能够根据块将其分解。

第一个拆分看起来像：

18 21 9 12 99 4 101 | 8 14 7 112 98

第二个看起来像：

18 21 | 9 12 99 | 4 101 ||| 8 14 | 7 112 | 98

如您所见，这意味着六个块。现在，我已经设法完成了第一步，但这不是通过递归或通过这些块完成的。我作弊并把列表的大小切成两半。那是不行的。

我愿意尝试任何建议，我只是对如何将其分解成这些块感到困惑，特别是如果我无法决定要进入的 "chunks" 的数量。

这是我的一段代码，如果有帮助的话：

    public List<Integer> chunkMergesort(List<Integer> S) {
    int c = 0;

    if(S.size() > 1){
        c = 1;
        for(int i = 0; i<S.size()-1 ; i++){
            if(S.get(i+1)< S.get(i)){
                c++;
                System.out.println("C is: " + c);
            }
        }
        System.out.println("Final C is: " + c);
        chunkDivide(S, c);
    }
        return S;
}

public Chunks chunkDivide(List<Integer> S, int c) {

    int Ssize = S.size()/2;
    System.out.println("List:"+ S);

    List<Integer> S1 = new ArrayList<Integer>();
    List<Integer> S2 = new ArrayList<Integer>();

    for(int i = 0; i < Ssize; i++){
        //System.out.println("i is: "+ i);
        S1.add(i, S.get(i));    
        System.out.println("S1 is:"+ S1);
    }

    for(int i = Ssize; i < S.size(); i++){
        S2.add(i-Ssize, S.get(i));
        System.out.println("S2 is:"+ S2);

    }

    System.out.println("S1 is: "+ S1);
    System.out.println("S2 is: "+ S2);      

    Chunks p = new Chunks(S1, S2);

    //chunkMergesort(S1);
    //chunkMergesort(S2);
    //chunkDivide(p.right, mid);
    //chunkDivide(p.left, mid);

    merge(S1,S2);

    return p;

提前致谢！

编辑：

我最终使用了类似于@Eritrean 建议的方法，但出现了一个全新的问题。我的列表被移动到块列表中，但列表中的最后一项 (98) 也应该是最后一个块，被删除了。我试图在另一个问题中询问如何解决这个问题，但立即被驳回，因为它是重复的。那些 "answers" 实际上并没有回答我的问题。对此有任何更深入的了解会很棒。

下面是我显示输出的图像。 CMD Snip

Answer 1

您可以遍历列表并通过比较当前元素及其后继元素来查找列表中已排序的部分。然后，您可以使用 list.subList(int fromIndex, int toIndex) 方法将这些部分添加到列表列表中。示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NewClass {

    public static void main(String[] args) {
        List<Integer> intList = Arrays.asList(18, 21, 9, 12, 99, 4, 101, 8, 14, 7, 112, 98);

        List<List<Integer>> chunks = breakIntoChunks(intList);

        for(List<Integer> chunk : chunks){
            System.out.println(chunk);
        }
    }

    private static List<List<Integer>> breakIntoChunks(List<Integer> intList) {
        List<List<Integer>> chunks = new ArrayList<>();
        int curr =0;
        for(int i = 0; i<intList.size()-1; i++){
            if(intList.get(i).compareTo(intList.get(i+1))>0 || i==intList.size()-1){
                chunks.add(intList.subList(curr, i+1));
                curr = i+1;
            }
         }
         if(curr<=intList.size()){
              chunks.add(intList.subList(curr,intList.size()));
         }
         return chunks;       
      }
  }

Java: 将一个列表分解成 "Chunks" 个已排序的列表，对列表进行完全排序

Java: Breaking a list into "Chunks" that are sorted, to sort list completely

java

arrays

mergesort

list