为什么 Java 中的合并排序算法打印随机输出而不对 Arraylist 进行排序？

Question

我正在尝试在 Java 中实现合并排序算法，但可能由于递归错误而不断获得随机输出。以下是导致问题的代码。

谢谢。

import java.util.ArrayList;
import java.util.Collections;

public class Merging {
    private static ArrayList<Integer> numbers = new ArrayList<Integer>();
    public static void main(String[] args) {
        Collections.addAll(numbers,7,6,3,1,9,8);
        mergeSort(numbers);
        for (int x: numbers){
            System.out.println(x);
        }
    }
    public static void mergeSort(ArrayList<Integer> numbers){
        // System.out.println(numbers.size());
        if (numbers.size()>1){
            int mid = (numbers.size()%2==0 ? numbers.size()/2 : ((int)Math.floor(numbers.size()/2)));
            //System.out.println(mid);
            ArrayList<Integer> left=new ArrayList<Integer>();
            ArrayList<Integer> right=new ArrayList<Integer>();
            for (int i=0;i<mid;i++){
                left.add(numbers.get(i));
            }
            for (int i=mid;i<numbers.size();i++){
                right.add(numbers.get(i));
            }
            mergeSort(left);
            mergeSort(right);
            int i,j;
            i=j=0;
            while (i<left.size() && j<right.size()){
                if (left.get(i)<=right.get(j)){
                    numbers.add(left.get(i));
                    i+=1;
                }else{
                    numbers.add(right.get(j));
                    j+=1;
                }
            }
            while (i<left.size()){
                numbers.add(left.get(i));
                i+=1;
            }
            while (j<right.size()){
                numbers.add(right.get(j));
                j+=1;
            }
        }
    }        
}`

我试过以几种方式修改 mid 变量并记录输出，但没有任何帮助解决它。

Answer 1

所以有几件事让你绊倒了。合并排序算法很棒，因为它在大 O 方面是最优的，并且可以就地完成。无需为了执行算法而复制数组的内容。在您的代码中，您将原始数组中的元素复制到左侧和右侧，并对它们执行合并排序。不要那样做。要么切换到在合并排序方法中使用开始和结束。像这样：

void mergeSort(List<Integer> numbers) {
   mergeSort( numbers, 0, numbers.size() );
}
void mergeSort(List<Integer> numbers, int start, int end) {
   ...
}

或者，如果您想继续左右操作，请改用

List.subList

。这将创建一个新的 List，其行为类似于 List，但它不是基础数据的副本。在内存方面要便宜得多（并且大多数情况下可以接受并且仍然符合就地条件）。

在合并它们之前，您也没有删除列表的元素。因此，该算法通过向列表中添加更多元素来增加数组。您需要使用

List.set( int index, E element)

来覆盖列表中的内容。您可以使用任一建议（即

set

或开始/结束）调用

subList

，并修改基础列表。

我建议在每次调用 mergeSort 时打印出数组，这样您就可以看到算法在做什么：

public void printArray( List<Integer> arr ) {
   System.out.print("[ ");
   boolean first = true;
   for( Integer i : arr ) {
      if( !first ) print(", ")
      System.out.print( i );
      first = false;
   }
   System.out.println(" ]");
}

还要了解

java.util.List

和

java.util.ArrayList

之间的关系，并尽可能有效地使用

List

（几乎无处不在）。这不是合并排序的事情，而是理解 Java 的重要一步。