引言

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規範，要得到一個符合實際的優秀算法，得經過大量的推理和分析。

簡介

排序算法可以分為：

• 內部排序：數據記錄在內存中進行排序。
• 外部排序：因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等，本文只講解內部排序算法。用一張圖概括：

術語説明

• 穩定：如果 A 原本在 B 前面，而 $A=B$，排序之後 A 仍然在 B 的前面。
• 不穩定：如果 A 原本在 B 的前面，而 $A=B$，排序之後 A 可能會出現在 B 的後面。
• 時間複雜度：定性描述一個算法執行所耗費的時間。
• 空間複雜度：定性描述一個算法執行所需內存的大小。

算法分類

十種常見排序算法可以分類兩大類別：比較類排序和非比較類排序。

常見的快速排序、歸併排序、堆排序以及冒泡排序等都屬於比較類排序算法。比較類排序是通過比較來決定元素間的相對次序，由於其時間複雜度不能突破 O(nlogn)，因此也稱為非線性時間比較類排序。在冒泡排序之類的排序中，問題規模為 n，又因為需要比較 n 次，所以平均時間複雜度為 O(n²)。在歸併排序、快速排序之類的排序中，問題規模通過分治法消減為 logn 次，所以時間複雜度平均 O(nlogn)。

比較類排序的優勢是，適用於各種規模的數據，也不在乎數據的分佈，都能進行排序。可以説，比較排序適用於一切需要排序的情況。

而計數排序、基數排序、桶排序則屬於非比較類排序算法。非比較排序不通過比較來決定元素間的相對次序，而是通過確定每個元素之前，應該有多少個元素來排序。由於它可以突破基於比較排序的時間下界，以線性時間運行，因此稱為線性時間非比較類排序。 非比較排序只要確定每個元素之前的已有的元素個數即可，所有一次遍歷即可解決。算法時間複雜度 $O(n)$。

非比較排序時間複雜度底，但由於非比較排序需要佔用空間來確定唯一位置。所以對數據規模和數據分佈有一定的要求。

冒泡排序 (Bubble Sort)

冒泡排序是一種簡單的排序算法。它重複地遍歷要排序的序列，依次比較兩個元素，如果它們的順序錯誤就把它們交換過來。遍歷序列的工作是重複地進行直到沒有再需要交換為止，此時説明該序列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢 “浮” 到數列的頂端。

算法步驟

1. 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
3. 針對所有的元素重複以上的步驟，除了最後一個；
4. 重複步驟 1~3，直到排序完成。

圖解算法

代碼實現

/**
 * 冒泡排序
 * @param arr
 * @return arr
 */
public static int[] bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // Set a flag, if true, that means the loop has not been swapped,
        // that is, the sequence has been ordered, the sorting has been completed.
        boolean flag = true;
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
       // Change flag
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
    return arr;
}

此處對代碼做了一個小優化，加入了 is_sorted Flag，目的是將算法的最佳時間複雜度優化為 O(n)，即當原輸入序列就是排序好的情況下，該算法的時間複雜度就是 O(n)。

算法分析

• 穩定性：穩定
• 時間複雜度：最佳：$O(n)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
• 空間複雜度：$O(1)$
• 排序方式：In-place

選擇排序 (Selection Sort)

選擇排序是一種簡單直觀的排序算法，無論什麼數據進去都是 $O(n^2)$ 的時間複雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間了吧。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

算法步驟

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
3. 重複第 2 步，直到所有元素均排序完畢。

圖解算法

代碼實現

/**
 * 選擇排序
 * @param arr
 * @return arr
 */
public static int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    return arr;
}

算法分析

• 穩定性：不穩定
• 時間複雜度：最佳：$O(n^2)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
• 空間複雜度：$O(1)$
• 排序方式：In-place

插入排序 (Insertion Sort)

插入排序是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用 in-place 排序（即只需用到 $O(1)$ 的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

插入排序和冒泡排序一樣，也有一種優化算法，叫做拆半插入。

算法步驟

1. 從第一個元素開始，該元素可以認為已經被排序；
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描；
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置；
4. 重複步驟 3，直到找到已排序的元素小於或者等於新元素的位置；
5. 將新元素插入到該位置後；
6. 重複步驟 2~5。

圖解算法

代碼實現

/**
 * 插入排序
 * @param arr
 * @return arr
 */
public static int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preIndex = i - 1;
        int current = arr[i];
        while (preIndex >= 0 && current < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex -= 1;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

算法分析

• 穩定性：穩定
• 時間複雜度：最佳：$O(n)$ ，最差：$O(n^2)$， 平均：$O(n2)$
• 空間複雜度：$O(1)$
• 排序方式：In-place

希爾排序 (Shell Sort)

希爾排序是希爾 (Donald Shell) 於 1959 年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為遞減增量排序算法，同時該算法是衝破 $O(n^2)$ 的第一批算法之一。

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄 “基本有序” 時，再對全體記錄進行依次直接插入排序。

算法步驟

我們來看下希爾排序的基本步驟，在此我們選擇增量 $gap=length/2$，縮小增量繼續以 $gap = gap/2$ 的方式，這種增量選擇我們可以用一個序列來表示，$\lbrace \frac{n}{2}, \frac{(n/2)}{2}, \dots, 1 \rbrace$，稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題，我們選擇的這個增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實這個增量序列不是最優的。此處我們做示例使用希爾增量。

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體算法描述：

• 選擇一個增量序列 $\lbrace t_1, t_2, \dots, t_k \rbrace$，其中 $t_i \gt t_j, i \lt j, t_k = 1$；
• 按增量序列個數 k，對序列進行 k 趟排序；
• 每趟排序，根據對應的增量 $t$，將待排序列分割成若干長度為 $m$ 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

圖解算法

代碼實現

/**
 * 希爾排序
 *
 * @param arr
 * @return arr
 */
public static int[] shellSort(int[] arr) {
    int n = arr.length;
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int current = arr[i];
            int preIndex = i - gap;
            // Insertion sort
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = current;

        }
        gap /= 2;
    }
    return arr;
}

算法分析

• 穩定性：不穩定
• 時間複雜度：最佳：$O(nlogn)$， 最差：$O(n^2)$ 平均：$O(nlogn)$
• 空間複雜度：$O(1)$

歸併排序 (Merge Sort)

歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法 (Divide and Conquer) 的一個非常典型的應用。歸併排序是一種穩定的排序方法。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為 2 - 路歸併。

和選擇排序一樣，歸併排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是 $O(nlogn)$ 的時間複雜度。代價是需要額外的內存空間。

算法步驟

歸併排序算法是一個遞歸過程，邊界條件為當輸入序列僅有一個元素時，直接返回，具體過程如下：

1. 如果輸入內只有一個元素，則直接返回，否則將長度為 $n$ 的輸入序列分成兩個長度為 $n/2$ 的子序列；
2. 分別對這兩個子序列進行歸併排序，使子序列變為有序狀態；
3. 設定兩個指針，分別指向兩個已經排序子序列的起始位置；
4. 比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間（用於存放排序結果），並移動指針到下一位置；
5. 重複步驟 3 ~ 4 直到某一指針達到序列尾；
6. 將另一序列剩下的所有元素直接複製到合併序列尾。

圖解算法

代碼實現

/**
 * 歸併排序
 *
 * @param arr
 * @return arr
 */
public static int[] mergeSort(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }
    int middle = arr.length / 2;
    int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
    int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
    return merge(mergeSort(arr_1), mergeSort(arr_2));
}

/**
 * Merge two sorted arrays
 *
 * @param arr_1
 * @param arr_2
 * @return sorted_arr
 */
public static int[] merge(int[] arr_1, int[] arr_2) {
    int[] sorted_arr = new int[arr_1.length + arr_2.length];
    int idx = 0, idx_1 = 0, idx_2 = 0;
    while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
        if (arr_1[idx_1] < arr_2[idx_2]) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 += 1;
        } else {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 += 1;
        }
        idx += 1;
    }
    if (idx_1 < arr_1.length) {
        while (idx_1 < arr_1.length) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 += 1;
            idx += 1;
        }
    } else {
        while (idx_2 < arr_2.length) {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 += 1;
            idx += 1;
        }
    }
    return sorted_arr;
}

算法分析

• 穩定性：穩定
• 時間複雜度：最佳：$O(nlogn)$， 最差：$O(nlogn)$， 平均：$O(nlogn)$
• 空間複雜度：$O(n)$

快速排序 (Quick Sort)

快速排序用到了分治思想，同樣的還有歸併排序。乍看起來快速排序和歸併排序非常相似，都是將問題變小，先排序子串，最後合併。不同的是快速排序在劃分子問題的時候經過多一步處理，將劃分的兩組數據劃分為一大一小，這樣在最後合併的時候就不必像歸併排序那樣再進行比較。但也正因為如此，劃分的不定性使得快速排序的時間複雜度並不穩定。

快速排序的基本思想：通過一趟排序將待排序列分隔成獨立的兩部分，其中一部分記錄的元素均比另一部分的元素小，則可分別對這兩部分子序列繼續進行排序，以達到整個序列有序。

算法步驟

快速排序使用 分治法（Divide and conquer）策略來把一個序列分為較小和較大的 2 個子序列，然後遞歸地排序兩個子序列。具體算法描述如下：

1. 從序列中隨機挑出一個元素，做為 “基準”(pivot)：選擇不同位置的中心元素，快速排序就有不同的變體，比如可以選擇：第一個元素、最後一個元素以及左端、右端和中心位置上的三個元素的中值作為中心元素
2. 重新排列序列，將所有比基準值小的元素擺放在基準前面，所有比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個操作結束之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；
3. 遞歸地把小於基準值元素的子序列和大於基準值元素的子序列進行快速排序。

圖解算法

代碼實現

來源：使用 Java 實現快速排序（詳解）

public static int partition(int[] array, int low, int high) {
    // 取最後一個元素作為中心元素
    int pivot = array[high];
    // 定義指向比中心元素大的指針，首先指向第一個元素
    int pointer = low;
    // 遍歷數組中的所有元素，將比中心元素大的放在右邊，比中心元素小的放在左邊
    for (int i = low; i < high; i++) {
        if (array[i] <= pivot) {
            // 將比中心元素小的元素和指針指向的元素交換位置 
            // 如果第一個元素比中心元素小，這裏就是自己和自己交換位置，指針和索引都向下一位移動 
            // 如果元素比中心元素大，索引向下移動，指針指向這個較大的元素，直到找到比中心元素小的元素，並交換位置，指針向下移動
            swap(array, i, pointer);
            pointer++;
        }
        //每次打印排序後結果
        System.out.println(Arrays.toString(array));
    }
    // 將中心元素和指針指向的元素交換位置
    swap(array, pointer, high);
    return pointer;
}
public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
        // 獲取劃分子數組的位置
        int position = partition(array, low, high);
        // 左子數組遞歸調用
        quickSort(array, low, position - 1);
        // 右子數組遞歸調用
        quickSort(array, position + 1, high);
    }
}

private static void swap(int[] arr, int i, int j) { 
    int temp = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = temp; 
}

// 洗牌算法，將輸入的數組隨機打亂 
private static void shuffle(int[] nums) { 
    Random rand = new Random(); 
    int n = nums.length; 
    for (int i = 0 ; i < n; i++) { 
        // 生成 [i, n - 1] 的隨機數 
        int r = i + rand.nextInt(n - i); 
        swap(nums, i, r); 
    } 
}

排序過程的結果如下：

[6, 72, 113, 11, 23]
[6, 72, 113, 11, 23]
[6, 72, 113, 11, 23]
[6, 11, 113, 72, 23]
[6, 11, 23, 72, 113]
[6, 11, 23, 72, 113]
排序後的結果
[6, 11, 23, 72, 113]

從這個排序結果我們可以知道整個排序過程。

算法分析

• 穩定性：不穩定
• 時間複雜度：最佳：$O(nlogn)$， 最差：$O(n^2)$，平均：$O(nlogn)$
• 空間複雜度：$O(logn)$

由於可能在數組已經有序或基本有序的情況下，最差的時間複雜度。為了避免最壞情況發生，可以通過隨機選擇基準元素或者使用三數取中法等策略來提高快速排序的性能；或者可以先使用洗牌算法shuffle，將數據打亂。

堆排序 (Heap Sort)

堆排序是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，並同時滿足堆的性質：即子結點的值總是小於（或者大於）它的父節點。

算法步驟

1. 將初始待排序列 $(R_1, R_2, \dots, R_n)$ 構建成大頂堆，此堆為初始的無序區；
2. 將堆頂元素 $R_1$ 與最後一個元素 $R_n$ 交換，此時得到新的無序區 $(R_1, R_2, \dots, R_{n-1})$ 和新的有序區 $R_n$, 且滿足 $R_i \leqslant R_n (i \in 1, 2,\dots, n-1)$；
3. 由於交換後新的堆頂 $R_1$ 可能違反堆的性質，因此需要對當前無序區 $(R_1, R_2, \dots, R_{n-1})$ 調整為新堆，然後再次將 $R_1$ 與無序區最後一個元素交換，得到新的無序區 $(R_1, R_2, \dots, R_{n-2})$ 和新的有序區 $(R_{n-1}, R_n)$。不斷重複此過程直到有序區的元素個數為 $n-1$，則整個排序過程完成。

圖解算法

代碼實現

// Global variable that records the length of an array;
static int heapLen;

/**
 * Swap the two elements of an array
 * @param arr
 * @param i
 * @param j
 */
private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

/**
 * Build Max Heap
 * @param arr
 */
private static void buildMaxHeap(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapify(arr, i);
    }
}

/**
 * Adjust it to the maximum heap
 * @param arr
 * @param i
 */
private static void heapify(int[] arr, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (right < heapLen && arr[right] > arr[largest]) {
        largest = right;
    }
    if (left < heapLen && arr[left] > arr[largest]) {
        largest = left;
    }
    if (largest != i) {
        swap(arr, largest, i);
        heapify(arr, largest);
    }
}

/**
 * Heap Sort
 * @param arr
 * @return
 */
public static int[] heapSort(int[] arr) {
    // index at the end of the heap
    heapLen = arr.length;
    // build MaxHeap
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        // Move the top of the heap to the tail of the heap in turn
        swap(arr, 0, i);
        heapLen -= 1;
        heapify(arr, 0);
    }
    return arr;
}

算法分析

• 穩定性：不穩定
• 時間複雜度：最佳：$O(nlogn)$， 最差：$O(nlogn)$， 平均：$O(nlogn)$
• 空間複雜度：$O(1)$

計數排序 (Counting Sort)

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。 作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。

計數排序 (Counting sort) 是一種穩定的排序算法。計數排序使用一個額外的數組 C，其中第 i 個元素是待排序數組 A 中值等於 i 的元素的個數。然後根據數組 C 來將 A 中的元素排到正確的位置。它只能對整數進行排序。

算法步驟

1. 找出數組中的最大值 max、最小值 min；
2. 創建一個新數組 C，其長度是 max-min+1，其元素默認值都為 0；
3. 遍歷原數組 A 中的元素 A[i]，以 A[i] - min 作為 C 數組的索引，以 A[i] 的值在 A 中元素出現次數作為 C[A[i] - min] 的值；
4. 對 C 數組變形，新元素的值是該元素與前一個元素值的和，即當 i>1 時 C[i] = C[i] + C[i-1]；
5. 創建結果數組 R，長度和原始數組一樣。
6. 從後向前遍歷原始數組 A 中的元素 A[i]，使用 A[i] 減去最小值 min 作為索引，在計數數組 C 中找到對應的值 C[A[i] - min]，C[A[i] - min] - 1 就是 A[i] 在結果數組 R 中的位置，做完上述這些操作，將 count[A[i] - min] 減小 1。

圖解算法

代碼實現

/**
 * Gets the maximum and minimum values in the array
 *
 * @param arr
 * @return
 */
private static int[] getMinAndMax(int[] arr) {
    int maxValue = arr[0];
    int minValue = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i];
        } else if (arr[i] < minValue) {
            minValue = arr[i];
        }
    }
    return new int[] { minValue, maxValue };
}

/**
 * Counting Sort
 *
 * @param arr
 * @return
 */
public static int[] countingSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    int[] extremum = getMinAndMax(arr);
    int minValue = extremum[0];
    int maxValue = extremum[1];
    int[] countArr = new int[maxValue - minValue + 1];
    int[] result = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - minValue] += 1;
    }
    for (int i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        int idx = countArr[arr[i] - minValue] - 1;
        result[idx] = arr[i];
        countArr[arr[i] - minValue] -= 1;
    }
    return result;
}

算法分析

當輸入的元素是 n 個 0 到 k 之間的整數時，它的運行時間是 $O(n+k)$。計數排序不是比較排序，排序的速度快於任何比較排序算法。由於用來計數的數組 C 的長度取決於待排序數組中數據的範圍（等於待排序數組的最大值與最小值的差加上 1），這使得計數排序對於數據範圍很大的數組，需要大量額外內存空間。

• 穩定性：穩定，相等元素的相對位置在排序後不會改變
• 時間複雜度：最佳：$O(n+k)$ 最差：$O(n+k)$ 平均：$O(n+k)$
• 空間複雜度：O(k)

優化策略

處理負數和極大範圍

當數據範圍很大或包含負數時，標準計數排序可能面臨問題，可以進行如下優化：

public static void countingSortForLargeRange(int[] arr) {
    // 找出數組中的最大值和最小值
    int max = arr[0], min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    
    // 計算範圍
    int range = max - min + 1;
    
    // 如果範圍過大，可以考慮使用其他排序算法
    if (range > arr.length * 100) {
        // 這裏可以調用其他排序算法，如快速排序
        Arrays.sort(arr);
        return;
    }
    
    // 正常的計數排序邏輯
    // ...
}

內存優化

當只需要排序結果、不需要保持穩定性時，可以省略輸出數組，直接更新原數組：

public static void countingSortInPlace(int[] arr) {
    // 找出最大值和最小值
    int max = arr[0], min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    
    // 創建計數數組
    int[] count = new int[max - min + 1];
    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }
    
    // 直接從計數數組重建原數組
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
}

桶排序 (Bucket Sort)

桶排序是一種分配式排序算法，將元素分到有限數量的桶裏，每個桶再單獨排序（比如用插入排序），最後依次把各個桶中的元素取出來即完成排序。

桶排序是計數排序的升級版。它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：

1. 在額外空間充足的情況下，儘量增大桶的數量
2. 使用的映射函數能夠將輸入的 N 個數據均勻的分配到 K 個桶中

桶排序的工作的原理：假設輸入數據服從均勻分佈，將數據分到有限數量的桶裏，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行。

算法步驟

1. 設置一個 BucketSize，作為每個桶所能放置多少個不同數值；
2. 遍歷輸入數據，並且把數據依次映射到對應的桶裏去；
3. 對每個非空的桶進行排序，可以使用其它排序方法，也可以遞歸使用桶排序；
4. 從非空桶裏把排好序的數據拼接起來。

圖解算法

代碼實現

/**
 * Gets the maximum and minimum values in the array
 * @param arr
 * @return
 */
private static int[] getMinAndMax(List<Integer> arr) {
    int maxValue = arr.get(0);
    int minValue = arr.get(0);
    for (int i : arr) {
        if (i > maxValue) {
            maxValue = i;
        } else if (i < minValue) {
            minValue = i;
        }
    }
    return new int[] { minValue, maxValue };
}

/**
 * Bucket Sort
 * @param arr
 * @return
 */
public static List<Integer> bucketSort(List<Integer> arr, int bucket_size) {
    if (arr.size() < 2 || bucket_size == 0) {
        return arr;
    }
    int[] extremum = getMinAndMax(arr);
    int minValue = extremum[0];
    int maxValue = extremum[1];
    int bucket_cnt = (maxValue - minValue) / bucket_size + 1;
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < bucket_cnt; i++) {
        buckets.add(new ArrayList<Integer>());
    }
    for (int element : arr) {
        int idx = (element - minValue) / bucket_size;
        buckets.get(idx).add(element);
    }
    for (int i = 0; i < buckets.size(); i++) {
        if (buckets.get(i).size() > 1) {
            buckets.set(i, sort(buckets.get(i), bucket_size / 2));
        }
    }
    ArrayList<Integer> result = new ArrayList<>();
    for (List<Integer> bucket : buckets) {
        for (int element : bucket) {
            result.add(element);
        }
    }
    return result;
}

算法分析

• 穩定性：穩定
• 時間複雜度：最佳：$O(n+k)$ 最差：$O(n^2)$ 平均：$O(n+k)$
• 空間複雜度：$O(n+k)$

基數排序 (Radix Sort)

基數排序也是非比較的排序算法，對元素中的每一位數字進行排序，從最低位開始排序，複雜度為 $O(n×k)$，$n$ 為數組長度，$k$ 為數組中元素的最大的位數；

基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基於分別排序，分別收集，所以是穩定的。

算法步驟

1. 取得數組中的最大數，並取得位數，即為迭代次數 $N$（例如：數組中最大數值為 1000，則 $N=4$）；
2. A 為原始數組，從最低位開始取每個位組成 radix 數組；
3. 對 radix 進行計數排序（利用計數排序適用於小範圍數的特點）；
4. 將 radix 依次賦值給原數組；
5. 重複 2~4 步驟 $N$ 次

圖解算法

代碼實現

/**
 * Radix Sort
 *
 * @param arr
 * @return
 */
public static int[] radixSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    int N = 1;
    int maxValue = arr[0];
    for (int element : arr) {
        if (element > maxValue) {
            maxValue = element;
        }
    }
    while (maxValue / 10 != 0) {
        maxValue = maxValue / 10;
        N += 1;
    }
    for (int i = 0; i < N; i++) {
        List<List<Integer>> radix = new ArrayList<>();
        for (int k = 0; k < 10; k++) {
            radix.add(new ArrayList<Integer>());
        }
        for (int element : arr) {
            int idx = (element / (int) Math.pow(10, i)) % 10;
            radix.get(idx).add(element);
        }
        int idx = 0;
        for (List<Integer> l : radix) {
            for (int n : l) {
                arr[idx++] = n;
            }
        }
    }
    return arr;
}

算法分析

• 穩定性：穩定
• 時間複雜度：最佳：$O(n×k)$ 最差：$O(n×k)$ 平均：$O(n×k)$
• 空間複雜度：$O(n+k)$

基數排序 vs 計數排序 vs 桶排序

這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

• 基數排序：根據鍵值的每位數字來分配桶
• 計數排序：每個桶只存儲單一鍵值
• 桶排序：每個桶存儲一定範圍的數值