深入解析Radix Sort基数排序算法思想及C语言实现示例

什么是基数排序算法

基数排序即Radix Sort，是一种非比较型排序算法。相比于其他排序算法，如快速排序、归并排序等，基数排序的时间复杂度较为稳定，且不受数据规模的影响，适用于数据范围较小但位数较多的序列排序。

基数排序算法思想

基数排序算法的核心思想是按照不同位数上的数字对数据进行排序，从低位到高位遍历数据，并将每一个位数上的数字作为key，将数据存储到桶中，最后通过对桶中的数据顺序进行排列，得到有序的数据序列。

以三位数为例，对于数据序列：{ 53, 87, 62, 24, 13 }，首先从个位开始遍历数据，将数据存储到0~9范围内共10个桶中，根据桶中的顺序重新输出数据序列为{ 53, 62, 13, 24, 87 }。接着从十位开始遍历，将数据存储到桶中并重新排序输出，得到序列{ 13, 24, 53, 62, 87 }。最后再从百位开始遍历，重复以上过程，得到有序数据序列。

基数排序算法C语言实现示例1

void radix_sort(int* arr, int len, int max_digit) {
    int* tmp = (int*)malloc(len * sizeof(int));
    int i, j, k, radix;
    int* count = (int*)malloc(10 * sizeof(int));
    for (k = 0; k < max_digit; k++) {
        memset(count, 0, sizeof(int) * 10);
        radix = (int)pow(10, k);
        for (i = 0; i < len; i++) {
            j = (arr[i] / radix) % 10;
            count[j]++;
        }
        for (i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        for (i = len - 1; i >= 0; i--) {
            j = (arr[i] / radix) % 10;
            tmp[--count[j]] = arr[i];
        }
        for (i = 0; i < len; i++) {
            arr[i] = tmp[i];
        }
    }
    free(count);
    free(tmp);
}

该示例使用动态内存分配，通过pow函数获取radix值，实现了基数排序算法的主体框架。借助桶进行数据的存储与排序。

基数排序算法C语言实现示例2

void radix_sort(int* arr, int len, int max_digit) {
    int radix = 1;
    int* tmp_arr = (int*)malloc(len * sizeof(int));
    int* count_arr = (int*)malloc(10 * sizeof(int));
    int i, j, k;
    for (i = 1; i <= max_digit; i++) {
        memset(count_arr, 0, 10 * sizeof(int));
        for (j = 0; j < len; j++) {
            k = (arr[j] / radix) % 10;
            count_arr[k]++;
        }
        for (j = 1; j < 10; j++) {
            count_arr[j] += count_arr[j - 1];
        }
        for (j = len - 1; j >= 0; j--) {
            k = (arr[j] / radix) % 10;
            tmp_arr[--count_arr[k]] = arr[j];
        }
        for (j = 0; j < len; j++) {
            arr[j] = tmp_arr[j];
        }
        radix = radix * 10;
    }
    free(count_arr);
    free(tmp_arr);
}

该示例使用了全局变量radix，不采用pow函数获取radix值。同时，将申请内存的操作放入了函数内部，通过循环实现了对桶的遍历、统计和排序，实现了基数排序的核心算法。

总结

基数排序算法是一种高效的排序算法，通过不同位数上的排列实现数据序列的有序性，适用于数据位数多、数据范围小的的数据排序场景。C语言提供了较为便捷的动态内存分配和指针操作，方便了算法的实现。