java - 合并排序实现java

我正在尝试实现自己的Mergesort函数，但是很难弄清什么不起作用。

我为UnSorted：[6, 1, 2, 7, 2, 3, 9, 7, 6]获得的输出是Sorted：[2, 3, 6, 1, 2, 7]

这是我到目前为止的内容：

public class mergeSort {

    public static void main(String[] args) {
        List<Integer> l = new ArrayList<Integer>();
        Random rd = new Random();

        for (int i = 1; i < 10; i++) {
            l.add(rd.nextInt(10) + 1);
        }

        System.out.println("UnSorted: " + l);
        msort(l);
        System.out.println("Sorted: "+msort(l));
    }

    public static List<Integer> msort(List<Integer> l) {
        if (l.size() <= 1) {
            return l;
        }

        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();

        for (int i = 0; i < (l.size() / 2); i++) {
            left.add(l.get(i));
        }
        for (int i = l.size() / 2; i < l.size(); i++) {
            right.add(l.get(i));
        }

        msort(left);
        msort(right);
        //System.out.println(left + "" +right);

        return join(left,right);
    }

    public static List<Integer> join(List<Integer> left, List<Integer> right) {
        /*if (right.size() == 0) {
            return left;
        }
        if (left.size() == 0) {
            return right;
        }*/

        List<Integer> fin = new ArrayList<Integer>();
        // pointers
        int lp = 0, rp = 0, fp = 0;

        while (lp < left.size() && rp < right.size()) {
            if (left.get(lp) < right.get(rp)) {
                fin.add(left.get(lp));
                lp++;
            } else {
                fin.add(right.get(rp));
                rp++;
            }
            fp++;
        }
        return fin;
    }
}

最佳答案

您的代码有几个问题。您的方法虽然正确


在join方法中，由于使用while循环，您将一些元素保留在列表中

lp
它将循环播放，直到其中一个列表已添加到fin中，而其他列表中可能仍剩余一些元素。因此，您还需要两个循环来适应此问题：

while(lp < left.size()) {
    fin.add(left.get(lp++));
}
while(rp < right.size()) {

    fin.add(right.get(rp++));
}

您的msort方法中也存在问题，您没有使用msort的返回值，因此您需要这样做：

左= msort（左）;

正确= msort（正确）;


希望这可以帮助。