基数排序的思想是，输入数据的排序是从最低有效位到最高有效位逐位进行的，它使用计数排序作为子例程来执行排序。计数排序是一种线性排序算法，在所有情况下总时间复杂度为 θ(N+K)，其中 N 是未排序数组中的元素数量， K是输入数据的范围。基数排序的思想是扩展计数排序算法，以便在K上升时获得更好的时间复杂度。
示例:
理解基数排序，让我们考虑一个未排序的数组 A = [101, 1, 20, 50, 9, 98, 27, 153, 35, 899] 并讨论按升序对数组进行排序所采取的每个步骤。
第 1 步:根据算法，输入数据首先根据最低有效位进行排序。因此，数组A[]是根据数字排序的。按数字排序后，将变为[20, 50, 101, 1, 153, 35, 27, 98, 9, 899]。
第 2 步:在这一步中，数组 A[ ] 数组按照十位进行排序，经过这一步后，它将变成 [101, 1, 9, 20, 27, 35, 50, 153, 98, 899]。
第 3 步:最后，数组 A[ ] 根据百位（最高有效位）排序，数组将在此步骤之后进行排序，最终数组将为[1, 9, 20, 27, 35, 50, 98, 101, 153, 899]。
基数排序的实现
public class MyClass {
// 基数排序函数
static void radixsort(int Array[]) {
int n = Array.length;
int max = Array[0];
//查找数组中最大的元素
for (int i=1; i<n; i++) {
if(max < Array[i])
max = Array[i];
}
//按照地点进行计数排序。
//比如个位、十位等等。
for (int place = 1; max/place > 0; place *= 10)
countingsort(Array, place);
}
static void countingsort(int Array[], int place) {
int n = Array.length;
int[] output = new int[n];
//对于每个考虑的地方，数字的范围是0-9。
int[] freq = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//计算freq数组中出现的次数
for(int i = 0; i < n; i++)
freq[(Array[i]/place)%10]++;
//更改 count[i] 以便 count[i] 现在包含实际的
//该数字在输出[]中的位置
for (int i = 1; i < 10; i++)
freq[i] += freq[i - 1];
//构建输出数组
for (int i = n - 1; i >= 0; i--) {
output[freq[(Array[i]/place)%10] - 1] = Array[i];
freq[(Array[i]/place)%10]--;
}
//将输出数组复制到输入数组，现在数组将
//包含基于指定位置的数字排序的数组
for (int i = 0; i < n; i++)
Array[i] = output[i];
}
//打印数组的函数
static void PrintArray(int Array[]) {
int n = Array.length;
for (int i=0; i<n; i++)
System.out.print(Array[i] + " ");
System.out.println();
}
//测试代码
public static void main(String[] args) {
int[] MyArray = {101, 1, 20, 50, 9, 98, 27, 153, 35, 899};
System.out.println("原始数组");
PrintArray(MyArray);
radixsort(MyArray);
System.out.println("\n排序数组");
PrintArray(MyArray);
}
} 上述代码将给出以下输出:
原始数组
101 1 20 50 9 98 27 153 35 899
排序数组
1 9 20 27 35 50 98 101 153 899 时间复杂度:
基数排序的时间复杂度为θ((N+b)*log b(max)) 在所有情况下，其中:
- N 是未排序数组中的元素数量。
- b 是输入数组的基数，例如，对于十进制系统，b 为 10。
- max 是输入数组的最大元素。