在 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