前言
本文重点讲解十大经典排序算法的基数排序
要点
基数排序(Radix Sort)属于分配式排序算法。
在计算机科学中,基数排序是一种非比较的整数排序算法,它通过用分享相同重要的位置和值方法分类得来的整数键来对数据进行排序。
该排序需要位置表示法,但是由于整数可以表示字符串(例如名称或日期) 和特殊格式化的浮点数,基数排序的对象可以不限于整数。
基数排序可以追溯到1887年赫尔曼·霍勒里斯在制表机上的工作。
代码实现
以下代码由java实现
public class RadixSort {
/**
* 基数排序
* @param arr
* @return
*/
public static int[] sort(int[] arr) {
if (arr.length <= 0) {
return null;
}
int maxLenght = getMaxLenght(arr);
// 初始长度
int initialLenght = 10;
// 初始化位数
int initialDigit = 1;
for (int i = 0; i < maxLenght; i++, initialDigit *= 10) {
// 第一维表示排序对应的位数 initialLenght * 2 为了防止有负数情况 0-9 为负数 10-19 为正数
int[][] counterArr = new int[initialLenght * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] / initialDigit) % initialLenght) + initialLenght;
// 扩容
counterArr[bucket] = Arrays.copyOf(counterArr[bucket], counterArr[bucket].length + 1);
// 当前桶位置赋值
counterArr[bucket][counterArr[bucket].length - 1] = arr[j];
}
int o = 0;
for (int[] bucket : counterArr) {
for (int num : bucket) {
arr[o++] = num;
}
}
}
return arr;
}
/**
* 获取最高位数
*/
public static int getMaxLenght(int[] arr) {
int max = 0;
for (int num : arr) {
if (max < num) {
max = num;
}
}
if (max == 0) {
return 1;
}
int lenght = 0;
for (; max != 0; max /= 10) {
lenght++;
}
return lenght;
}
public static void main(String[] args) {
int[] arr = {9, 5, 3, 6, 8, 1, 2, 3, 11, 52, 32, 11, 23, -9, -5};
System.out.println(Arrays.toString(sort(arr)));
}
}
时间性能
时间复杂度为$O(nlog(r)m)$,其中r为所采取的基数,而m为堆数,基数排序法的效率高于其它的稳定性排序法,但使用范围较窄。
空间复杂度
在基数排序过程中,对于任何位数上的基数进行$装桶$操作时,都需要n+m个临时空间,所以空间复杂度为$O(n+m)$。
稳定性
在基数排序过程中,每次都是将当前位数上相同数值的元素统一装桶,并进行先进先出策略,不需要交换位置,所以基数排序是稳定的算法。