java - 合并排序不起作用

Question

我编写了一个程序，您可以在其中使用 3 种不同的排序方法对 ArrayList 进行排序:冒泡、合并和 bogo(或愚蠢排序)。这是代码:

import java.util.*;
import java.io.*;
import java.lang.*;
import java.lang.IndexOutOfBoundsException;

public class Sorting {

    public static void bubbleSort(ArrayList<Integer> bubble) {
        int temp;
        if (bubble.size() > 1) {
            for (int i = 0; i < bubble.size(); i++) {
                for (int j = 0; j < bubble.size() - i - 1; j++) {
                    if (bubble.get(i).compareTo(bubble.get(i + 1)) > 0) {
                        temp = bubble.get(i);
                        bubble.set(i, bubble.get(i + 1));
                        bubble.set(i + 1, temp);
                    }
                }
            }
        }
    }

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

            for (int i = 0; i < halfway; i++) {
                left.add(merge.get(i));
            }
            for (int i = halfway; i < merge.size(); i++) {
                right.add(merge.get(i));
            }

            left = mergeSort(left);
            right = mergeSort(right);

            ArrayList<Integer> newMerge = new ArrayList<Integer>(merge.size());

            int index1 = 0;
            int index2 = 0;

            for (int i = 0; i < merge.size(); i++) {
                if (index1 == left.size()) {
                    merge.set(i, right.get(index2));
                    index2++;
                } else if (index2 == right.size()) {
                    merge.set(i, left.get(index1));
                    index1++;
                } else {
                    if (left.get(index1) <= right.get(index2)) {
                        newMerge.set(i, left.get(index1));
                        index1++;
                    } else if (left.get(index1) >= right.get(index2)) {
                        newMerge.set(i, right.get(index2));
                        index2++;
                    }
                }
            }
            return newMerge;
        }
    }

    public static void bogoSort(ArrayList<Integer> bogo) {
        while (!isOrdered(bogo)) {
            Collections.shuffle(bogo);
        }
    }

    public static boolean isOrdered(ArrayList<Integer> order) {
        for (int i = 0; i < order.size(); i++) {
            if (order.get(i) > order.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        try {
            Scanner input = new Scanner(new File("random1.txt"));
            ArrayList<Integer> random = new ArrayList<Integer>();
            while (input.hasNextInt()) {
                random.add(input.nextInt());
            }
            input.close();

            System.out.println("Unsorted: " + random);

            long startTime = System.nanoTime();
            bubbleSort(random);
            long endTime = System.nanoTime();
            long duration = ((endTime - startTime) / 1000000);
            System.out.println("Sorted: " + random);
            System.out.println("Bubble sort took: " + duration + " milliseconds to sort.");
            System.out.println();

            long startTime2 = System.nanoTime();
            mergeSort(random);
            long endTime2 = System.nanoTime();
            long duration2 = ((endTime2 - startTime2) / 1000000);
            System.out.println("Sorted: " + random);
            System.out.println("Merge sort took: " + duration2 + " milliseconds to sort.");
            System.out.println();

            long startTime3 = System.nanoTime();
            bogoSort(random);
            long endTime3 = System.nanoTime();
            long duration3 = ((endTime3 - startTime3) / 1000000);
            System.out.println("Sorted: " + random);
            System.out.println("Bogo sort took: " + duration3 + " milliseconds to sort.");
            System.out.println();
        } catch (FileNotFoundException e) {
            System.out.println("File is not found.");
            System.exit(1);
        }
    }
}

当我运行该程序时，出现了未排序的 ArrayList 和冒泡排序方法，但我的合并排序方法收到错误，指出我在第 38、57 和 102 行有一个 IndexOutOfBoundsException。我正确地执行了算法但我不知道为什么会收到错误消息。这背后有什么推理吗？

Answer 1

对于列表，如果索引大于大小，则不能在特定索引处添加或设置元素。查看文档 here .您可以将空值添加到您的 List(newMerge) 以解决此问题，或者只需将元素添加到您的 newMerge 列表。我更喜欢以后。其他IndexOutOfBoundsException 异常与此相关。