引言
本篇是排序算法的最后一篇,基数排序,桶排序的升级版。
1、算法步骤
1、首先对一组数据按照个位上的数字进行桶排序
2、然后对这组数据继续按照十位上的数字进行桶排序
3、依次循环至这组数据的最大数位置上,排序就完成了。
2、时间复杂度
平均时间复杂度O(n + k)
3、算法实现
public class RadixSort {
public static void main(String[] args) {
int[] numbers = {12,2,24,30,6,16};
int[] result = RadixSort.sort(numbers);
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i < result.length; i++) {
stringBuffer.append(result[i] + " ");
}
System.out.println(stringBuffer.toString());
}
public static int[] sort(int[] numbers){
int[] needSort = Arrays.copyOf(numbers, numbers.length);
//获取最大数的位数
int maxLength = getMaxLength(needSort);
//根据位数依次排序
return radixSort(needSort, maxLength);
}
public static int getMaxLength(int[] arg){
//获取最大的数
int maxValue = arg[0];
for (int i = 1; i < arg.length; i++) {
if(maxValue < arg[i]){
maxValue = arg[i];
}
}
//获取最大数位数
if(maxValue == 0){
return 1;
}
int maxLength = 0;
for (long temp = maxValue; temp != 0; temp /= 10) {
maxLength++;
}
return maxLength;
}
public static int[] radixSort(int[] arg,int maxLength){
//位数
int dev = 1;
//10进制
int hex = 10;
for (int i = 0; i < maxLength; i++,dev *= 10,hex *= 10) {
// 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
int[][] counter = new int[hex * 2][0];
for (int j = 0; j < arg.length; j++) {
int bucket = (arg[j] % hex) / dev + hex;
counter[bucket] = arrayAppend(counter[bucket],arg[j]);
}
int length = 0;
for (int[] bucket : counter) {
for (int value : bucket){
arg[length++] = value;
}
}
}
return arg;
}
private static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
复制代码
4、总结
计数排序中每个桶只存储单一数值,有很多空桶浪费了;桶排序中,每个桶存储一定范围的数值,每个桶中的数据仍需再排序;基数排序是根据键值的每位数字来分配桶。
结束语
排序算法到此结束,现在入职新公司,在熟悉业务和代码中,后面有时间刷LeetCode的时候会再进行总结。
近期评论