基数排序

简介
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
图解

代码

  public static void radixSort(int[] arr) {
    int[] nums = new int[10];
    int[][] bucket = new int[10][arr.length];
    int element;
    for (int j : arr) {
      element = j % 10;
      bucket[element][nums[element]] = j;
      nums[element]++;
    }
    int index = 0;
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] != 0) {
       for (int j = 0; j < nums[i]; j++) {
         arr[index++] = bucket[i][j];
       }
      }
      nums[i] = 0;
    }
    System.out.println("第一轮======"+Arrays.toString(arr));

    for (int j : arr) {
      element = j /10 % 10;
      bucket[element][nums[element]] = j;
      nums[element]++;
    }
    index = 0;
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] != 0) {
        for (int j = 0; j < nums[i]; j++) {
          arr[index++] = bucket[i][j];
        }
      }
      nums[i] = 0;
    }
    System.out.println("第二轮======"+Arrays.toString(arr));

    for (int j : arr) {
      element = j /100 % 10;
      bucket[element][nums[element]] = j;
      nums[element]++;
    }
    index = 0;
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] != 0) {
        for (int j = 0; j < nums[i]; j++) {
          arr[index++] = bucket[i][j];
        }
      }
      nums[i] = 0;
    }
    System.out.println("第三轮======"+Arrays.toString(arr));
  }

测试

     int[] arr = { 26, 5, 317, 548, 64, 114};
    radixSort(arr);

根据上面的代码可以得到以下代码

  public static void radixSort2(int[] arr) {
    int[] nums = new int[10];
    int[][] bucket = new int[10][arr.length];
    int element;
    int maxIndex = 0;
    int index = 0;
    for (int i = 1; i < arr.length; i++) {
      if (arr[maxIndex] < arr[i]) {
        maxIndex = i;
      }
    }
    int maxLength = (arr[maxIndex] + "").length();
    for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
      for (int j : arr) {
        element = j /n % 10;
        bucket[element][nums[element]] = j;
        nums[element]++;
      }
      index = 0;
      for (int j = 0; j < nums.length; j++) {
        if (nums[j] != 0) {
          for (int k = 0; k < nums[j]; k++) {
            arr[index++] = bucket[j][k];
          }
        }
        nums[j] = 0;
      }
      System.out.println("第三轮======"+Arrays.toString(arr));
    }

  }

测试

   int[] arr = { 26, 5, 317, 548, 64, 114};
    radixSort2(arr);

可以发现结果是一样的

带负整数的排序

 public static void radixSort3(int[] arr) {
    int[] nums = new int[10];
    int[][] bucket = new int[10][arr.length];
    int element;
    int maxIndex = 0;
    int index;
    //统计负数的个数
    int count = 0;
    for (int i = 1; i < arr.length; i++) {
      if (arr[maxIndex] < arr[i]) {
        maxIndex = i;
      }
    }
    int maxLength = (arr[maxIndex] + "").length();
    for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
      for (int j : arr) {
        if (i == 0 && j < 0) {
          count++;
        }
        element = Math.abs(j /n % 10);
        bucket[element][nums[element]] = j;
        nums[element]++;
      }

      index = 0;
      for (int j = 0; j < nums.length; j++) {
        if (nums[j] != 0) {
          for (int k = 0; k < nums[j]; k++) {
            arr[index++] = bucket[j][k];
          }
        }
        nums[j] = 0;
      }
      System.out.println(Arrays.toString(arr));
    }
    count--;
    index = 0;
    for (int k : arr) {
      if (k >= 0) {
        bucket[1][nums[1]] = k;
        nums[1]++;
      } else {
        //将顺序反过来
        bucket[0][Math.abs(nums[0] - count)] = k;
        nums[0]++;
      }
    }
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < nums[i]; j++) {
        arr[index++] = bucket[i][j];
      }
    }
    System.out.println(Arrays.toString(arr));
  }

测试

    int[] arr = { -26, -5,-6,0, 317, 548,8, -64,266};
    radixSort3(arr);

注意

1. 基数排序是以空间换时间，内存占用很大，当排序的数据过多是，会造成内存不足
2. 有负数的数组不推荐使用基数排序.

基数排序

原文：https://www.cnblogs.com/ftlzypx/p/15128544.html