package algorithm.sort;

import java.util.Arrays;

/**

* @author 李文浩

* @date 2018/2/5

*/

public class Radix {

public static void sort(int[] arr) {

if (arr.length <= 1) return;

//取得数组中的最大数，并取得位数

int max = 0;

for (int i = 0; i < arr.length; i++) {

if (max < arr[i]) {

max = arr[i];

}

}

int maxDigit = 1;

while (max / 10 > 0) {

maxDigit++;

max = max / 10;

}

//申请一个桶空间

int[][] buckets = new int[10][arr.length];

int base = 10;

//从低位到高位，对每一位遍历，将所有元素分配到桶中

for (int i = 0; i < maxDigit; i++) {

int[] bktLen = new int[10]; //存储各个桶中存储元素的数量

//分配：将所有元素分配到桶中

for (int j = 0; j < arr.length; j++) {

int whichBucket = (arr[j] % base) / (base / 10);

buckets[whichBucket][bktLen[whichBucket]] = arr[j];

bktLen[whichBucket]++;

}

//收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞

int k = 0;

for (int b = 0; b < buckets.length; b++) {

for (int p = 0; p < bktLen[b]; p++) {

arr[k++] = buckets[b][p];

}

}

System.out.println("Sorting: " + Arrays.toString(arr));

base *= 10;

}

}

}