迹忆客 专注技术分享

本教程介绍了在 Java 中使用 ArrayList 执行合并排序所需的步骤。合并排序使用分治法对数组或 ArrayList 中的项目进行排序。

在 Java 中使用 ArrayList 进行合并排序

我们需要两个函数来执行归并排序；第一个功能是将我们要排序的 ArrayList 分成两半，即我们将 ArrayList 从中间分开，然后调用自身，直到它们完全分开。

第二种方法是将分割的元素合并成一个单一的 ArrayList。这是我们得到排序的 ArrayList 的时候。

在下面的例子中，我们创建了一个名为 arrayToSort 的 ArrayList 实例，它保存整数值。我们在 ExampleClass1 构造函数中初始化列表。

现在我们创建两个方法，divideArrayElements() 和 mergeArrayElements。

divideArrayElements() 将 indexStart 和 indexEnd 作为参数来标识从哪个索引开始以及在哪里结束。在方法内部，我们检查 indexStart 是否小于 indexEnd 以及它们的差是否不大于 1。

在条件语句中，我们使用 (indexEnd + indexStart) / 2 获得 ArrayList 的中间元素，它将 ArrayList 分成两半。

现在通过调用 divideArrayElements() 划分已经划分的 ArrayList，并将 indexStart 作为起始索引，将 middleElement 作为结束索引。

这样做是为了打破分割的 ArrayList。为了分割后半部分，我们再次调用 divideArrayElements() 方法并将 middleElement + 1 作为其开始索引和 indexEnd。

请注意，我们正在递归调用 divideArrayElements() 方法。下一步是通过调用方法 mergeArrayElements() 对分割后的 ArrayList 元素进行合并和排序，在该方法中我们传递开始索引、中间索引和结束索引。

在 mergeArrayElements() 函数中，我们创建了一个临时合并元素的 ArrayList。然后我们需要左索引和右索引来知道合并元素的起点和终点。

我们使用一个循环，直到 getLeftIndex 和 getRightIndex 小于 indexMiddle 和 indexEnd。

现在在循环中，我们检查 tempArray 中元素的值是否在左侧索引上小于右侧索引，如果是，则将左侧索引上的值添加到 ArrayList 中，并且增加 getLeftIndex 值。

如果左索引大于右索引，我们在列表中插入右索引值。

我们还创建了两个单独的循环来检查左侧索引是否小于中间索引，另一个循环来检查右侧索引是否小于结束索引。最后，我们将临时的 ArrayList 设置为 arrayToSort 列表。

我们在 main() 方法中创建列表来排序和插入一些值。我们创建一个 ExampleClass1 类的对象，并在其构造函数中传递列表。

使用返回列表的 getArrayAfterSorting() 来获取 ArrayList。第一个输出显示调用 divideArrayElements() 之前的列表，第二个输出显示排序后的列表。

import java.util.ArrayList;

public class ExampleClass1 {
    private final ArrayList<Integer> arrayToSort;

    public ExampleClass1(ArrayList<Integer> arrayToSort) {
        this.arrayToSort = arrayToSort;
    }

    public ArrayList<Integer> getArrayAfterSorting() {
        return arrayToSort;
    }

    public void divideArrayElements(int indexStart, int indexEnd) {

        if (indexStart < indexEnd && (indexEnd - indexStart) >= 1) {
            int middleElement = (indexEnd + indexStart) / 2;

            divideArrayElements(indexStart, middleElement);
            divideArrayElements(middleElement + 1, indexEnd);

            mergeArrayElements(indexStart, middleElement, indexEnd);
        }
    }

    public void mergeArrayElements(int indexStart, int indexMiddle, int indexEnd) {

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

        int getLeftIndex = indexStart;
        int getRightIndex = indexMiddle + 1;

        while (getLeftIndex <= indexMiddle && getRightIndex <= indexEnd) {

            if (arrayToSort.get(getLeftIndex) <= arrayToSort.get(getRightIndex)) {

                tempArray.add(arrayToSort.get(getLeftIndex));
                getLeftIndex++;

            } else {

                tempArray.add(arrayToSort.get(getRightIndex));
                getRightIndex++;

            }
        }

        while (getLeftIndex <= indexMiddle) {
            tempArray.add(arrayToSort.get(getLeftIndex));
            getLeftIndex++;
        }

        while (getRightIndex <= indexEnd) {
            tempArray.add(arrayToSort.get(getRightIndex));
            getRightIndex++;
        }


        for (int i = 0; i < tempArray.size(); indexStart++) {
            arrayToSort.set(indexStart, tempArray.get(i++));

        }

    }

    public static void main(String[] args) {
        ArrayList<Integer> integerArrayList = new ArrayList<>();
        integerArrayList.add(23);
        integerArrayList.add(44);
        integerArrayList.add(12);
        integerArrayList.add(3);
        integerArrayList.add(76);

        ExampleClass1 exampleClass1 = new ExampleClass1(integerArrayList);

        System.out.println("Array Before Merge Sort: ");
        for (Integer integer : exampleClass1.getArrayAfterSorting()) {
            System.out.println(integer);
        }

        System.out.println();

        exampleClass1.divideArrayElements(0, integerArrayList.size() - 1);

        System.out.println("Array After Merge Sort: ");
        for (Integer integer : exampleClass1.getArrayAfterSorting()) {
            System.out.println(integer);
        }


    }
}

输出：

Array Before Merge Sort:
23
44
12
3
76

Array After Merge Sort:
3
12
23
44
76