在 Java 中使用 ArrayList 進行合併排序

Rupam Yadav 2022年5月1日
在 Java 中使用 ArrayList 進行合併排序

本教程介紹了在 Java 中使用 ArrayList 執行合併排序所需的步驟。合併排序使用分治法對陣列或 ArrayList 中的專案進行排序。

在 Java 中使用 ArrayList 進行合併排序

我們需要兩個函式來執行歸併排序;第一個功能是將我們要排序的 ArrayList 分成兩半,即我們將 ArrayList 從中間分開,然後呼叫自身,直到它們完全分開。

第二種方法是將分割的元素合併成一個單一的 ArrayList。這是我們得到排序的 ArrayList 的時候。

在下面的例子中,我們建立了一個名為 arrayToSortArrayList 例項,它儲存整數值。我們在 ExampleClass1 建構函式中初始化列表。

現在我們建立兩個方法,divideArrayElements()mergeArrayElements

divideArrayElements()indexStartindexEnd 作為引數來標識從哪個索引開始以及在哪裡結束。在方法內部,我們檢查 indexStart 是否小於 indexEnd 以及它們的差是否不大於 1。

在條件語句中,我們使用 (indexEnd + indexStart) / 2 獲得 ArrayList 的中間元素,它將 ArrayList 分成兩半。

現在通過呼叫 divideArrayElements() 劃分已經劃分的 ArrayList,並將 indexStart 作為起始索引,將 middleElement 作為結束索引。

這樣做是為了打破分割的 ArrayList。為了分割後半部分,我們再次呼叫 divideArrayElements() 方法並將 middleElement + 1 作為其開始索引和 indexEnd

請注意,我們正在遞迴呼叫 divideArrayElements() 方法。下一步是通過呼叫方法 mergeArrayElements() 對分割後的 ArrayList 元素進行合併和排序,在該方法中我們傳遞開始索引、中間索引和結束索引。

mergeArrayElements() 函式中,我們建立了一個臨時合併元素的 ArrayList。然後我們需要左索引和右索引來知道合併元素的起點和終點。

我們使用一個迴圈,直到 getLeftIndexgetRightIndex 小於 indexMiddleindexEnd

現在在迴圈中,我們檢查 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
Author: Rupam Yadav
Rupam Yadav avatar Rupam Yadav avatar

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

相關文章 - Java ArrayList