基于C语言的基数排序算法

一、基数排序简介

        基数排序是一种非比较整数排序算法，其原理是按数字的各位依次进行排序，属于稳定性排序。

        基数排序是一种高效的排序算法，它的时间复杂度为 O(d(n + r))，其中 d是数字的位数，n是待排序元素的数量，r 是基数，通常为 10（十进制）。空间复杂度为 O(n + r)。

        基数排序的基本思想是将整数按位数分割成不同的数字，然后按每个位数分别进行排序。它通过使用计数排序或桶排序作为辅助算法来实现高效的排序。

        例如，对于一个包含整数的数组，首先找出最大的数字，并确定其位数。然后从最低位开始，对每个数字的对应位进行计数排序或桶排序，将数字分配到不同的桶中，再按照桶的顺序依次取出数字，放回原数组。接着，对下一位进行同样的操作，直到最高位排序完成。

        在实际应用中，基数排序适用于处理大量整数的排序问题，尤其是当整数的位数相对固定且数量较大时，它的性能优势更加明显。

        基数排序的优点在于它不需要进行比较操作，因此在某些情况下可以比其他排序算法更快。此外，它是一种稳定性排序，即相同值的元素在排序后保持相对顺序不变。

        然而，基数排序也有一些限制。它需要额外的空间来存储桶或计数数组，并且对于位数较多的整数，可能需要进行多次遍历和排序操作。

        总之，基数排序是一种有效的整数排序算法，适用于特定的应用场景。在选择排序算法时，需要根据具体问题的特点和要求来综合考虑各种因素。

二、排序思想

        基数排序的基本思路是将待排序的数据按照位数进行拆分，然后从最低位开始，依次对每一位进行排序。具体来说，首先根据数据的个位数字将数据分配到不同的桶中，然后按照桶的顺序依次收集数据，得到按个位数字排序后的序列。接着，再根据十位数字进行分配和收集，依次类推，直到最高位排序完成。

        以一组数据为例，假设有数据 64、8、216、512、27、729、0、1、343、125。首先，按照个位数字进行分配，将个位数字为 0 的数据放入第 0 个桶，个位数字为 1 的数据放入第 1 个桶，以此类推。分配完成后，按照桶的顺序依次收集数据，得到按个位数字排序后的序列。然后，再按照十位数字进行分配和收集，重复这个过程，直到最高位排序完成。

        在这个过程中，每一位的排序都是通过桶的概念来实现的。每个桶可以看作是一个链表，用来存储具有相同位数数字的数据。在分配过程中，将数据根据其位数数字放入相应的桶中。在收集过程中，按照桶的顺序依次将数据从桶中取出，放回原序列中，从而实现对数据的排序。

三、代码实现

（一）示例代码分析

以下是使用 C 语言实现基数排序的代码示例分析：

#include <stdio.h>
#include <stdlib.h>// 获取数字的指定位数上的数值
// 参数说明：
// num：要获取位数的数字
// digit：指定的位数（从右往左数，个位为第 1 位）
int getDigit(int num, int digit) 
{int temp = 1;// 通过循环生成指定位数对应的基数（如获取十位，temp 为 10）for (int i = 0; i < digit - 1; i++) {temp *= 10;}// 获取指定的数字，并返回该位上的数值return (num / temp) % 10;
}// 基数排序函数
// 参数说明：
// arr：待排序的数组
// n：数组的长度
void radixSort(int arr[], int n) 
{int maxVal = arr[0];// 找出数组中的最大值for (int i = 1; i < n; i++) {if (arr[i] > maxVal) {maxVal = arr[i];}}int maxDigit = 0;// 计算最大值的位数while (maxVal > 0) {maxVal /= 10;maxDigit++;}// 定义一个指针数组，每个指针指向一个整数数组，用于存储不同位数上的数字int* buckets[10];for (int i = 0; i < 10; i++) {// 为每个桶分配内存空间，每个桶可以存储 n 个整数buckets[i] = (int*)malloc(n * sizeof(int));}// 初始化每个桶的大小为 0int bucketSizes[10] = {0};// 对每一位进行排序for (int digit = 1; digit <= maxDigit; digit++) {for (int i = 0; i < n; i++) {// 获取当前数字在当前位数上的值int currentDigit = getDigit(arr[i], digit);// 将数字放入对应的桶中，并增加桶的大小buckets[currentDigit][bucketSizes[currentDigit]++] = arr[i];}int index = 0;// 将桶中的数字依次取出，放回原数组for (int i = 0; i < 10; i++) {for (int j = 0; j < bucketSizes[i]; j++) {arr[index++] = buckets[i][j];}// 重置桶的大小为 0，为下一次排序做准备bucketSizes[i] = 0;}}// 释放每个桶占用的内存空间for (int i = 0; i < 10; i++) {free(buckets[i]);}
}// 打印数组函数
// 参数说明：
// arr：要打印的数组
// n：数组的长度
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("原始数组：");printArray(arr, n);// 调用基数排序函数对数组进行排序radixSort(arr, n);// 输出排序后的数组printf("排序后的数组：");printArray(arr, n);return 0;
}

• 代码首先定义了获取数字指定位数上数值的函数getDigit。然后在radixSort函数中，先找到数组中的最大值并确定其位数。接着创建了 10 个桶，每个桶对应一个数字范围（0-9）。
• 在每次循环中，根据当前位数将数字分配到相应的桶中，然后再从桶中收集数字放回原数组。最后释放桶的内存空间。

（二）致命缺陷及解决方法

        基数排序当前程序可能存在只能排正数的问题。解决方法之一是在排序之前将数组全部加上一个常数，使其变成正数，然后排序完成后减去这个常数。具体实现步骤如下：

1. 首先找出数组中的最小值，如果最小值小于零，那么需要给所有元素加上最小值的绝对值，因为基数排序实际上只能给正数排序。
2. 进行基数排序，按照正数的方式进行排序操作。
3. 排序完成后，如果最小值小于零，将数组中的元素减去之前加上的最小值的绝对值，恢复原始数据的状态。

        通过这种方式，可以解决基数排序不能处理负数的问题，使得基数排序可以适用于包含负数的数组。

四、性能分析

（一）时间复杂度

        基数排序的时间复杂度为 O(d(n + r))，其中 d是数字的位数，n 是待排序元素的数量，r 是基数，通常为 10（十进制）。在最好情况下，当待排序元素的位数较少且分布较为均匀时，基数排序的时间复杂度接近 O(n)。这是因为在每一轮对特定位数进行排序时，分配和收集操作的时间复杂度与元素数量和基数有关，而如果位数较少且分布均匀，那么总的时间复杂度就会较低。

        例如，对于一个包含 1000个三位数的整数数组，进行基数排序时，首先需要对个位、十位和百位分别进行排序。每一轮排序中，最多需要遍历 1000个元素，将它们分配到 10个桶中，然后再收集起来。因此，每一轮的时间复杂度为 O(1000 + 10)，即 O(1010)。由于有三位数字需要排序，所以总的时间复杂度为 O(3*1010)，近似为O(n)。

（二）空间复杂度

        基数排序的空间复杂度为 O(n + r)。其中， n 是待排序元素的数量，r 是基数。空间复杂度主要来源于存储桶或计数数组的空间。在基数排序过程中，需要创建多个桶或计数数组来存储中间结果。例如，在十进制基数排序中，需要创建 个桶来存储不同位数的数字。每个桶的大小取决于待排序元素的数量，因此总的空间复杂度为 O(n + r)。

        以一个包含 个整数的数组为例，进行基数排序时，需要创建 10个桶，每个桶最多可以存储 10个元素。因此，总的空间复杂度为 O(500 + 10)，即 O(510)，近似为 O(n)。

（三）稳定性

        基数排序是一种稳定的排序算法。稳定性是指在排序过程中，相等元素的相对顺序不会改变。基数排序之所以是稳定的，是因为在每一轮对特定位数进行排序时，采用的是稳定的计数排序或桶排序方法。例如，在对个位数字进行排序时，如果有多个数字的个位数字相同，那么它们在桶中的顺序与在原数组中的顺序是一致的。在后续的十位、百位等位数的排序过程中，也会保持这种相对顺序不变。

        举个例子，有一个整数序列 52, 51, 52，在进行基数排序时，首先对个位数字进行排序，由于三个数字的个位数字分别为 2, 1, 2，所以排序后的序列为 51, 52, 52。接着对十位数字进行排序，由于三个数字的十位数字都是 5，所以它们在桶中的顺序与在原数组中的顺序一致，即 51, 52, 52。最终排序结果仍然保持了相等元素的相对顺序不变。

五、总结

        基数排序在 C 语言中的应用具有重要的价值。它为处理整数排序问题提供了一种高效的方法，尤其是在处理大量整数且整数位数相对固定的情况下。

        基数排序的高效性在于其时间复杂度相对较低，在特定场景下可以接近线性时间复杂度 O(n)。这使得它在处理大规模数据时具有明显的优势，能够快速地完成排序任务。

        然而，基数排序也存在一定的局限性。它需要额外的空间来存储桶或计数数组，这在处理非常大的数据集时可能会导致内存占用过高的问题。此外，基数排序对于位数较多的整数可能需要进行多次遍历和排序操作，这也会增加计算时间。

        尽管如此，在特定的应用场景下，基数排序仍然是一种非常实用的排序算法。例如，在处理小规模数据集或者整数位数较少的情况下，基数排序可以快速地完成排序任务，并且具有稳定性的特点，能够保证相等元素的相对顺序不变。

        总之，基数排序在 C 语言中的应用既有价值又有局限性。在实际应用中，我们需要根据具体的问题特点和要求，综合考虑各种因素，选择合适的排序算法。如果数据规模较小、整数位数较少且对稳定性有要求，那么基数排序是一个不错的选择。而对于大规模数据集或者位数较多的整数，可能需要结合其他排序算法或者进行优化，以提高排序效率和减少内存占用。