🍆 基数排序（Radix Sort)
简介：
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
设计思想：
取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
代码实现：
c语言版
int get_index(int num, int dec, int order) { int i, j, n; int index; int div; for (i = dec; i > order; i--) { n = 1; for (j = 0; j < dec - 1; j++) n *= 10; div = num / n; num -= div * n; dec--; } n = 1; for (i = 0; i < order - 1; i++) n *= 10; index = num / n; return index; } void RadixSort(int *arr, int len, int dec, int order) { int i, j; int index; int tmp[len]; int num[10]; memset(num, 0, 10 * sizeof(int)); memset(tmp, 0, len * sizeof(int)); if (dec < order) { return; } for (i = 0; i < len; i++) { index = get_index(arr[i], dec, order); num[index]++; } for (i = 1; i < 10; i++) { num[i] += num[i-1]; } for (i = len - 1; i >= 0; i--) { index = get_index(arr[i], dec, order); j = --num[index]; tmp[j] = arr[i]; } for (i = 0; i < len; i++) { arr[i] = tmp[i]; } RadixSort(arr, len, dec, order+1); }
Java版
/** * 基数排序 * @param array * @return * @date 2022/01/20 */ public static int[] RadixSort(int[] array) { if (array == null || array.length < 2) return array; // 1.先算出最大数的位数； int max = array[0]; for (int i = 1; i < array.length; i++) { max = Math.max(max, array[i]); } int maxDigit = 0; while (max != 0) { max /= 10; maxDigit++; } int mod = 10, div = 1; ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < 10;i++){ bucketList.add(new ArrayList<Integer>()); } for(int i = 0;i < maxDigit;i++,mod *= 10 ,div *= 10){ for(int j = 0;j < array.length;j++){ int num = (array[j] % mod) / div; bucketList.get(num).add(array[j]); } int index = 0; for(int j = 0;j < bucketList.size();j++){ for(int k = 0;k < bucketList.get(j).size();k++){ array[index++] = bucketList.get(j).get(k); } bucketList.get(j).clear(); } } return array; }
🦴 附件
术语说明
- 稳定：如果a原本在b前面，而a=b,排序之后a仍然在b的前面；
- 不稳定：如果a原本在b前面，而a=b,排序之后a有可能会出现在b的后面；
- 时间复杂度：描述算法运行时间的函数，用大O符号表述；
- 空间复杂度：描述算法所需要的内存空间大小。
