你能帮我使用 ArrayList 为 MergeSort 获得正确的输出吗 [英] Can you help me get the right output for MergeSort using ArrayList

问题描述

我是合并排序的新手，我能够使用整数数组 int[] 解决合并排序，但是每当我尝试使用 ArrayList 实现它时，我似乎根本无法获得正确的顺序.我试图了解为什么会这样，以及使用相同的方法和变量名称的实际解决方案是什么.

I'm new to mergeSort and I was able to solve mergeSort using integer array int[] however whenever I try to implement it using ArrayList, I can't seem to get the order right at all. I'm trying to understand why this is and what the actual solution to this would be using the same methods and variable names.

/* Java program for Merge Sort */
import java.util.ArrayList;
import java.util.Scanner;
class MergeSort
{
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(ArrayList<Integer> al, int beg, int mid, int end)
    {
        // Find sizes of two subarrays to be merged
        int ls = mid - beg + 1;
        int rs = end - mid;

        /* Create temp arrays */
        ArrayList lft = new ArrayList(ls);
        ArrayList rgt = new ArrayList(rs);

        /*Copy data to temp arrays*/
        for (int i = 0; i < ls; i++)
            lft.add(i, al.get(beg + i));
        for (int j = 0; j < rs; ++j)
            rgt.add(j, al.get(mid + 1 + j));

        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int li;
        int ri;
        li = 0;
        ri = 0;

        // Initial index of merged subarry array
        int mi = beg;
        while (li < ls && ri < rs) {
            if ((int)lft.get(li) <= (int)rgt.get(ri)) {
                al.set(mi, (int)lft.get(li));
                li++;
            } else {
                al.set(mi, (int)rgt.get(li));
                ri++;
            }
            mi++;
        }

        /* Copy remaining elements of L[] if any */
        while (li < ls) {
            al.add(mi, (int)lft.get(li));
            li++;
            mi++;
        }

        /* Copy remaining elements of R[] if any */
        while (ri < rs) {
            al.add(mi, (int)rgt.get(ri));
            ri++;
            mi++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(ArrayList al, int beg, int end)
    {
        if (beg < end) {
            // Find the middle point
            int mid =beg+ (end-beg)/2;

            // Sort first and second halves
            sort(al, beg, mid);
            sort(al, mid + 1, end);

            // Merge the sorted halves
            merge(al, beg, mid, end);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(ArrayList al)
    {
        int arSize = al.size();
        for (int i = 0; i < arSize; i++)
            System.out.print(al.get(i) + " ");
        System.out.println();
    }

    // Driver code
    public static void main(String args[])
    {
        ArrayList finArr = new ArrayList();
        finArr.add(11);
        finArr.add(12);
        finArr.add(10);
        finArr.add(6);
        finArr.add(1);
        System.out.println("Given Array");
        printArray(finArr);

        MergeSort ob = new MergeSort();
        ob.sort(finArr, 0, finArr.size() - 1);

        System.out.println("\nSorted array");
        printArray(finArr);
    }
}

以上代码的输出为:

Given Array
11 12 10 6 1

Sorted array
10 11 12 12 12 12 10 6 1

但是，我不明白为什么输出不是:

however, I don't understand why the output isn't:

Sorted array
1 6 10 11 12

推荐答案

既然你分配了初始大小的临时数组，你应该使用 lft.set() 和 rgt.set() 来设置值而不是 .add.同样，当从临时数组中复制剩余元素时，使用 al.set() 而不是 al.add().

Since you allocate the temporary arrays with an initial size, you should use lft.set() and rgt.set() to set the values instead of .add. Similarly, when copying the remaining elements from the temporary arrays, use al.set() instead of al.add().

这是修改后的版本:

/* Java program for Merge Sort */
import java.util.ArrayList;
import java.util.Scanner;
class MergeSort
{
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(ArrayList<Integer> al, int beg, int mid, int end)
    {
        // Find sizes of two subarrays to be merged
        int ls = mid - beg + 1;
        int rs = end - mid;

        /* Create temp arrays */
        ArrayList lft = new ArrayList<Integer>(ls);
        ArrayList rgt = new ArrayList<Integer>(rs);

        /* Copy data to temp arrays */
        for (int i = 0; i < ls; i++)
            lft.set(i, al.get(beg + i));
        for (int j = 0; j < rs; ++j)
            rgt.set(j, al.get(mid + 1 + j));

        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int li;
        int ri;
        li = 0;
        ri = 0;

        // Initial index of merged subarray array
        int mi = beg;
        while (li < ls && ri < rs) {
            if ((int)lft.get(li) <= (int)rgt.get(ri)) {
                al.set(mi, (int)lft.get(li));
                li++;
            } else {
                al.set(mi, (int)rgt.get(li));
                ri++;
            }
            mi++;
        }

        /* Copy remaining elements of L[] if any */
        while (li < ls) {
            al.set(mi, (int)lft.get(li));
            li++;
            mi++;
        }

        /* Copy remaining elements of R[] if any */
        while (ri < rs) {
            al.set(mi, (int)rgt.get(ri));
            ri++;
            mi++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(ArrayList al, int beg, int end)
    {
        if (beg < end) {
            // Find the middle point
            int mid = beg + (end - beg) / 2;

            // Sort first and second halves
            sort(al, beg, mid);
            sort(al, mid + 1, end);

            // Merge the sorted halves
            merge(al, beg, mid, end);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(ArrayList al)
    {
        int arSize = al.size();
        for (int i = 0; i < arSize; i++)
            System.out.print(al.get(i) + " ");
        System.out.println();
    }

    // Driver code
    public static void main(String args[])
    {
        ArrayList finArr = new ArrayList();
        finArr.add(11);
        finArr.add(12);
        finArr.add(10);
        finArr.add(6);
        finArr.add(1);
        System.out.println("Given Array");
        printArray(finArr);

        MergeSort ob = new MergeSort();
        ob.sort(finArr, 0, finArr.size() - 1);

        System.out.println("\nSorted array");
        printArray(finArr);
    }
}

这篇关于你能帮我使用 ArrayList 为 MergeSort 获得正确的输出吗的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！