0

我正在构建一个扩展 ArrayList 的可排序 ArrayLists 类。目标是能够在 SortDoubleArray 上调用排序方法，并通过所描述的方法对该数组进行排序。我得到了快速排序、插入排序、冒泡排序和选择排序，所有这些都可以按我的意愿工作。但是，我在使用合并排序时遇到了一些困难。

排序工作，但由于涉及递归的工作方式，我被迫将列表的内容重置为应用于自身的方法。

首先，这里是测试器类。它显示了其他类型是如何实现的。如果我在解释我的问题时做得不好，希望您会看到必须使用 mergeSort() 方法的不同之处。

public class SortTester
{
    /**
     * @param args
     */
    public static void main(String[] args)
    {
        SortDoubleArray list = new SortDoubleArray();

        // Code to fill an array with random values.

        //list.quickSort();
        //list.insertionSort();
        //list.selectionSort();
        //list.bubbleSort();
        list = list.mergeSort();

        // Code to print the sorted array.
    }
}

接下来，这里是 SortDoubleArray 类。为简洁起见，除插入排序（作为我想要的工作方式的示例）之外的所有其他排序都已被删除。

public class SortDoubleArray extends ArrayList<Double>
{ // Start of class.
    private static final long serialVersionUID = 1271821028912510404L;

    /**
     * Progresses through the elements one at a time inserting them in their proper place
     * via swaps.
     */
    public void insertionSort()
    { // Start of insertionSort.
        int current = 1;

        while (current < size())
        {
            int i = current;
            boolean placeFound = false;

            while(i > 0 && !placeFound)
            {
                if (get(i) < get(i - 1))
                {
                    double temp = get(i);
                    set(i, get(i - 1));
                    set(i - 1, temp);
                    i -= 1;
                }
                else
                {
                    placeFound = true;
                }
            }
            current += 1;
        }
    } // End of insertionSort.

    /**
     * Triggers the recursive mSort method.
     * @return 
     */
    public SortDoubleArray mergeSort()
    { // start of mergeSort.
        return mSort(this);
    } // End of mergeSort.

    /**
     * Separates the values each into their own array.
     */
    private SortDoubleArray mSort(SortDoubleArray list)
    { // Start of mSort.
        if (list.size() <= 1)
        {
            return list;
        }

        SortDoubleArray left = new SortDoubleArray();
        SortDoubleArray right = new SortDoubleArray();

        int middle = list.size() / 2;

        for (int i = 0; i < middle; i += 1)
        {
            left.add(list.get(i));
        }

        for (int j = middle; j < list.size(); j += 1)
        {
            right.add(list.get(j));
        }

        left = mSort(left);
        right = mSort(right);

        return merge(left, right);
    } // End of mSort.

     /**
     * Merges the separated values back together in order.
     */
    private SortDoubleArray merge(SortDoubleArray left, SortDoubleArray right)
    { // Start of merge.
        SortDoubleArray result = new SortDoubleArray();

        while (left.size() > 0 || right.size() > 0)
        {
            if (left.size() > 0 && right.size() > 0)
            {
                if (left.get(0) <= right.get(0))
                {
                    result.add(left.get(0));
                    left.remove(0);
                }
                else
                {
                    result.add(right.get(0));
                    right.remove(0);
                }
            }
            else if (left.size() > 0)
            {
                result.add(left.get(0));
                left.remove(0);
            }
            else if (right.size() > 0)
            {
                result.add(right.get(0));
                right.remove(0);
            }
        }

        return result;
    } // End of merge.
} // End of class.

请给我一些关于如何更改 SortDoubleArray 类中的 mergeSort() / mSort() 函数的想法，以使其具有与其他排序相同的实现。

谢谢！

4

2 回答 2

0

鉴于mSort和merge方法是正确的，这个怎么样？

public void mergeSort()
{ // start of mergeSort.
    SortDoubleArray result = mSort(this);
    clear();
    addAll(result);
} // End of mergeSort.

然后，您的测试中的相关行将是：

    list.mergeSort();

祝你好运！

于 2013-02-21T23:57:37.173 回答
0

目前，您的mergeSort()和merge()函数都在创建新SortedDoubleArray对象。理想情况下，您会在不创建新数组的情况下就地完成所有操作，您创建和复制的数量将对您的算法产生相当大的性能影响。

所以你的方法会有这样的原型：

private SortDoubleArray mSort(SortDoubleArray list, int startIndex, int length)

private SortDoubleArray merge(SortDoubleArray list, 
                              int leftIndex, int leftlength,
                              int rightIndex, int rightlength)

Then use ArrayList.set and .get with a temporary variable to do the swapping in-place. This will mean you're only working on a single array and not creating any new unnecessary ones.

Does this help? Let me know if I understood the issue or you need more explanation.

Note that int endIndex can also work instead of int length

于 2013-02-22T00:01:13.260 回答