基数排序是非比较型整数排序算法，其原理是将整数按位分割进行排序。基数排序适用于大范围数据排序，打破了计数排序的限制。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数，所以基数排序也不是只能使用于整数。
概念
基数排序是非比较型整数排序算法，其原理是将整数按位分割进行排序。
数排序适用于大范围数据排序，打破了计数排序的限制。
由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数，所以基数排序也不是只能使用于整数。
2种排序方式
按位分割小技巧
LSD排序算法实现
算法实现代码
/**
* 按位进行计数排序
* @param arr
* @param divid
* @return
*/
private static int[] countingSort(int[] arr, int divid){
int[] bucket = new int[10];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i] / divid % 10]++;
}
for (int i = 1; i < bucket.length; i++) {
bucket[i] = bucket[i-1] + bucket[i];
}
int[] sortArr = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--){
int position = bucket[arr[i] / divid % 10];
sortArr[position - 1] = arr[i];
bucket[arr[i] / divid % 10]--;
}
return sortArr;
}
public static int[] radixSort(int[] arr) {
// 查找数组最大值
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
}
// 按位排序
int digit = 1;
for (int i = 1; i < max; digit*=10, i = digit) {
arr = countingSort(arr, digit);
}
return arr;
}
public static void main(String[] args) {
int[] arr = {999,1000,1001,1000,999,1005};
System.out.println("排序前:" + JSON.toJSONString(arr));
int[] sortArr = radixSort(arr);
System.out.println("排序后:" + JSON.toJSONString(sortArr));
}
MSD排序算法实现
算法实现代码
public static int[] sort(int[] arr){
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
// 获取最大值
max = Math.max(arr[i], max);
}
// 获取最大值的位数
int digit = getDataDigit(max);
// 计算最大值的基数
int radix = new Double(Math.pow(10, digit - 1)).intValue();
// msd基数排序
return msdSort(arr, radix);
}
/**
* MSD 基数排序
* @param arr
* @param radix
* @return
*/
public static int[] msdSort(int[] arr, int radix){
// 递归分组到个位，退出
if (radix <= 0) {
return arr;
}
// 分组计数器
int[] groupCounter = new int[10];
// 分组桶
int[][] groupBucket = new int[10][arr.length];
// 遍历待排序数组，按位分组
for (int i = 0; i < arr.length; i++) {
// 计算分组桶位置
int position = arr[i] / radix % 10;
// 将元素存入分组
groupBucket[position][groupCounter[position]] = arr[i];
// 当前分组计数加1
groupCounter[position]++;
}
int index = 0;
int[] sortArr = new int[arr.length];
// 遍历分组计数器
for (int i = 0; i < groupCounter.length; i++) {
// 组内元素数量>1，递归分组
if (groupCounter[i] > 1) {
int[] copyArr = Arrays.copyOf(groupBucket[i], groupCounter[i]);
// 递归分组
int[] tmp = msdSort(copyArr, radix / 10);
// 收集递归分组后的元素
for (int j = 0; j < tmp.length; j++) {
sortArr[index++] = tmp[j];
}
} else if (groupCounter[i] == 1) {
// 收集组内元素数量=1的元素
sortArr[index++] = groupBucket[i][0];
}
}
return sortArr;
}
/**
* 获取数据的位数
* @param data
* @return
*/
public static int getDataDigit(int data) {
// int index = 0;
// int digit = 1;
// while (data / digit >0) {
// digit *= 10;
// index++;
// }
// return index;
return String.valueOf(data).length();
}
验证排序结果：
public static void main(String[] args) {
int[] arr = {333,1002,1001,1000,333,1003,2000};
System.out.println("排序前:" + JSON.toJSONString(arr));
int[] sortArr = sort(arr);
System.out.println("排序后:" + JSON.toJSONString(sortArr));
}
排序前:
[333,1002,1001,1000,333,1003,2000]
排序后:
[333,333,1000,1001,1002,1003,2000]
三向切分字符快速排序
算法实现代码
/**
* 按位将字符串切分为三个区间
* 1. 小于v区间：[lo,lt]
* 2. 等于v区间：[lt,gt]
* 3. 大于v区间: [gt+1,hi]
* @param arr
* @param lo
* @param hi
* @param d
*/
public static void sortStr(String[] arr, int lo, int hi, int d){
if (hi <= lo) {
return;
}
// 定义小于v的看门lt, 大于v的看门gt
int lt = lo, gt = hi, i = lo + 1, v = charAt(arr[lo],d);
while (i <= gt){
int t = charAt(arr[i], d);
if (t < v) {
exch(arr, i++, lt++);
} else if (t > v) {
exch(arr, i, gt--);
} else {
i++;
}
}
// 递归小于v的区间
sortStr(arr, lo, lt - 1, d);
// 递归等于v的区间
if (v >= 0) {
sortStr(arr, lt, gt, d + 1);
}
// 递归大于v的区间
sortStr(arr, gt + 1, hi, d);
}
private static int charAt(String s, int d) {
if (d < s.length()) {
return s.charAt(d);
}
return -1;
}
public static void exch(String[] arr, int sourceIdx, int targetIdx) {
String tmp = arr[sourceIdx];
arr[sourceIdx] = arr[targetIdx];
arr[targetIdx] = tmp;
}
结果验证：
public static void main(String[] args) {
String[] a = new String[]{"by","air","she","shell","the","okay","bump","shirt","shells","sh","the","shells","the"};
System.out.println("排序前:" + JSON.toJSONString(a));
sortStr(a, 0, a.length - 1, 0);
System.out.println("排序后:" + JSON.toJSONString(a));
}
总结
