ArrayList 的 Java 递归合并排序

Java Recursive MergeSort for ArrayLists

提问by Jean-Baptiste Yunès

I have been having a problem with my mergesort function, as I am not able to sort a series of integers or strings whenever inputting it into the program. 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. Numbers are randomly inputted.

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

CODE:

代码：

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


                }

回答by Kraal

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.

我有一个外部类，可以将项目调用到其中，但是它根本不会对数字/字符串进行排序。下面是两种方法，不知道问题出在哪里。

The first problem is that if you call your mergeSortmethod with first = 0and last = a.size()you won't sort anything as you only call mergeif last-first == 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;
    }
}

Appart from this point, I don't get how you're trying to implement the Merge Sort algorithm. It's neither a top down, nor a bottom up implementation. You're splitting inside the merge method which is also really odd. It would have been easier to help you if you had provided your pseudo code + the way you call your publicmethod. IMHO you have a real issue with your algorithm.

从这一点来看，我不明白你是如何尝试实现合并排序算法的。它既不是自上而下，也不是自下而上的实现。你在合并方法中分裂，这也很奇怪。如果您提供了伪代码 + 调用public方法的方式，那么帮助您会更容易。恕我直言，你的算法有一个真正的问题。

In fact the merge sort algorithm is really simple to implement. To illustrate this, I wrote this top down implementation of the merge sort algorithmusing Dequeinstead of Listobjects:

事实上，归并排序算法实现起来非常简单。为了说明这一点，我使用而不是对象编写了这个合并排序算法的自顶向下实现：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));
        }
    }
}

I used Dequebecause peek()/ pop()is ways prettier IMHO than get(0)and remove(0)but it's up to you. If you absolutely want to use ArrayListhere follows the corresponding implementation.

我使用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));
        }
    }
}

Both implementation work with Integerand Stringor other Comparable.

两种实现都与Integer和String或其他一起使用Comparable。

Hope it helps.

希望能帮助到你。

回答by Jean-Baptiste Yunès

There are several problems but an important one is that you should not iterate over a list while modifying the list, i.e. in:

有几个问题，但一个重要的问题是你不应该在修改列表时迭代列表，即：

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

because once you remove an element, indexes for others are not the same... So you add in leftelements of athat are not what you think.

因为一旦你删除了一个元素，其他元素的索引就不一样了......所以你添加的left元素a不是你想的那样。

A working code is the following (with some comments) :

工作代码如下（有一些注释）：

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

It has been tested on some inputs... Example:

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

[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]

For efficiency you may use subListmethod to avoid constructing too much sub lists explicitly, it will need to take care about indices.

为了提高效率，您可以使用subListmethod 来避免显式构建过多的子列表，它需要注意索引。

回答by HippoMano

A WARNING about Kraal's implementation that got the checkmark. It's a great implementation, but Kraal's Merge sort doesn't preserve the relative order of items that have the same value, which in some cases, when sorting objects for instance, is an important strength that merge sort has that other sorting algorithms, like quicksort, do not have. I modified Kraal's code to preserve relative orders.

有关 Kraal 实施的警告，已获得复选标记。这是一个很好的实现，但是 Kraal 的合并排序不会保留具有相同值的项目的相对顺序，在某些情况下，例如在对对象进行排序时，这是合并排序具有其他排序算法（如快速排序）的重要优势， 没有。我修改了 Kraal 的代码以保留相对顺序。

private static List<Object> merge(final List<Object> left, final List<Object> right) {
            printArr("left", left);
            printArr("Right", right);
            final List<Object> merged = new ArrayList<>();
            while (!left.isEmpty() && !right.isEmpty()) {
                if(left.get(0).getValue()-right.get(0).getValue() <= 0){
                    merged.add(left.remove(0));
                } else {
                    merged.add(right.remove(0));
                }
            }
            merged.addAll(left);
            merged.addAll(right);
            return merged;
     }

 public static void mergeSort(final List<Object> input) {
     if (input.size() > 1) {
         final List<Object> left = new ArrayList<Object>();
         final List<Object> right = new ArrayList<Object>();
         boolean logicalSwitch = true;

         while (!input.isEmpty()) {
             if (logicalSwitch) {
                 left.add(input.remove(0));
             } else {
                 right.add(input.remove(input.size()/2));
             }
             logicalSwitch = !logicalSwitch;
         }
         mergeSort(left);
         mergeSort(right);
         input.addAll(merge(left, right));
     }
 }

回答by Mikhailov Valentine

If you want to sort an array using Merge sort, and not to implement a sorting algorithm by yourself, I recommend using standard Java sorting algorithms because it implements "Merge sort" algorithm for non primitive types.

如果您想使用合并排序对数组进行排序，而不是自己实现排序算法，我建议使用标准 Java 排序算法，因为它为非原始类型实现了“合并排序”算法。

Collections.sort();

If you would like to implement your own version of Merge sort then you should look first at this implementation.

如果您想实现您自己的合并排序版本，那么您应该首先查看此实现。

And if you are interested in better understanding sorting algorithms I recommend this book.

如果你有兴趣更好地理解排序算法，我推荐这本书。

回答by Prashant Rana

public class MergeSort{
    public void sort(List<Integer> list){
        sortAndMerge(list, 0, list.size()-1);
    }

    public void sortAndMerge(List<Integer> list, int start, int end){
        if((end - start) >= 2){
            int mid = (end - start)/2;
            sortAndMerge(list, start, start + mid);
            sortAndMerge(list, start + mid +1, end);

            int i=start;
            int j=start + mid +1;
            while(i<j && j<=end){
                if(list.get(i) > list.get(j)){
                    list.add(i, list.remove(j));
                    i++;
                    j++;
                }else if(list.get(i) == list.get(j)){
                    list.add(i+1, list.remove(j));
                    i++;
                    j++;
                }else{
                    i++;
                }
            }  

        }else{
            if(end > start){
                if(list.get(start) > list.get(end)){
                    int endValue = list.remove(end);
                    list.add(start, endValue);
                }                
            }
        }
    }