常見的排序算法：冒泡、快排、歸并、計數

冒泡排序：

時間復雜度：O(n^2)

冒泡排序就像水里的氣泡一樣，輕的氣泡會一點一點地浮到水面。在這個算法中，我們將待排序的元素比喻成氣泡，通過比較相鄰元素的值，讓較大的元素慢慢“浮”到數組的末端。

具體步驟如下：

比較相鄰的兩個元素，如果前一個比后一個大（假設我們要從小到大排序），就交換它們的位置。
對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。
針對所有的元素重復以上的步驟，除了最后已經排序好的元素。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 外層循環控制排序輪數，每輪將最大的元素移動到正確的位置
    for (int i = 1; i < arr.length; i++) {
        boolean swap = false;// 設置一個標志，用于判斷本輪是否發生了交換
        // 內層循環進行相鄰元素的比較和交換
        for (int j = 0; j < arr.length - i; j++) {
            // 交換大小數
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                swap = true;
            }
        }
        // 如果一輪比較下來沒有發生交換，說明數組已經有序，可以退出循環
        if (!swap) {
            break;
        }
    }
}

快速排序：

時間復雜度：O(n log n) - O(n^2)

快速排序的思想是找一個基準值（pivot），將數組分為兩部分，左邊都比基準值小，右邊都比基準值大。然后對這兩部分再遞歸地進行同樣的操作。

具體步驟如下：

選擇一個基準值，通常是數組的中部或最后一個元素。
將數組分為兩部分，小于基準值的元素放到左邊，大于基準值的元素放到右邊。
對左右兩個子數組重復步驟1和2，直到每個子數組的元素數量不超過1。

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }
    // 使用三數取中法選擇基準值，避免最壞情況的發生
    int mid = (start + end) >> 1;
    int pivot = Math.max(Math.min(arr[start], arr[mid]), Math.min(Math.max(arr[start], arr[mid]), arr[end]));

    int l = start - 1, r = end + 1;
    // 雙指針遍歷，找到小于和大于基準值的元素并進行交換
    do {
        while (arr[++l] < pivot) ;// L向右遍歷，找到大于或等于基準值的元素
        while (arr[--r] > pivot) ;// R向左遍歷，找到小于或等于基準值的元素
        if (l < r) {
            // L < R：交換大小數
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
    } while (l < r);// R ≤ L：說明arr已完整遍歷，跳出循環
    // 對子數組進行遞歸排序
    quickSort(arr, start, l - 1);
    quickSort(arr, r + 1, end);
}

歸并排序：

時間復雜度：O(n log n)

歸并排序是采用分治法的一個非常典型的應用。它的思想是將數組分成若干個小數組，對每個小數組進行排序，然后將小數組合并成較大的數組，直到最后只有一個排序完成的大數組。

具體步驟如下：

把數組分成若干個小數組，直到每個小數組只有一個元素。
將相鄰的小數組合并成較大的數組，合并時對數組進行排序。
重復步驟2，直到最后只有一個排序完成的大數組。

public static int[] mergeSort(int[] arr, int start, int end) {
    if (start >= end) {
        return new int[]{arr[start]};
    }
    // 計算左子數組的末尾位置
    int endL = (start + end) >> 1;
    // 對兩個子數組進行遞歸排序
    int[] lArr = mergeSort(arr, start, endL);
    int[] rArr = mergeSort(arr, endL + 1, end);

    int k = 0, i = 0, j = 0;
    int[] newArr = new int[end - start + 1];
    // 當兩個子數組都還有元素時，比較并放入較小的元素到新數組
    while (i < lArr.length && j < rArr.length) {
        newArr[k++] = lArr[i] < rArr[j] ? lArr[i++] : rArr[j++];
    }
    // 如果子數組還有剩余元素，將其復制到新數組
    System.arraycopy(lArr, i, newArr, k, lArr.length - i);
    k += lArr.length - i;
    System.arraycopy(rArr, j, newArr, k, rArr.length - j);
    return newArr;
}

計數排序：

時間復雜度：O(n + k)

計數排序是一種簡單的排序算法，它的工作原理是數一數每個元素在數組中出現的次數。然后，根據這些計數，將元素按照順序重新排列到另一個數組中。這種方法特別適用于整數排序，尤其是當整數的范圍不是很大時。

public static void countingSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 找出數組中的最大值和最小值
    int min = arr[0], max = arr[0];
    for (int i : arr) {
        max = Math.max(max,i);
        min = Math.min(min,i);
    }
    // 計算每個元素的個數，放入計數數組
    int[] ints = new int[max - min + 1];
    for (int i : arr) {
        ints[i - min]++;
    }
    // 重建排序后的數組
    for (int i = 0, j = 0; i < ints.length; i++) {
        while (ints[i]-- > 0) {
            arr[j++] = min + i;
        }
    }
}

總結：

每種排序算法各有特點，冒泡排序簡單但效率較低，快速排序效率高但需要額外的存儲空間，歸并排序則是效率和穩定性都比較好的排序算法。

posted @ 2024-04-20 01:00 Yfeil 閱讀(93) 評論(0) 收藏舉報

刷新頁面返回頂部