ArrayList排序的詳解

在Java編程中，ArrayList是一個迭代器，它可以動態地添加和刪除數據。在處理數據時，我們有時需要將數據進行排序。在這篇文章中，我們將從多個方面對ArrayList進行排序進行詳細的闡述。

一、選擇排序

選擇排序是一種簡單的排序算法。遍曆數組，不斷的找到數組中的最小值，並將這個最小值放在第一個位置，接着在剩餘的未排序的數組中繼續找到最小值並放在第二個位置……以此類推，直至整個數組排序完成。這個過程就叫做選擇排序。

public void selectionSort(ArrayList arr) {
    for (int i = 0; i < arr.size() - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr.get(j) < arr.get(minIndex)) {
                minIndex = j;
            }
        }
        int temp = arr.get(i);
        arr.set(i, arr.get(minIndex));
        arr.set(minIndex, temp);
    }
}

選擇排序的時間複雜度是O(n^2)，不適用於大數據量的排序。

二、冒泡排序

冒泡排序是一種基礎的排序方法，它不斷地交換元素位置，每次遍曆數組都將相鄰兩個元素進行比較，如果前一個元素大於後一個元素，就將這兩個元素交換位置。這樣一次遍歷完成以後，最大的元素就被移到了數組最後一個位置。重複這個過程，直到排序完成。

public void bubbleSort(ArrayList arr) {
    for (int i = 0; i < arr.size() - 1; i++) {
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr.get(j) < arr.get(i)) {
                int temp = arr.get(i);
                arr.set(i, arr.get(j));
                arr.set(j, temp);
            }
        }
    }
}

冒泡排序的時間複雜度是O(n^2)，和選擇排序一樣，不適用於大數據量的排序。

三、快速排序

快速排序是目前應用最廣泛的排序算法之一。其基本思想是從數組中選擇一個基準元素，將小於基準元素的數放到左邊，大於基準元素的數放到右邊。經過一次排序後，基準元素位於中間，並且左邊的數都小於基準元素，右邊的數都大於基準元素。接着，對左邊的數和右邊的數分別進行快速排序，直到整個數組排序完成。

public void quickSort(ArrayList arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr.get(left);
    int i = left;
    int j = right;
    while (i < j) {
        while (i = pivot) {
            j--;
        }
        if (i < j) {
            arr.set(i, arr.get(j));
            i++;
        }
        while (i < j && arr.get(i) < pivot) {
            i++;
        }
        if (i < j) {
            arr.set(j, arr.get(i));
            j--;
        }
    }
    arr.set(i, pivot);
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

快速排序的時間複雜度是O(nlogn)，相對於選擇排序和冒泡排序，快速排序在大數據量的排序中表現更加優秀。

四、歸併排序

歸併排序，是一種採用分治法的排序算法。其基本思想是將一個大數組分成若干個小數組，對這些小數組進行排序後進行合併。合併時將兩個已排序的小數組合併成一個有序的大數組，依次進行合併，直到整個數組排序完成。

public void mergeSort(ArrayList arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
private void merge(ArrayList arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (arr.get(i) < arr.get(j)) {
            temp[k++] = arr.get(i++);
        } else {
            temp[k++] = arr.get(j++);
        }
    }
    while (i <= mid) {
        temp[k++] = arr.get(i++);
    }
    while (j <= right) {
        temp[k++] = arr.get(j++);
    }
    for (int m = 0; m < temp.length; m++) {
        arr.set(left + m, temp[m]);
    }
}

歸併排序的時間複雜度也是O(nlogn)，和快速排序一樣，是目前被廣泛應用的排序算法之一。

五、總結

本篇文章從選擇排序、冒泡排序、快速排序和歸併排序四個方面詳細闡述了ArrayList排序的基礎知識。在排序算法中，每種算法均有其適用的範圍和優劣勢，需要按照特定的需求適時的選擇不同的排序算法。