Java 中的错误 MergeSort

Question

我正在使用 List 和 ArrayList 类的动态数组。我认为错误是 merge 方法，但我不知道哪里出了问题。我在 JS 和 Python 中使用了 "same" 代码，一切都按照预期进行。

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

public class mergeS {

    private static List<Integer> numbers = new ArrayList<Integer>();
    private static int lon = 8;

    public static void main(String[] args) {
        long start, end;
        float time;
        for(int i = 0; i < lon; i++) {
            if(Math.random() < 0.5) {
                numbers.add((int)(Math.random()*(100)));
            }else {
                numbers.add((int)(-1*Math.random()*(100)));
            }
        }
        System.out.println("Unsorted list:\n"+numbers+"\n");
        start = System.nanoTime();
        mergeSort(numbers);
        end = System.nanoTime();
        time = (float) ((end-start)/Math.pow(10, 9));
        System.out.println("Sorted list:\n"+numbers);
        System.out.println("The time used was: "+time);
    }

    private static void mergeSort(List<Integer> numbers) {
        if (numbers.size() < 2) {
            return;
        }
        int mid = numbers.size() / 2;
        List<Integer> left = numbers.subList(0, mid);
        List<Integer> right = numbers.subList(mid, numbers.size());
        mergeSort(left);
        mergeSort(right);
        merge(left, right, numbers);
    }

    private static void merge(List<Integer> left, 
                            List<Integer> right, 
                            List<Integer> numbers) {
        int i = 0, j = 0, k = 0;
        while(i < left.size() && j < right.size()) {
            if(left.get(i) <= right.get(j)) {
                numbers.set(k, left.get(i));
                i++;
            }else {
                numbers.set(k, right.get(j));
                j++;
            }
            k++;
        }
        while(i < left.size()) {
            numbers.set(k, left.get(i));
            i++;
            k++;
        }
        while(j < right.size()) {
            numbers.set(k, right.get(j));
            j++;
            k++;
        }
    }

}

Answer 1

您的代码很好，您只是错过了 List.subList 没有为您创建新对象。它只是 returns 对同一个 numbers 数组的引用。一旦你更换

    List<Integer> left = numbers.subList(0, mid);
    List<Integer> right = numbers.subList(mid, numbers.size());

与

    List<Integer> left = new ArrayList<Integer>( numbers.subList( 0, mid ) );
    List<Integer> right = new ArrayList<Integer>( numbers.subList( mid, numbers.size() ) );

一切都很顺利。

Java 中的错误 MergeSort

Bugged MergeSort in Java

java

mergesort