Java ArrayList 的递归合并排序

Question

我的合并排序函数遇到了问题，因为每当将一系列整数或字符串输入到程序中时，我无法对其进行排序。我有一个外部类可以调用其中的项目，但是它根本不对数字/字符串进行排序。下面两种方法，不知道问题出在哪里。数字是随机输入的。

代码:

/**
     * Takes in entire vector, but will merge the following sections together:
     * Left sublist from a[first]..a[mid], right sublist from a[mid+1]..a[last].
     * Precondition: each sublist is already in ascending order
     *
     * @param a
     *            reference to an array of integers to be sorted
     * @param first
     *            starting index of range of values to be sorted
     * @param mid
     *            midpoint index of range of values to be sorted
     * @param last
     *            last index of range of values to be sorted
     */
    private void merge(ArrayList<Comparable> a, int first, int mid, int last) {
        int x;
        int i;
        ArrayList<Comparable> left = new ArrayList<Comparable>();
        ArrayList<Comparable> right = new ArrayList<Comparable>();
        mergeSort(a,first,mid);
        for(i = 0; i < a.size() - mid; i++){
            left.add(i,a.get(i));
            a.remove(i);
        }
        mergeSort(a,mid,last);
        for (x = mid; x < a.size(); x++) {
            right.add(x,a.get(x));
            a.remove(x);
        }
        if ((left.get(i).compareTo(right.get(x))) > 0) {
            i++;
            a.add(i);
        } else if (i < x) {
            x++;
            a.add(x);
        }


        System.out.println();
        System.out.println("Merge");
        System.out.println();

    }

    /**
     * Recursive mergesort of an array of integers
     *
     * @param a
     *            reference to an array of integers to be sorted
     * @param first
     *            starting index of range of values to be sorted
     * @param last
     *            ending index of range of values to be sorted
     */
    public void mergeSort(ArrayList<Comparable> a, int first, int last) {

        int mid = (first + last)/2;
        if(first == last){

        }else if(last - first == 1){
            merge(a,first, mid ,last);              
        }else{
            last = mid;
        }


                }

Answer 1

I have an outside class that calls items into it, however it simply doesn't sort the numbers/strings. The two methods are below, I don't know where the problem is.

第一个问题是，如果您使用 first = 0 和 last = a.size() 调用 mergeSort 方法，您将不会'不对任何内容进行排序，因为仅在 last-first == 1 时调用 merge :

public void mergeSort(ArrayList<Comparable> a, int first, int last) {
    int mid = (first + last)/2;
    if(first == last){
    }else if(last - first == 1){
        // you only merge if last - first == 1...
        merge(a,first, mid ,last);              
    }else{
        last = mid;
    }
}

除此之外，我不明白您如何尝试实现合并排序算法。它既不是自上而下的实现，也不是自下而上的实现。您在合并方法中进行了 split ，这也很奇怪。如果您提供了伪代码+调用 public 方法的方式，那么帮助您会更容易。恕我直言，你的算法确实有问题。

事实上，合并排序算法的实现非常简单。为了说明这一点，我写了这个top down implementation of the merge sort algorithm使用 Deque 而不是 List 对象:

import java.util.Deque;
import java.util.LinkedList;

public class Example {

    private LinkedList<Comparable> merge(final Deque<Comparable> left, final Deque<Comparable> right) {
        final LinkedList<Comparable> merged = new LinkedList<>();
        while (!left.isEmpty() && !right.isEmpty()) {
            if (left.peek().compareTo(right.peek()) <= 0) {
                merged.add(left.pop());
            } else {
                merged.add(right.pop());
            }
        }
        merged.addAll(left);
        merged.addAll(right);
        return merged;
    }

    public void mergeSort(final LinkedList<Comparable> input) {
        if (input.size() != 1) {
            final LinkedList<Comparable> left = new LinkedList<Comparable>();
            final LinkedList<Comparable> right = new LinkedList<Comparable>();
            // boolean used to decide if we put elements
            // in left or right LinkedList
            boolean logicalSwitch = true;
            while (!input.isEmpty()) {
                if (logicalSwitch) {
                    left.add(input.pop());
                } else {
                    right.add(input.pop());
                }
                logicalSwitch = !logicalSwitch;
            }
            mergeSort(left);
            mergeSort(right);
            input.addAll(merge(left, right));
        }
    }
}

我使用了 Deque 因为 peek()/pop() 恕我直言，它比 get(0) 更漂亮> 和 remove(0) 但这取决于你。如果您绝对想使用ArrayList，请遵循相应的实现。

import java.util.ArrayList;
import java.util.List;

public class Example {

    private List<Comparable> merge(final List<Comparable> left, final List<Comparable> right) {
        final List<Comparable> merged = new ArrayList<>();
        while (!left.isEmpty() && !right.isEmpty()) {
            if (left.get(0).compareTo(right.get(0)) <= 0) {
                merged.add(left.remove(0));
            } else {
                merged.add(right.remove(0));
            }
        }
        merged.addAll(left);
        merged.addAll(right);
        return merged;
    }

    public void mergeSort(final List<Comparable> input) {
        if (input.size() != 1) {
            final List<Comparable> left = new ArrayList<Comparable>();
            final List<Comparable> right = new ArrayList<Comparable>();
            boolean logicalSwitch = true;
            while (!input.isEmpty()) {
                if (logicalSwitch) {
                    left.add(input.remove(0));
                } else {
                    right.add(input.remove(0));
                }
                logicalSwitch = !logicalSwitch;
            }
            mergeSort(left);
            mergeSort(right);
            input.addAll(merge(left, right));
        }
    }
}

两种实现都适用于Integer和String或其他Comparable。

希望有帮助。