java - Java中ArrayList的归并排序

Question

我正在学习如何用Java实现基本算法，所以我是这个环境的新手。我正在尝试使用 ArrayList 实现合并排序算法，其中程序将从文件中读取数据(每行中的整数)并使用合并排序生成排序结果。但是，我的代码显示了相同的结果，因为它没有解决任何问题!如果有人能指出我在哪里犯了错误，我将非常高兴。由于我是初学者，代码非常简单，没有优化，而且性能可能不是很快。

这是我的代码:

public class MergeSortExp1 {

    public static void main(String[] args) {

        ArrayList<Integer>number = new ArrayList<Integer>();

        Scanner myScanner = null;
        try {
        myScanner = new Scanner(new File("/Users/Sabbir/Desktop/workload.txt"));
        } catch (FileNotFoundException e) {

        e.printStackTrace();
        }

        while(myScanner.hasNextInt()){
            number.add(myScanner.nextInt());
        }

        System.out.println("Before sorting" +number);
        number=mergeSort(number);
        System.out.println("Sorted Array =" +number);
    }

        public static ArrayList<Integer> mergeSort( ArrayList<Integer> Input)
        {
            if (Input.size() ==1){
                return Input;
            }
            else {
                int mid= Input.size()/2;
                ArrayList<Integer> left= new ArrayList<Integer>(mid);
                ArrayList<Integer> right=new ArrayList<Integer>(Input.size()-mid);

               for (int i = 0; i < mid; i++) {
                   left.add(Input.get(i));
                   } 

               for (int i = 0; i < Input.size()-mid; i++) {
                   right.add(Input.get(i));
               } 

               left=mergeSort(left); 
               right=mergeSort(right);
               merge(left,right,Input);
            }
               return Input;
        }


        public static void merge (ArrayList<Integer>left,ArrayList<Integer>right,ArrayList<Integer>Input)
        {
            int i1=0;// left Index
            int i2=0;// right Index
            int InputIndex=0;

            for (int i = 0; i < Input.size(); i++) {
                if (i2>=right.size() || (i1<left.size() && left.get(i)<=right.get(i))) 
                {
                    Input.set(InputIndex,left.get(i1));
                    InputIndex++;
                }
                else {
                    Input.set(InputIndex, right.get(i2));
                    InputIndex++;
                }
            }

        }
}

Answer 1

如果你的合并方法没问题(我没有测试)，你忘记合并左右输入，请编辑你的代码，如下所示，然后重试:

 // This is called recursion. Calling a method again within the  
 //method until the value of left and right becomes 1.
 left=mergeSort(left); 
 right=mergeSort(right);

 merge(left,right,Input);

希望对你有帮助!