C语言实现基数排序算法

"这篇文档是关于C语言实现的基数排序算法。它提供了一个完整的基数排序函数`RadixSort`，并结合了计数排序作为基数排序的一部分。代码中包括了计数排序函数`RadixCountSort`，以及处理不同位数的循环结构，确保了排序的稳定性。" 基数排序是一种非比较型整数排序算法，它的原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。这个文档中介绍的基数排序是通过多次计数排序来实现的，因为计数排序对于一定范围内的整数可以达到线性时间复杂度。 首先，我们来看`RadixCountSort`函数。这个函数接收四个参数：`npIndex`是关键字序列，`nMax`是关键字的范围，`npData`是要排序的实际数据，`nLen`是数据的范围。它首先利用动态内存分配创建一个计数数组`pnCount`，大小与`nMax`相同，用于存储每个关键字出现的次数。接着，遍历数据，更新计数数组。然后，通过对计数数组的累加，计算出每个关键字在排序后的位置。最后，使用另一个临时数组`pnSort`进行排序，并将结果复制回原数组`npData`。 接下来是`RadixSort`函数，这是整个基数排序的核心。它首先申请一个与输入数据同样大小的辅助数组`nDataRadix`，用于存储不同位数的排序结果。然后，初始化基数`nRadixBase`为1，并设置一个标志`nIsOk`来判断是否已完成排序。在循环中，每次乘以10增加基数，意味着处理下一个位数。循环会持续到所有位数都被处理，即排序完成。 循环内部，`RadixSort`调用`RadixCountSort`来对当前位数进行排序。这个过程不断重复，直到`nIsOk`为真，表示所有位数都已经处理完毕。最后，释放辅助数组`nDataRadix`和计数数组`pnCount`，以释放内存。 这份文档提供了C语言实现基数排序的详细步骤，包括如何利用计数排序处理每个位数，以及如何通过迭代增加基数来处理所有位数。这种排序方法适用于处理大量整数且数值范围较小的情况，能有效提高排序效率。