MergeSort -Recursively

Question

如果没有任何软件包的帮助，你会怎么写这个？( mergeSort(int[] A) (接受一个数组的输入)和合并( int[] a、int[] l、int[]r)的布局相同。主要问题是将Arrays.copyOfRange转换为非-package版本的java到此代码。谢谢你回答这个问题。

我的另一个问题是如何在参数中使用3个数组来实现合并函数。

这是我尝试过的代码：

 public static int[] mergeArrays3(int[] a, int[] b, int[] c) {
        
       
        int[] result = new int[a.length + b.length +c.length];

        int i = 0, j = 0, k = 0, l=0;
        while(i<a.length &&j<b.length && l<c.length)

        {
//            if (b[i] < a[j] || b[i] <c[i]) {
//                result[k] = c[i];
//                j++;
//            }
            if (c[i] < b[j] || c[i] <a[i]) {
                    result[k] = c[i];
                    l++;
                }

            if (a[i] < b[j] || a[i] <c[i]) {
                result[k] = a[i];
                i++;
            }
            else {
                result[k] = b[j];
                j++;
            }
            k++;
        }
        while(i<a.length)

        {
            result[k] = a[i];
            i++;
            k++;
        }
        while(j<b.length)

        {
            result[k] = b[j];
            j++;
            k++;
        }

        while(l<c.length)
        {
            result[k]=c[l];
            l++;
            k++;
        }

        return result;

    }

进口java.io.*；

进口java.util.Arrays；

公共类MergeSort {

public static void main(String[] args) throws IOException{

    BufferedReader R = new BufferedReader(new InputStreamReader(System.in));

    int arraySize = Integer.parseInt(R.readLine());

    int[] inputArray = new int[arraySize];

    for (int i = 0; i < arraySize; i++) {

        inputArray[i] = Integer.parseInt(R.readLine());

    }

    mergeSort(inputArray);

    for (int j = 0; j < inputArray.length; j++) {

        System.out.println(inputArray[j]);

    }

}

static void mergeSort(int[] A) {

    if (A.length > 1) {

        int q = A.length/2;

//将leftArray的范围从0到-q更改为0到-(q-1)，如何编辑Arrays.copyOfRange以手动生成相同的函数而不使用任何包？

        *int[] leftArray = Arrays.copyOfRange(A, 0, q-1);

//将rightArray的范围从Q到A长度更改为q- to -(A.length-1)

        int[] rightArray = Arrays.copyOfRange(A,q,A.length-1);*

        mergeSort(leftArray);

        mergeSort(rightArray);

        merge(A,leftArray,rightArray);

    }

}

static void merge(int[] a, int[] l, int[] r) {

    int totElem = l.length + r.length;

    //int[] a = new int[totElem];

    int i,li,ri;

    i = li = ri = 0;

    while ( i < totElem) {

        if ((li < l.length) && (ri<r.length)) {

            if (l[li] < r[ri]) {

                a[i] = l[li];

                i++;

                li++;

            }

            else {

                a[i] = r[ri];

                i++;

                ri++;

            }

        }

        else {

            if (li >= l.length) {

                while (ri < r.length) {

                    a[i] = r[ri];

                    i++;

                    ri++;

                }

            }

            if (ri >= r.length) {

                while (li < l.length) {

                    a[i] = l[li];

                    li++;

                    i++;

                }

            }

        }

    }

    //return a;

}

}

```javascript

Answer 1

这种方法不像Arrays.copyOfRange那样快，也不包括所有的情况，如负索引，也有必要检查大小。

private static int[] copyArray(int[] original, int from, int to) {
  int [] res = new int[to-from];
  for (int i = from; i< to; i++) {
    res[i - from] = original[i];
  }
  return res;
}

Answer 2

为一次数组复制和交替参数进行自顶向下的合并排序和for循环，以改变合并的方向和每个递归级别。MergeSort是一个条目函数，它分配并复制到第二个数组。MergeSortR是递归函数。除非所有3个子数组至少有一个元素，否则永远不会调用合并。合并中的嵌套的if \ The只需要2比较来确定最小的元素，但是使用重复的代码来处理aa2是最小元素的情况。(使用C|C++，可以使用goto的代码避免重复代码)。bb是开始索引，ee是结束索引。

    static void MergeSort(int[] a)
    {
        if(a.length < 2)                // if < 2 elements, nothing to sort
            return;
        int [] b = new int[a.length];   // b[] = a[] | int[]b = a.clone();
        for(int i = 0; i < a.length; i++)
            b[i] = a[i];
        MergeSortR(b, a, 0, a.length);  // sort b[] to a[]
    }

    static void MergeSortR(int[] b, int[] a, int bb, int ee)
    {
        if(ee - bb < 2)                 // if < 2 elements, nothing to sort
            return;
        if(ee - bb == 2){               // if 2 elements
            if(a[bb] > a[bb+1]){
                int t = a[bb];
                a[bb] = a[bb+1];
                a[bb+1] = t;
            }
            return;
        }
        int m1 = bb+(ee+0-bb)/3;        // split into 3 parts
        int m2 = m1+(ee+1-bb)/3;
        MergeSortR(a, b, bb, m1);       // sort a[] to b[]
        MergeSortR(a, b, m1, m2);
        MergeSortR(a, b, m2, ee);
        Merge(b, a, bb, m1, m2, ee);    // merge b[] to a[]
    }
    
    static void Merge(int[] a, int[] b, int bb, int m1, int m2, int ee)
    {
        int b0 = bb;                    // b[] index
        int a0 = bb;                    // a[] indexes
        int a1 = m1;
        int a2 = m2;
        while(true){                    // 3 way merge
            if(a[a0] <= a[a1]){
                if(a[a0] <= a[a2]){
                    b[b0] = a[a0];      // a[a0] smallest
                    b0++;
                    a0++;
                    if(a0 < m1)         //  if not end of run
                        continue;       //   continue
                    a0 = a1;            //  else setup for 2 way merge
                    a1 = a2;
                    m1 = m2;
                    m2 = ee;
                    break;
                } else {
                    b[b0] = a[a2];      // a[a2] smallest
                    b0++;
                    a2++;
                    if(a2 < ee)         //  if not end of run
                        continue;       //   continue
                    break;              //  else setup for 2 way merge
                }
            } else {
                if(a[a1] <= a[a2]){
                    b[b0] = a[a1];     // a[a1] smallest
                    b0++;
                    a1++;
                    if(a1 < m2)         //  if not end of run
                        continue;       //   continue
                    a1 = a2;            //  else setup for 2 way merge
                    m2 = ee;
                    break;
                } else {
                    b[b0] = a[a2];      // a[a2] smallest
                    b0++;
                    a2++;
                    if(a2 < ee)         //  if not end of run
                        continue;       //   continue
                    break;              //  else setup for 2 way merge
                }
            }
        }    
        while(true){                    // 2 way merge
            if(a[a0] <= a[a1]){
                b[b0] = a[a0];
                b0++;
                a0++;
                if(a0 < m1)             //  if not end of run
                    continue;           //   continue
                a0 = a1;                //  else setup for copy
                m1 = m2;
                break;
            }else{
                b[b0] = a[a1];
                b0++;
                a1++;
                if(a1 < m2)             //  if not end of run
                    continue;           //   continue
                break;                  //  else setup for copy
            }
        }
        while(true){                    // copy rest of remaining run
            b[b0] = a[a0];
            b0++;
            a0++;
            if(a0 < m1)
                continue;
            break;
        }
    }