Java實現數組排序

介紹

排序是程序設計中常用的算法之一。在現實生活中，很多問題都需要對數據進行排序，比如搜索引擎對搜索結果按相關性排序、股票交易中根據股票價格排序等。在 Java 中，對數組進行排序也是常見的操作，通常使用 Arrays 類中的 sort() 方法實現。本文將從多個方面介紹 Java 中數組排序的相關知識。

排序算法

排序算法是指將一組數據按照某個順序重新排列的過程，常見的排序算法有冒泡排序、選擇排序、插入排序、快速排序等。

冒泡排序

冒泡排序是一種簡單的排序算法，工作原理是通過相鄰元素之間的比較和交換，每次操作將數組中最大（或最小）的元素 “冒泡” 到最後（或最前）的位置。在實現冒泡排序時，通常使用雙重循環來遍曆數組中的元素：

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            // 如果前一個元素比後一個元素大，則交換兩個元素的位置
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

選擇排序

選擇排序的工作原理是搜索數組中最小值（或最大值），並將其放置在第一個位置；接着，在剩餘的數組中搜索第二小值（或第二大值），並將其放置在第二個位置；以此類推，直到整個數組排序完成。選擇排序的實現也很簡單，可以使用雙重循環進行：

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            // 找到最小元素的下標
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 將最小元素與第 i 個元素交換位置
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

插入排序

插入排序的工作原理是將未排序的元素插入到已排序好的子序列中，初始狀態下已排序的子序列只包含第一個元素。在遍曆數組過程中，將當前元素與已排序的子序列中的元素比較，找到該元素對應的位置並插入。插入排序同樣可以使用雙重循環進行：

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 將比 key 大的元素向右移動一位，空出 key 的位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 將 key 插入到正確的位置
        arr[j + 1] = key;
    }
}

快速排序

快速排序是一種比較高效的排序算法，其基本思路是通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字值均比另一部分記錄的關鍵字值小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。在實現快速排序時，通常使用遞歸方式進行：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivotIdx = partition(arr, left, right);
        quickSort(arr, left, pivotIdx - 1);
        quickSort(arr, pivotIdx + 1, right);
    }
}
private static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i++;
        }
    }
    int temp = arr[right];
    arr[right] = arr[i];
    arr[i] = temp;
    return i;
}

Arrays.sort() 方法

Java 提供了 Arrays 類，該類提供了許多操作數組的方法。其中的 sort() 方法可以對數組進行排序，sort() 方法使用快速排序算法實現。該方法的基本使用方式如下：

int[] arr = {4, 2, 9, 7};
Arrays.sort(arr);

如果要對數組按從大到小排序，可以使用 sort() 方法的重載版本，並傳入自定義的 Comparator 對象：

int[] arr = {4, 2, 9, 7};
Arrays.sort(arr, (a, b) -> b - a);

總結

本文介紹了 Java 中常見的數組排序算法，包括冒泡排序、選擇排序、插入排序和快速排序，並提供了每個算法的實現代碼。此外，也介紹了使用 Arrays 類的 sort() 方法對數組進行排序的方式。掌握了這些知識，讀者可以在實際項目中根據不同情況選擇合適的排序算法。