迹忆客 专注技术分享

在基数排序算法中，元素的排序首先将具有相同位值的单个数字分组，然后按照升序或降序排序。本教程详细解释了基数排序算法，并演示了 Java 中基数排序的实现。

基数排序算法

按照以下步骤应用基数排序。

1. 首先从输入数组中找到最大元素；然后，该最大数量将用于遍历所有数组成员的重要位置。
2. 接下来，一个一个地走过每个重要的地方。我们可以使用任何稳定的排序算法，例如计数排序，对每个重要位置的元素进行排序。

支持六个元素的数组。radix sort 将首先根据单位位置的值对元素进行排序。

然后根据第十位的值对数组的元素进行排序。

假设数组是 [9, 50, 4, 203, 17, 39]。下图显示了这个数组根据 radix sort 进行了多次排序。

基数排序算法的时间复杂度

下表显示了 radix sort 算法在不同情况下的时间复杂度。

1. 最佳情况 - 当不需要排序时，数组已经排序。在最佳情况下，基数排序时间复杂度是Ω(n+k)。
2. 平均情况 - 数组元素的顺序混乱，没有正确的降序或升序。在平均情况下，基数排序时间复杂度是θ(nk)。
3. 最坏情况 - 当数组元素必须以相反的顺序排序时，例如从升序到降序或从降序到升序。在最坏的情况下，基数排序时间复杂度是 O(nk)。

基数排序算法的伪代码

基数排序算法的伪代码如下。

Radix_Sort(Input_Array)
    MAX = largest number in the input array
    DIGIT = number of digits in the largest number
    Now, create DIGIT buckets of size 0 - 9
    for x -> 0 to DIGIT
        sort the elements according to any stable sort

Java 中的基数排序算法实现

使用计数排序，让我们实现基数排序算法。参见示例：

package delftstack;

import java.util.Arrays;

public class Radix_Sort {

    public static void main(String args[]) {
        int[] input_array = { 9, 50, 4, 203, 17, 39};
        int array_size = input_array.length;
        Radix_Sort RadixSort = new Radix_Sort();
        RadixSort.Radix_Sort(input_array, array_size);
        System.out.println("Sorted Array Using Radix Sort: ");
        System.out.println(Arrays.toString(input_array));
    }


    // Counting sort to sort the elements on the basis of significant places
    void Counting_Sort(int input_array[], int array_size, int number_place) {
        int[] output_array = new int[array_size + 1];
        int max_number = input_array[0];
        for (int x = 1; x < array_size; x++) {
            if (input_array[x] > max_number) {
                max_number = input_array[x];
            }
        }
        int[] count_array = new int[max_number + 1];

        for (int x = 0; x < max_number; ++x) {
        	count_array[x] = 0;
        }
        // Calculating the count of elements
        for (int x = 0; x < array_size; x++) {
        	count_array[(input_array[x] / number_place) % 10]++;
        }
        // Calculating the cumulative count
        for (int x = 1; x < 10; x++) {
        	count_array[x] += count_array[x - 1];
        }
        // Sorting the elements
        for (int x = array_size - 1; x >= 0; x--) {
        	output_array[count_array[(input_array[x] / number_place) % 10] - 1] = input_array[x];
        	count_array[(input_array[x] / number_place) % 10]--;
        }

        for (int x = 0; x < array_size; x++) {
            input_array[x] = output_array[x];
        }
    }

    // Get the largest element from input array
    int Get_Max(int input_array[], int array_size) {
        int max_number = input_array[0];
        for (int i = 1; i < array_size; i++) {
            if (input_array[i] > max_number) {
            	max_number = input_array[i];
            }
        }
        return max_number;
    }

    // Implement the radix sort
    void Radix_Sort(int input_array[], int array_size) {

        // Get the maximum number
        int max_number = Get_Max(input_array, array_size);

        // Apply the counting sort based on significant place value.
        for (int number_place = 1; max_number / number_place > 0; number_place *= 10) {
        	Counting_Sort(input_array, array_size, number_place);
        }
    }
}

上面的代码在 counting sort 的帮助下实现了基数排序。见输出：

Sorted Array Using Radix Sort:
[4, 9, 17, 39, 50, 203]