Radix Sort

共计 3408 个字符，预计需要花费 9 分钟才能阅读完成。

Radix sort is a non-comparative sorting algorithm that works by processing individual digits or characters of elements within a collection (e.g., integers or strings) from the least significant digit (or character) to the most significant digit (or character) or vice versa. It’s called “radix” because it sorts based on the value of digits or characters’ positions within the elements.

Here’s a general overview of how radix sort works:

1. Determine the maximum number of digits or characters: Before sorting, you need to find the maximum number of digits or characters in the elements you want to sort. This determines the number of passes the algorithm needs to perform.
2. Passes: Radix sort performs a series of passes, starting from the least significant digit (or character) and moving towards the most significant one or vice versa. In each pass, it distributes the elements into buckets based on the value of the digit (or character) at the current position. For example, if you’re sorting integers, you would use 10 buckets (0-9) for each digit position.
3. Bucketing: During each pass, the elements are distributed into buckets based on the value of the current digit or character. Elements with the same digit (or character) value go into the same bucket.
4. Collecting: After each pass, the elements are collected from the buckets in a specific order. The order depends on whether you’re sorting from the least significant digit to the most significant or vice versa.
5. Repeat: Steps 3 and 4 are repeated for each digit position, moving from the least significant to the most significant or vice versa. After processing all digits (or characters), the elements are sorted.
6. Final Sorted Array: The result is a sorted collection.

Radix sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements. It has a linear time complexity of O(n * k), where “n” is the number of elements to be sorted, and “k” is the number of digits or characters in the maximum element. Radix sort is particularly useful when sorting integers with a fixed number of digits, and it can be faster than some other sorting algorithms like quicksort or merge sort in specific situations. However, it’s not as commonly used as some other sorting algorithms due to its limited applicability.

Radix sort is a non-comparative sorting algorithm that works by distributing elements into buckets based on their individual digits or characters. It sorts numbers or strings by processing each digit or character from the least significant to the most significant digit or character. Here’s a simple implementation of radix sort in C for sorting an array of integers:

#include <stdio.h>
#include <stdlib.h>

// Function to find the maximum number in the array
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// Function to perform counting sort based on a specific digit
void countSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Radix Sort function
void radixSort(int arr[], int n) {
    int max = getMax(arr, n);

    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    radixSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

This C program demonstrates radix sort for sorting an array of integers. It first finds the maximum number in the array to determine the number of digits, and then it performs counting sort for each digit from the least significant to the most significant digit. Finally, it prints the sorted array.