在 Java 中使用 ArrayList 进行合并排序
本教程介绍了在 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
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn