Java：将列表分解为排序的"Chunks"，以完全排序列表

Question

好了，这是我的第一个帖子，所以请耐心等待。

所以我尽量自己解决这个问题，但是我有点不知所措。我已经得到了一个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

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

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

下面是我的一段代码，如果有帮助的话:

    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;

提前感谢!

编辑:

我最终使用了类似于@厄立特里亚建议的东西，但一个全新的问题出现了。我的列表被移动到一个块列表中，但是列表中的最后一项(98)也应该是最后一个块，被删除了。我试图在另一个问题中询问如何解决这个问题，并立即被驳回，因为它是重复的。这些"答案"并没有真正回答我的问题。对此有更多的了解就太好了。

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

Answer 1

您可以遍历列表，并通过比较当前元素与其后继元素来查找列表中已排序的部分。然后，您可以使用方法列表将这些部件添加到列表列表中。subList(int from mindex, 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;       
      }
  }