用于ArrayLists的Java递归MergeSort

Question

我的mergesort函数一直存在问题,因为我无法在将其输入程序时对一系列整数或字符串进行排序.我有一个调用项目的外部类,但它根本不对数字/字符串进行排序.下面两种方法,我不知道问题出在哪里.数字是随机输入的.

码:

/**
     * 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

我有一个调用项目的外部类,但它根本不对数字/字符串进行排序.下面两种方法,我不知道问题出在哪里.

第一个问题是,如果你打电话给你的mergeSort方法有first = 0和last = a.size()你只叫你不会排序什么merge,如果last-first == 1:

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;
    }
}

从这一点来说,我不知道你是如何尝试实现Merge Sort算法的.它既不是自上而下,也不是自下而上的实现.你在merge方法中分裂,这也很奇怪.如果您提供了伪代码+调用public方法的方式,那么帮助您会更容易.恕我直言,你的算法有一个真正的问题.

实际上,合并排序算法实现起来非常简单.为了说明这一点,我使用而不是对象编写了这种自顶向下的合并排序算法实现:DequeList

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.

希望能帮助到你.

Answer 2

有几个问题，但是一个重要的问题是，在修改列表时，您不应遍历列表，例如：

for (i = 0; i < a.size() - mid; i++){
    left.add(i,a.get(i));
    a.remove(i);
}

因为一旦删除一个元素，其他元素的索引就不一样了...因此，添加该left元素a并不是您的想法。

以下是有效的代码（带有一些注释）：

 private static void merge(ArrayList<Comparable> a) {
    if (a.size()<=1) return; // small list don't need to be merged

    // SEPARATE

    int mid = a.size()/2; // estimate half the size

    ArrayList<Comparable> left = new ArrayList<Comparable>();
    ArrayList<Comparable> right = new ArrayList<Comparable>();

    for(int i = 0; i < mid; i++) left.add(a.remove(0)); // put first half part in left
    while (a.size()!=0) right.add(a.remove(0)); // put the remainings in right
    // Here a is now empty

    // MERGE PARTS INDEPENDANTLY

    merge(left);  // merge the left part
    merge(right); // merge the right part

    // MERGE PARTS

    // while there is something in the two lists
    while (left.size()!=0 && right.size()!=0) {
      // compare both heads, add the lesser into the result and remove it from its list
      if (left.get(0).compareTo(right.get(0))<0) a.add(left.remove(0));
      else                                       a.add(right.remove(0));
    }

    // fill the result with what remains in left OR right (both can't contains elements)
    while(left.size()!=0)  a.add(left.remove(0));
    while(right.size()!=0) a.add(right.remove(0));
  }

已经在一些输入上进行了测试...示例：

[4, 7, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11]
[0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

为了提高效率，您可以使用subList方法来避免显式构造过多的子列表，这需要注意索引。