排序算法之基数排序【Java版】

引言

本篇是排序算法的最后一篇，基数排序，桶排序的升级版。

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的时候会再进行总结。