编辑代码

#include <stdio.h>

// 获取数组中的最大值
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;
}

// 使用计数排序对数组按照指定位数进行排序
void countingSort(int arr[], int n, int exp) {
    const int MAX_DIGIT = 10;  // 假设数字的基数是10
    int* output = (int*)malloc(n * sizeof(int)); // 输出数组
    int* count = (int*)malloc(MAX_DIGIT * sizeof(int)); // 计数数组
    if (output == NULL || count == NULL) {
        // 处理内存分配失败的情况
        printf("Memory allocation failed\n");
        free(output);
        free(count);
        return;
    }
    // 初始化计数数组
    for (int i = 0; i < MAX_DIGIT; i++) {
        count[i] = 0;
    }
    // 统计每个数字出现的次数
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % MAX_DIGIT]++;
    }
    // 将计数数组转换为累积计数数组
    for (int i = 1; i < MAX_DIGIT; i++) {
        count[i] += count[i - 1];
    }
    // 构建输出数组
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % MAX_DIGIT] - 1] = arr[i];
        count[(arr[i] / exp) % MAX_DIGIT]--;
    }
    // 将输出数组复制到原始数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    // 释放动态分配的内存
    free(output);
    free(count);
}

// 基数排序函数
void radixSort(int arr[], int n) {
    // 获取数组中的最大值，以确定需要遍历的位数
    int max = getMax(arr, n);
    // 对每一位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; 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("测试一：原始数组: ");
    printArray(arr, n);
    // 调用基数排序函数
    radixSort(arr, n);
    printf("测试一：排序后数组: ");
    printArray(arr, n);

    int arr1[] = {39, 13, 100, 10, 1, 250};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("测试二：原始数组: ");
    printArray(arr1, n1);
    // 调用基数排序函数
    radixSort(arr1, n1);
    printf("测试二：排序后数组: ");
    printArray(arr1, n1);

    int arr2[] = {99,111, 34, 23, 50, 88};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("测试二：原始数组: ");
    printArray(arr2, n2);
    // 调用基数排序函数
    radixSort(arr2, n2);
    printf("测试二：排序后数组: ");
    printArray(arr2, n2);
    
    return 0;
}