在 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