什么是基数排序算法？详述基数排序算法的原理？用C语言实现基数排序算法。内附完整代码。

大家好，我是贤弟！

一、什么是基数排序？

基数排序是一种非比较排序算法，它的原理是根据数字的位数来进行排序。将每个数字按照一定的规则分配到桶中，然后依次取出桶中的数字，形成有序序列。

二、基数排序的步骤

基数排序的具体步骤如下：

1、找出待排序数组中最大的数字，并统计其位数。

2、设定一个位数计数器，从个位开始到最高位，对每一位上的数字进行基数排序（一般采用十进制）。

3、将每一位上的数字依次放入对应的桶中，并按照桶的顺序依次输出所有数字。重复此过程，直到完成对最高位的排序。

三、代码示例

以下是用C语言实现基数排序算法的代码：

void counting_sort(int arr[], int n, int exp) { int* count = (int*)calloc(10, sizeof(int)); int* output = (int*)malloc(n * sizeof(int));

// 统计每个数字出现的次数 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]; }

free(count); free(output);}

void radix_sort(int arr[], int n) { // 找出最大值并确定位数 int max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } int exp; for (exp = 1; max / exp > 0; exp *= 10) { counting_sort(arr, n, exp); }}