Java归并排序算法输出随机值，无法正确排序ArrayList求助

问题根源 #

你的代码核心错误出在合并阶段：每次合并时，直接向原numbers列表追加排序后的元素，但未清空原列表里的未排序元素。这导致原列表同时保留了初始未排序元素和新添加的排序元素，最终输出是旧元素+新排序元素的混合，看起来像是“随机输出”。

另外，mid的计算可以简化——Java中整数除法numbers.size()/2本身就会向下取整，不需要额外判断奇偶或调用Math.floor。

修正后的代码 #

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){
        if (numbers.size()>1){
            // 简化mid计算，整数除法自动向下取整
            int mid = numbers.size() / 2;
            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);
            
            // 合并前先清空原列表的旧元素
            numbers.clear();
            
            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++;
                }else{
                    numbers.add(right.get(j));
                    j++;
                }
            }
            while (i<left.size()){
                numbers.add(left.get(i));
                i++;
            }
            while (j<right.size()){
                numbers.add(right.get(j));
                j++;
            }
        }
    }        
}

关键修改点 #

• 合并两个子列表前，调用numbers.clear()清空原列表的旧元素，确保后续添加的是完全排序后的元素。
• 简化mid的计算逻辑，去掉冗余的奇偶判断和Math.floor调用，直接用numbers.size()/2即可。

内容的提问来源于stack exchange，提问作者A Tong