java 基数排序算法-ag捕鱼王app官网

在基数排序算法中，元素的排序首先将具有相同位值的单个数字分组，然后按照升序或降序排序。本教程详细解释了基数排序算法，并演示了 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]