MergeSort 将零放入数组

Question

MergeSort.java:

public class MergeSort {

    public static void run(int[] array, int size) {
        mergeSort(array, 0, size - 1);
    }
    
    private static void mergeSort(int[] array, int i, int f) {
        if (i >= f) {
            return;
        }
        
        int m = (i + f) / 2;
        mergeSort(array, i, m);
        mergeSort(array, m + 1, f);
        merge(array, i, m, f);
    }
    
    private static void merge(int[] array, int i1, int f1, int f2) {
        int[] aux = new int[f2 - i1 + 1];
        
        int startSave = i1;
        int endSave = f2;
        
        int i2 = f1 + 1;
        int i = 0;
        
        while (i1 <= f1 && i2 <= f1) {
            if (array[i1] <= array[i2]) {
                aux[i] = array[i1];
                ++i;
                ++i1;
            } else {
                aux[i] = array[i2];
                ++i;
                ++i2;
            }
        }
        
        if (i1 < f1) {
            while (i1 <= f1) {
                aux[i] = array[i1];
                ++i;
                ++i1;
            }
        } else {
            while (i2 <= f2) {
                aux[i] = array[i2];
                ++i;
                ++i2;
            }
        }
        
        int k = 0;
        for (int j = startSave; j <= endSave; ++j) {
            array[j] = aux[k];
            ++k;
        }
    }
}

Main.java:

import java.util.Random;

public class Main {
    public static void main(String args[]) {
        Main m = new Main();
        m.run();
    }
    
    private void run() {
        Random r = new Random();
        int size = 8;
        int[] array = new int[size];
        
        int el = 0;
        for (int i = 0; i < size; ++i) {
            el = r.nextInt(50);     // randomly fills the array
            array[i] = el;
            System.out.print(array[i] + " ");    // prints each element
        }
        System.out.println("");
        
        MergeSort.run(array, size);
        
        for (int i = 0; i < size; ++i) {
            System.out.print(array[i] + " ");    // print each element to know if array is sorted
        }
        System.out.println("");
    }
}

输出如下：

$ java Main 
30 38 14 29 42 44 43 34 
38 0 0 0 0 0 0 0

或

17 29 4 17 13 21 47 19 
17 0 0 0 0 0 0 0

或

41 25 38 49 7 4 26 46 
25 0 0 0 0 0 0 0

我不知道为什么这不起作用。为什么它只打印一个元素而其他所有元素都是零？此外，第一个元素甚至不是最小值……因此代码中肯定存在某些错误。你可以帮帮我吗？我不知道我做错了什么

Answer 1

除了一些错误外，您的代码几乎是正确的：

merge() 中的第一个 while 循环应该是 while (i1<=f1 && i2<=f2)（对于第二个条件，f2 而不是 f1）
您在此块中的 if 条件与 while 循环冲突：

if (i1<f1){
    while (i1<=f1){
        aux[i] = array[i1];
        ++i;
        ++i1;
    }
} else{
    while (i2<=f2){
        aux[i] = array[i2];
        ++i;
        ++i2;
    }
}

但你甚至不需要它们。只需将整个块替换为：

while (i1<=f1){
    aux[i] = array[i1];
    ++i;
    ++i1;
}
while (i2<=f2){
    aux[i] = array[i2];
    ++i;
    ++i2;
}

通过这些更改，它似乎奏效了！代码如下（我把它们合并成一个class）：

import java.util.Random;

public class Main{
    public static void main(String args[]){
        Main m = new Main();
        m.run();
    }
    
    private void run(){
        Random r = new Random();
        int size = 8;
        int[] array = new int[size];
        
        int el = 0;
        for(int i=0; i<size; ++i){
            el = r.nextInt(50);     // randomly fills the array
            array[i] = el;
            System.out.print(array[i] + " ");    // prints each element
        }
        System.out.println("");
        
        runMergeSort(array,size);
        
        for(int i=0; i<size; ++i){
            System.out.print(array[i] + " ");    // print each element to know if array is sorted
        }
        System.out.println("");
    }
    
    public static void runMergeSort(int[] array, int size){
        mergeSort(array,0,size-1);
    }
    
    private static void mergeSort(int[] array, int i, int f){
        if (i>=f){
            return;
        }
        
        int m = (i+f)/2;
        mergeSort(array,i,m);
        mergeSort(array,m+1,f);
        merge(array,i,m,f);
    }
    
    private static void merge(int[] array, int i1, int f1, int f2){
        int[] aux = new int[f2-i1+1];
        
        int startSave = i1;
        int endSave = f2;
        
        int i2 = f1+1;
        int i = 0;
        
        while (i1<=f1 && i2<=f2){
            if (array[i1]<=array[i2]){
                aux[i] = array[i1];
                ++i;
                ++i1;
            } else {
                aux[i] = array[i2];
                ++i;
                ++i2;
            }
        }
        
        while (i1<=f1){
            aux[i] = array[i1];
            ++i;
            ++i1;
        }
         while (i2<=f2){
            aux[i] = array[i2];
            ++i;
            ++i2;
        }
        
        int k = 0;
        for (int j=startSave; j<=endSave; ++j){
            array[j]=aux[k];
            ++k;
        }
    }
}

Answer 2

除了 Aziz 富有洞察力的回答之外，我还想强调在 mergeSort() 中包含边界 i 和 f 的约定可能造成的混淆。将上边界作为第一个值的索引在之后切片允许更简单的代码，无需 +1/-1 调整和更惯用的 < 索引比较。

这是修改后的版本：

public class MergeSort {

    public static void run(int[] array, int size) {
        mergeSort(array, 0, size);
    }
    
    private static void mergeSort(int[] array, int i, int f) {
        if (f - i < 2) {
            return;
        }
        
        int m = i + (f - i) / 2;  /* avoid potential overflow on `(i + f) / 2`
        mergeSort(array, i, m);
        mergeSort(array, m, f);
        merge(array, i, m, f);
    }
    
    private static void merge(int[] array, int i1, int f1, int f2) {
        int[] aux = new int[f2 - i1];
        
        int startSave = i1;
        int endSave = f2;
        
        int i2 = f1;
        int i = 0;
        
        while (i1 < f1 && i2 < f1) {
            if (array[i1] <= array[i2]) {
                aux[i++] = array[i1++];
            } else {
                aux[i++] = array[i2++];
            }
        }
        
        while (i1 < f1) {
            aux[i++] = array[i1++];
        }
        while (i2 < f2) {
            aux[i++] = array[i2++];
        }
        
        int j = startSave;
        for (int k = 0; k < i; k++) {
            array[j++] = aux[k];
        }
    }
}

MergeSort 将零放入数组

MergeSort put zeros in the array

java

sorting

merge

mergesort

array-merge