[JAVA]基數排序法(Radix sort)

2022-06-04 置頂文章

需要二維陣列：第一維用來表示第幾個桶，第二維用來儲存符合x位數基數的值
需要一維陣列：用來表示二維陣列的每個桶，儲存幾個值
每個桶的空間：以待排序陣列長度為基準
步驟：1. 先找出最大值，並得出最大值位數 => 基數排序進行的次數，假設最大值為百位數，那基數排序會排序3次
2. 求出個位數基數，將值依序放入二維陣列中
3. 紀錄每個桶放入幾個數 => 入一維陣列
4. 取出二維陣列的值放回原待排序陣列，並清空二維陣列、一維陣列做為下一次排序使用

import java.util.Arrays;

// 空間換時間
// 基數排序
public class RadixSort {
  public static void main(String[] args) {
    int[] array = {23,1,56,975,356,754,23,4};
    doRadixSorting(array);
  }

  /**
   * 基數排序
   * @param array
   */
  public static void doRadixSorting(int[] array) {
    int[][] bucketValues = new int[10][array.length];
    int[] bucketValueCounts = new int[10];
    // 找出最大值幾位數
    int maxDigit = findMaxDigit(array);
    int radix = 1;
    for (int i = 0; i < maxDigit; i++, radix *= 10) {
      for (int j = 0; j < array.length; j++) {
        // 得出位數基數
        int digitNo = array[j] / radix % 10;
        // 把值放入桶(二維陣列)
        bucketValues[digitNo][bucketValueCounts[digitNo]++] = array[j];
      }
      // 依序將桶中的值取出放入原待排序陣列，並將桶與計數桶裡幾個值清空(歸0)
      int count = 0;
      for (int k = 0; k < bucketValues.length; k++) {
        for (int l = 0; l < bucketValueCounts[k]; l++) {
          array[count++] = bucketValues[k][l];
          bucketValues[k][l] = 0;
        }
        bucketValueCounts[k] = 0;
      }
      System.out.printf("第%d輪排序後array : %s ", i+1, Arrays.toString(array));
      System.out.println();
    }

  }

  /**
   * 找出最大值幾位數
   * @param array
   * @return
   */
  public static int findMaxDigit(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
      if (max < array[i]) {
        max = array[i];
      }
    }
    return String.valueOf(max).length();
  }
}

如有敘述錯誤，還請不吝嗇留言指教，thanks!

回首頁