java - Java中使用Queue进行归并排序

Question

public class NumberQueue {
    private int firstLoc=0;
    private int lastLoc=0;
    private int[] numArray = new int[MAXSIZE]; 
    public static final int MAXSIZE=100;

    public int getQsize() { 
        return (MAXSIZE+lastLoc-firstLoc) % MAXSIZE;
    }

    public boolean fullCheck() { 
        return (getQsize() == MAXSIZE-1);
    }

    public boolean emptyCheck() { 
        return (firstLoc == lastLoc); 
    }

    public int getValue(int loc) { 
        return numArray[loc];
    }   

    public int front() {
        return numArray[firstLoc]; 
    }

    public void remove() { 
        if (!emptyCheck()) 
            firstLoc = (firstLoc + 1) % MAXSIZE;
    }

    public int insert(int val) {
        if (fullCheck()) {
            return -1;
        } else {
          numArray[lastLoc] = val;
          lastLoc = (lastLoc +1) % MAXSIZE;
          return 0;
        }
    }

    public void display() {
        int i = firstLoc;
        while(i < lastLoc) {
            System.out.print(numArray[i]+" ");
            i++;
        }
        System.out.println();
    }   
}


public class NumberQueueMain {
  public static void main(String[] args) {

    //Create three queues
    NumberQueue S1 = new NumberQueue();
    NumberQueue S2 = new NumberQueue();
    NumberQueue S3 = new NumberQueue();

    //Get the array of queues       
    Scanner S = new Scanner(System.in);
    System.out.println("Enter a series of number with a space between each value: ");       
    String str = S.nextLine();
    String[] arr = str.split(" ");
    int array[] = new int[arr.length];
    for(int i = 0; i < arr.length; i++) {
        array[i] = Integer.parseInt(arr[i]);
    }

    //Put the array into the NumberQueues-S1.
    for(int i = 0; i < arr.length; i++) {
        S1.insert(array[i]);
    }

    //Merge Sort S1 
    int loc = -1;
    while(loc < (S1.getQsize()-1)) {
        do {
            S2.insert(S1.front());       
            S1.remove();                
            loc++;
        } while(S1.getValue(loc) < S1.getValue(loc+1) && loc < S1.getQsize()-1);
        S2.display(); 

        while(loc < S1.getQsize()-1) {
            do{
                S3.insert(S1.front());
                S1.remove();
                loc++;
        } while(S1.getValue(loc) < S1.getValue(loc+1) && loc < S1.getQsize()-1);
            S3.display();
        }

        while(!S2.emptyCheck() && !S3.emptyCheck()) {
            if(S2.front() > S3.front()) {
                S1.insert(S3.front());
                S3.remove();        
            } else if(S2.front()==S3.front()) {
                S1.insert(S2.front());
                S1.insert(S3.front());
                S2.remove();
                S3.remove();
            } else {
                S1.insert(S2.front());
                S2.remove();
            }
        }

        if (S2.emptyCheck()){
            int sizeS3 = S3.getQsize();
            for(int i = 0;i < sizeS3; i++){
                S1.insert(S3.front());
                S3.remove();
            }
        } else if(S3.emptyCheck()){
            int sizeS2 = S2.getQsize();
            for(int i = 0;i < sizeS2; i++) {
                S1.insert(S2.front());
                S2.remove();
            }
        }
    } 
    System.out.println();
    S1.display();
  }

}

输出:

Enter a series of number with a space between each value: 3 5 7 2 3 5 11 34 12 10 15 18 3 12 17 22 12 18 25 22 30 3 5 7 2 3 5 11 34 2 3 5 11 34 12 2 3 5 11 34 12 10 15 18 3 12 17 22 12 18 25 22 30

2 3 3 5 5 7 11 34 12 10 15 3 12 17 18 22 12 18 25 22 30

问题:
为什么它只对彼此相邻的两个队列进行排序，并且只做了一次。我找不到可以修复的地方。任何人都可以帮助我，拜托!!!

Answer 1

您的代码中有很多问题。但首先考虑第一个问题，您没有处理所有数据的原因是以下行中的错误:

while(loc < (S1.getQsize()-1))

以下 block 中的代码从 S1 中删除项目，因此大小随着每次迭代而减小。

您可以通过以下方式解决此问题:

int size = S1.getQsize();
while (loc < size - 1)

或者(更好)

while (!S1.emptyCheck)

但是，即使处理所有输入数据，排序算法仍然存在错误。也许您可以解决这个问题，进一步调查，然后在遇到困难时提出一个具体问题。