基於桶的排序之基數排序以及排序方法總結

作者：Grey

原文地址：

部落格園：基於桶的排序之基數排序以及排序方法總結

CSDN：基於桶的排序之基數排序以及排序方法總結

說明

基於桶的排序有兩種，分別是計數排序和基數排序。

但是這兩種排序應用範圍有限，需要樣本的資料狀況滿足桶的劃分

計數排序演演算法說明見：基於桶的排序之計數排序

基數排序

一般來講，基數排序要求，樣本是 10 進位制的正整數, 流程如下

第一步：找到最大值，這個最大值是幾位的，其他數不足這個位數的，用 0 補齊；

例如：

原始陣列為

arr = {17,210,3065,40,71,2}

最大值為 3065，是四位的，其他都不是四位的，前面用 0 補充，所以先讓陣列變成

arr = {0017,0210,3065,0040,0071,0002}

第二步：準備 10 個桶，每個桶是佇列；

第三步：從個位依次進桶（和對應桶中的元素用佇列相連），然後依次倒出；然後根據十位數進桶（和對應桶中的元素用佇列相連），依次倒出；以此類推，一直到最高進桶，然後倒出。最後倒出的順序就是排序後的結果。

以上述陣列為例，基數排序的整個流程如下

第一輪入桶，個位上的數依次是：7,0,5,0,1,2，入桶後，是如下效果:

然後出桶，第一輪結果是{0210,0040,0071,0002,3065,0017};

第二輪入桶，十位上的數位分別是：1,4,7,0,6,1，入桶後，效果如下:

第二輪出桶：結果是{0002,0210,0017,0040,3065,0071};

第三輪入桶，百位上的數位分別是：0,2,0,0,0,0，入桶後，效果如下:

第四輪入桶，也是最後一輪入桶，千位上的數位分別是：0,0,0,3,0,0，入桶後，效果如下：

最後一輪出桶：結果是{0002,0017,0040,0071,0210,3065}，已排好序。

上述是基數排序的流程，但是在演演算法實現上，有更優化的解法

根據整個基數排序的演演算法，程式碼上做了一些優化，用了一個包含十個元素的陣列count來表示桶，而且整個程式碼沒有用佇列這個資料結構，僅用 count 陣列就實現了入桶和出桶的過程，接下來一一分析一下程式碼，其中helper陣列用於存排序後的陣列，bits表示最大數十進位制一共有幾位，流程和之前提到的演演算法流程一致：

// 從個位開始，一直到最高位，不斷入桶出桶
for (int bit = 1; bit <= bits; bit++) {
    // 入桶
    // 出桶
}

入桶的邏輯，原先我們需要把入桶的值記錄到桶對應的佇列中，如今不需要，我們只需要記錄一個個數即可，就是如下邏輯

// 從個位開始，一直到最高位，不斷入桶出桶
for (int bit = 1; bit <= bits; bit++) {
    int[] count = new int[10];
    for (int num : arr) {
        count[digit(num, bit)]++;
    }
    // 出桶
}

以上述範例陣列來說明，範例陣列初始狀態是{0017,0210,3065,0040,0071,0002}，經過第一輪個位數的入桶操作，count陣列會變成{2,1,1,0,0,1,0,1,0,0}，如下範例圖

原始演演算法

用 count 優化後

可以看到 count 只存了陣列中的數的有相同位數值的數有多少個。

比如：

count[0] = 2; // 說明 0 號桶在第一輪入桶的時候，有兩個數，也說明個位上是 0 的數有兩個。
count[5] = 1; // 說明 5 號桶在第一輪入桶的時候，有一個數，也說明個位上是 5 的數有一個。
......

接下來是出桶操作，原始演演算法中，值存在佇列，從左到右遍歷桶，桶中元素按佇列遍歷出來即可；優化後，只有一個count陣列，count 陣列只記錄了個數，如何實現出桶呢？客觀上，在第一輪中，出桶順序是{0210,0040,0071,0002,3065,0017}，其實，就是出桶編號從小到大，桶中的數依次出來。

基於第一輪的count={2,1,1,0,0,1,0,1,0,0}可得到其字首和陣列{2,3,4,4,4,5,5,6,6,6}，最大編號且包含陣列元素的桶是 7 號桶，且 7 號桶中只有一個數，就是 0017 ，所以這個數一定是最後出桶的那個數！接下來包含元素的最大桶編號是 5 號桶，5 號桶只有一個數，就是 3065，這個數一定是倒數第二順序出來的數！依次類推，就可以把所有第一輪出桶的數按順序提取出來，核心程式碼入下：

      // 字首和
      for (int j = 1; j < 10; j++) {
        count[j] = count[j - 1] + count[j];
      }
      // 倒序遍歷陣列
      for (int i = arr.length - 1; i >= 0; i--) {
        int pos = digit(arr[i], bit);
        // 陣列中某一位是 pos 的數，在某一輪入桶後
        // 出桶的時候，應該處在什麼位置！！！
        help[--count[pos]] = arr[i];
      }

完整程式碼見

public class Code_RadixSort {

  // 非負數
  public static void radixSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
      return;
    }
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
      max = Math.max(arr[i], max);
    }
    // 最大值有幾位
    int bits = 0;
    while (max != 0) {
      bits++;
      max /= 10;
    }
    int[] help = new int[arr.length];
    for (int bit = 1; bit <= bits; bit++) {
      int[] count = new int[10];
      for (int num : arr) {
        count[digit(num, bit)]++;
      }
      // 字首和
      for (int j = 1; j < 10; j++) {
        count[j] = count[j - 1] + count[j];
      }
      // 倒序遍歷陣列
      for (int i = arr.length - 1; i >= 0; i--) {
        int pos = digit(arr[i], bit);
        help[--count[pos]] = arr[i];
      }
      int m = 0;
      for (int num : help) {
        arr[m++] = num;
      }
    }
  }

  // 獲取某個數在某一位上的值
  // 從1開始，從個位開始
  public static int digit(int num, int digit) {
    return ((num / (int) Math.pow(10, digit - 1)) % 10);
  }
}

排序總結

	時間複雜度	額外空間複雜度	穩定性
選擇排序	O(N^2)	O(1)	無
氣泡排序	O(N^2)	O(1)	有
插入排序	O(N^2)	O(1)	有
歸併排序	O(N*logN)	O(N)	有
隨機快排	O(N*logN)	O(logN)	無
堆排序	O(N*logN)	O(1)	無
計數排序	O(N)	O(M)	有
基數排序	O(N)	O(N)	有

選擇排序做不到穩定性，比如：5，5，5，5，5，3，5，5，5

氣泡排序可以做到穩定性，在相等的時候，不往右即可

插入排序可以做到穩定性，在相等的時候，不往左邊繼續交換即可

快排做不到穩定性，因為partition過程無法穩定，某個數會和小於等於區域交換

0）排序穩定性關鍵在於處理相等的時候

1）不基於比較的排序，對樣本資料有嚴格要求，不易改寫

2）基於比較的排序，只要規定好兩個樣本怎麼比大小就可以直接複用

3）基於比較的排序，時間複雜度的極限是O(N*logN)

4）時間複雜度O(N*logN)、額外空間複雜度低於O(N)、且穩定的基於比較的排序是不存在的。

5）為了絕對的速度選快排、為了省空間選堆排、為了穩定性選歸併

演演算法和資料結構筆記

參考資料

演演算法和資料結構體系班-左程雲

基於桶的排序之基數排序以及排序方法總結

基於桶的排序之基數排序以及排序方法總結

說明

基數排序

排序總結

更多

參考資料