基数排序的两种实现方法--Radix Sort

基数排序的基本思路

对于一个输入数组，我们有如下形式：

我们按照最低位优先的顺序进行排序（也可以按照最高位优先的顺序进行排序）
第一趟排序后的桶：

第二趟排序后的桶：

如果待排数组中存在三位数或者四位数，此时还必须进行第三趟排序或者进行第四趟排序，假设把上述输入数组中的数组元素92改为192，那我们就必须进行第三趟排序（第一次和第二次排序和上述过程相同）：
第三趟排序后的桶：

这里需要声明一点：输入数组只对第一次排序有效，对于第二次和第三次排序均是基于前一次的排序完成之后的桶再次进行排序的。
对于基数排序的思路，YouTube和GeeksforGeeks网站上有详细的视频和图片解释。
点击打开网址

数组实现

我们给出数组实现基数排序的完整代码和详细分析。
完整代码如下：

//radix_sort
#include<stdio.h>
#include<stdlib.h>

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

void
Count_Sort(int arr[], int n, int exp)
{
    //in the vc6.0 complier environment, the size of array output must be given
    //but for other complier, the size of array could be 'n'
    int i, count[10] = {0};
    int output[10];
//  int output[n];

    //store count of occurrences in count[]
    for(i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // Change count[i] so that count[i] now contains actual
    // position of this digit in output[]
    for(i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array
    //for(i = 0; i < n; i--)
    for(i = n - 1; i >= 0; i--)
    {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
//      over code's explainition detailedly
//      int tmp = count[(arr[i] / exp) % 10];
//      int x = count[tmp];
//      output[x - 1] = arr[i];
//      x--;
    }

    for(i = 0; i < n; i++)
        arr[i] = output[i];
}

void
Radix_Sort(int arr[], int n)
{
    int exp;
    int m = Get_Max(arr, n);
    for(exp = 1; m / exp > 0; exp *= 10)
        Count_Sort(arr, n, exp);
}

void
Print_Arr(int arr[], int n)
{
    int i;
    for(i = 0; i < n; i++)
        printf("%dn", arr[i]);
}

void
main()
{
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    Radix_Sort(arr, n);
    Print_Arr(arr, n);
}

可以这么说，数组实现的基数排序严格遵守了上述排序思路。下面，我们就来看一看链表实现的基数排序。

链表实现

对于链表实现的排序思路，和数组实现的稍有不同。我们可以采用链表数组的方法实现。

typedef struct bucket_node
{
    int value;
    bucket_node *next;
}BUCKET;
BUCKET bucket[10] = {0, };      //creat the linked list of array

输入数组：

这次，采用最高位优先的顺序进行排序。

为了达到以上的效果，我们需要对输入数组做以下处理：
1. 计算输入数组的最大值–max
2. 计算输入数组中最大值的位数–maxdigital
具体代码如下：

int 
get_max_digital_count(int *array, int length)
{
    assert(array && length > 0);
    int i = 0;
    int max = array[0];
    int maxdigital = 0;
    int tmp;

    for(i = 1; i < length; i++)
    {//count the maximum 
        if(array[i] > max)
            max = array[i];
    }
    while(max > 0)
    {
        max /= 10;
        ++maxdigital;
    }
    return maxdigital;
}

具体的链表实现过程如下：

void
bucket_sort(int *array, int length)
{
    assert(array && length >= 0);
    if(length <= 1)
        return;
    int i, index;
    BUCKET *tmp = NULL;
    BUCKET bucket[10] = {0, };
    int count = get_max_digital_count(array, length);
    BUCKET *data = (BUCKET *)malloc(length * sizeof(BUCKET));

    if(data == NULL)
        printf("error: out of space...");

    for(i = 0; i < length; i++)
    {
        data[i].value = array[i];
        data[i].next = NULL;
    }

    for(i = 0; i < length; i++)
    {
        index = get_ditital_at_1(data[i].value, count);
        if(bucket[index].next == NULL)
            bucket[index].next = &data[i];
        else
        {
            tmp = &bucket[index];
            while(tmp->next != NULL && tmp->next->value < data[i].value)
                tmp = tmp->next;
            data[i].next = tmp->next;
            tmp->next = &data[i];
        }
    }

    index = 0;
    for(i = 0; i < 10; i++)
    {
        tmp = bucket[i].next;
        while(tmp != NULL)
        {
            array[index++] = tmp->value;
            tmp = tmp->next;
        }
    }
    free(data);
}

其中，函数get_ditital_at_1()定义如下：

//获取Num中从高位到低位上的第n位的数字
int get_ditital_at_1(int num, int n)
{
    while (--n > 0) 
    {
        num /= 10;
    }
    return (num % 10);
}

对于该链表实现的桶式排序，我们不难看出，只执行了一趟基数排序(即只对最高位进行了排序)，然后利用如下语句：

tmp = &bucket[index];
            while(tmp->next != NULL && tmp->next->value < data[i].value)
                tmp = tmp->next;
            data[i].next = tmp->next;
            tmp->next = &data[i];

对每个桶中的数进行排序。
当然，采用最高位优先的顺序进行排序有一个bug。比如，待排序的十个数中只有一个三位数或者四位数，那么，该排序算法的实现过程是类似于这样的：

这样的排序无异于普通的链表操作，此时的基数排序将没有任何意义。
声明：对于基数排序的这两种方法，均不能实现对负数的排序。

最后

以上就是顺心人生为你收集整理的基数排序的两种实现方法--Radix Sort的全部内容，希望文章能够帮你解决基数排序的两种实现方法--Radix Sort所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。