Mergesort 拆分为 2 个数组

Question

我正在尝试做一个作业，但我无法正确进行合并排序。我们基本上必须制作一个新版本的归并排序。首先接收原始数组进行排序，然后我们必须将其拆分为 2 个子数组，然后通过另一种方法将它们重新组合在一起。

我无法更改方法的创建方式，无法更改 return 的类型或参数，我只能更改其主体。

到目前为止，这是我的代码。每种方法的说明都在其顶部说明。（它是西班牙语 D:)

/**
     * SII i<=f: devuelve un array con los elementos del subarray 
     * v[i, f] ordenados Asc. 
     * 
     * @param v  Sus elementos implementan la interfaz Comparable
     * @param i  Extremo inferior del intervalo a ordenar
     * @param f  Extremo superior del intervalo a ordenar
     * @return T[], el array resultante de ordenacion de v[i, f]
     */
    private static <T extends Comparable<T>> T[] mergeSort2(T[] v,
                                                             int i, int f) {
        T[] resultado = (T[]) new Comparable[f-i+1];                                                        
        if (i < f) {
            int m = (i + f) / 2;
            T[] v1 = Arrays.copyOfRange(v, i, m);
            T[] v2 = Arrays.copyOfRange(v, m, f);
            v1 = mergeSort2(v, i, m);
            v2 = mergeSort2(v, m + 1, f);
            resultado = merge2(v1, v2);
        }
        return resultado;
    }        
    
    /**
     * Devuelve el array mezcla de v1 y v2, dos arrays ordenados Asc.
     * 
     * @param v1  Sus elementos implementan la interfaz Comparable
     * @param v2  Sus elementos implementan la interfaz Comparable
     * @return T[], el array resultante de la fusion de v1 y v2
     */
    
    private static <T extends Comparable<T>> T[] merge2(T[] v1, T[] v2) {
        T[] aux = (T[]) new Comparable[v1.length + v2.length];
        int i = 0, j = 0, k = 0;
        while (i < v1.length && j < v2.length)  
           aux[k++] = v1[i].compareTo(v2[j]) < 0 ? v1[i++] :  v2[j++];
    
        while (i < v1.length)  
            aux[k++] = v1[i++];
    
        while (j < v2.length)    
            aux[k++] = v2[j++];
    
        return aux;
    }

我一整天都在尝试这个。请帮忙！

Answer 1

由于函数 return 数组，您不需要创建它们。请注意，mergeSort return 是一个 Comparable，但 returned 数组将与输入数组具有相同的类型。调用参数是第一个和最后一个元素的索引（更常见的是使用第一个和结束（last+1）索引）。

import java.util.Arrays;
import java.util.Random;
// ...

    private static <T extends Comparable<T>> T[] mergeSort2(T[] v,
                                                             int i, int f) {
        if (i < f) {
            int m = (i + f) / 2;
            T[] v1 = mergeSort2(v, i, m);
            T[] v2 = mergeSort2(v, m + 1, f);
            return merge2(v1, v2);
        }
        return Arrays.copyOfRange(v, i, f);
    }        
    
    private static <T extends Comparable<T>> T[] merge2(T[] v1, T[] v2) {
        T[] aux = (T[]) new Comparable[v1.length + v2.length];
        int i = 0, j = 0, k = 0;
        while (i < v1.length && j < v2.length)  
           aux[k++] = v1[i].compareTo(v2[j]) < 0 ? v1[i++] :  v2[j++];
        while (i < v1.length)  
            aux[k++] = v1[i++];
        while (j < v2.length)    
            aux[k++] = v2[j++];
        return aux;
    }

    public static void main(String[] args) {
        Integer[] a = new Integer[1024*1024];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        Comparable[]b = mergeSort2(a, 0, a.length-1);
        end = System.currentTimeMillis();

        for(int i = 1; i < b.length; i++){
            if(b[i-1].compareTo(b[i]) > 0){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }

Mergesort 拆分为 2 个数组

Mergesort split into 2 arrays

java

mergesort