java - 使用 "Divide and Conquer"在 Java 中排序

Question

合并排序，通过将一个随机数组分成两半，然后将它们按数字顺序排序。概念被称为“分而治之”。输出是乱序的，我看不出这段代码有什么问题。 Main 只是输出数组中的所有数字。仅供引用，代码的其他部分不是问题。但如果你需要，我可以给你。

private void merge(int[] a, int first, int mid, int last)
{
    int size = last - first + 1;
    int [] temp = new int[size];
    int i = first, j = mid + 1;
    for(int s = 0; s < size; s++){ // a.length
        if(i > mid){ // case a
            temp[s] = a[j];
            j++;
        }else if(j > last){ // case b
            temp[s] = a[i];
            i++;
        }else if(a[i] < a[j]){ // case c
            temp[s] = a[i];
            i++;
        }else if(a[j] <= a[i]){ // case d
            temp[s] = a[j];
            j++;
        }
    }

    for(int s = first; s < size; s++){
        a[first] = temp[s - first];
    }
}

public void mergeSort(int[] a, int first, int last)
{
    int size = last - first + 1, mid;
    if(size == 1){
        steps++;
    }else if(size == 2){
        if(a[last] > a[first]){
            int temp = a[last];
            a[last] = a[first];
            a[first] = temp;
            steps += 3;
        }
    }else{
        mid = (last + first) / 2;
        mergeSort(a, first, mid);
        mergeSort(a, mid + 1, last);
        merge(a, first, mid, last);
        steps += 4;
    }
}

这是生成器的样子:

private void fillArray(int numInts, int largestInt)
{
    myArray = new int[numInts];
    Random randGen = new Random();

    for(int loop = 0; loop < myArray.length; loop++){
        myArray[loop] = randGen.nextInt(largestInt) + 1;
    }
}

Answer 1

您的代码中有两个缺陷:

首先:

for(int s = first; s - first < size; s++){// replace s<size with s-first<size
        a[s] = temp[s - first];//yours a[first] = temp[s-first] 
}

在您的编码中，first 是固定的，它会始终更新 a[first]，我认为这不是您想要的。

第二个:

....
}else if(a[i] > a[j]){ // case c  yours a[i]<a[j]
            temp[s] = a[i];
            i++;
}else if(a[i] <= a[j]){ // case d  yours a[j] <= a[i]
            temp[s] = a[j];
            j++;
}
.... 

因为关于你的排序，你会得到一个下降序列，而在合并中你想要得到升序，这相互冲突。