0

これまでのところ、次のコードがあります。

public class MergeSort {
int[] theList;
int counter;  //required for analysis later
double time;  //required for analysis later

MergeSort(int[] n){
    int len = n.length;
    this.theList = mergeSort(n, 0, len);
}

int[] mergeSort(int[] n, int p, int r){
    if((p + 1 )<r){
        int q = (r + p)/2;
        mergeSort(n, p, q);
        mergeSort(n, q+1, r);
        merge(n, p, q, r);
    }
    return n;

}
public void merge(int[] input, int p, int q, int r){
    int lefti = q - p;
    int righti = r - q;
    int[] left = new int[lefti+1];
    int[] right = new int[righti+1];
    for(int i = 0; i < lefti; i++){
        this.counter++;
        left[i] = input[p+i];
    }
    for(int i = 0; i < righti; i++){
        this.counter++;
        right[i] = input[q+i];
    }
    left[left.length - 1] = 1000000;
    right[right.length - 1] = 1000000;
    int i = 0;
    int j = 0;
    for(int k = p; k < r; k++){
        this.counter++;
        if(left[i] < right[j]){
            input[k] = left[i];
            i++;
        }
        else{
            input[k] = right[j];
            j++;
        }
    }
}

}

私はこれをあまりにも長く見つめていたと思います.誰かが私をより良い方向に導くことができれば幸いです.

現在、MergeSort([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]) の入力では、theList equals[4, 1, 0, 2, 3, 7, 5, 6 、8、9]。

私が受けられるどんな助けにも感謝します。

4

1 に答える 1

0

mergeSort メソッドの基本ケースが必要なようです。(p+1) >= r の場合、サブ配列をソートします (つまり、サブ配列のサイズは 1 または 2 にする必要があります。サイズが 1 の場合は何もせず、サイズが 2 の場合はスワップします順序が間違っている場合は 2 つの値)

于 2013-04-02T19:45:04.070 に答える