c语言实现基数排序解析及代码示例

前言

基数排序是一种特殊的排序算法，它的时间复杂度为O(dn)，其中d表示数据位数，n表示数据个数。它可以用于排序整数、字符串、链表等数据类型。本篇攻略通过讲解基数排序的原理、流程和C语言实现，希望能够帮助大家更好地理解和应用基数排序算法。

基数排序原理

基数排序是一种非比较排序算法，它的实现基于按照键值的每位数字对待排序数据进行排序的方法。在排序过程中，待排序的数据需要拆分成若干个位数，然后分别按照个位、十位、百位等位数进行排序，最终得到一个有序的结果。

基数排序流程

基数排序的排序流程分为两个阶段：

1. 按位排序：需要对每一位数字进行排序，可以将待排序的数据拆分成若干个数字，然后依次按照每个数字进行排序，最终得到一个排好序的序列。
2. 收集排序结果：将按位排序后的结果按照顺序收集起来，得到一个有序的序列。

基数排序的排序流程可以用下面的伪代码来表示：

radix_sort(arr, n):
    max_value = find_max_value(arr, n)
    exp = 1
    while max_value // exp > 0:
        counting_sort(arr, n, exp)
        exp *= 10
    return arr

其中，find_max_value函数用于找到待排序数据中的最大值；counting_sort函数用于按照指定位数对数据进行排序。

基数排序示例

下面通过两个示例来说明基数排序的具体实现过程。

示例1：按照个位数排序

假设我们有以下10个数需要进行排序：[34, 23, 67, 89, 123, 235, 665, 999, 1, 5]。按照个位数进行排序，我们可以拆分每个数的个位数字并放到对应的桶子中，桶子的下标表示数字，桶子的值表示该数字出现的次数。例如，对于数值34来说，我们可以将它的个位数字4放到下标为4的桶子中，桶子的值加1。对于数值123来说，我们可以将它的个位数字3放到下标为3的桶子中，桶子的值加1。最终，按照个位数字排序后的结果为[1, 5, 67, 89, 123, 235, 34, 665, 999]。

示例2：按照十位数排序

假设我们有以下10个数需要进行排序：[34, 23, 67, 89, 123, 235, 665, 999, 1, 5]。按照十位数进行排序，我们可以拆分每个数的十位数字并放到对应的桶子中，桶子的下标表示数字，桶子的值表示该数字出现的次数。例如，对于数值34来说，我们可以将它的十位数字0放到下标为0的桶子中，桶子的值加1（由于34的十位数字是个位数字，所以放到下标为0的桶子中）。对于数值123来说，我们可以将它的十位数字2放到下标为2的桶子中，桶子的值加1。最终，按照十位数字排序后的结果为[1, 5, 23, 34, 67, 89, 123, 235, 665, 999]。

基数排序C语言代码示例

下面是基数排序的C语言实现代码：

void counting_sort(int arr[], int n, int exp) {
    int i, bucket[10] = {0}, output[n];
    for (i = 0; i < n; i++)
        bucket[(arr[i] / exp) % 10]++;
    for (i = 1; i < 10; i++)
        bucket[i] += bucket[i - 1];
    for (i = n - 1; i >= 0; i--) {
        output[bucket[(arr[i] / exp) % 10] - 1] = arr[i];
        bucket[(arr[i] / exp) % 10]--;
    }
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

int find_max_value(int arr[], int n) {
    int max_value = arr[0], i;
    for (i = 1; i < n; i++) {
        if (arr[i] > max_value)
            max_value = arr[i];
    }
    return max_value;
}

void radix_sort(int arr[], int n) {
    int max_value = find_max_value(arr, n), exp = 1;
    while (max_value / exp > 0) {
        counting_sort(arr, n, exp);
        exp *= 10;
    }
}

其中，counting_sort函数用于按照指定位数对数据进行排序，find_max_value函数用于找到待排序数据中的最大值，radix_sort函数用于调用以上两个函数进行基数排序。

基数排序的具体实现过程相对来说比较简单，主要是按位排序和收集排序结果两个步骤。但是，基数排序在排序整数等类型数据时效果比较明显，而在排序字符串等复杂类型时需要选取合适的位数进行排序，这也是需要注意的地方。