在 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