桶排序之后 --- > 基数排序-蒲公英云

桶排序之后 --- > 基数排序

迷南。 2022-03-20 01:42 333阅读 0赞

和桶排序一样，也不是基于比较的。

基数排序一般用于整数的处理，它的基本原理是：一直想把它说的更白话一点，可是，哎。。。

我们可以想象一下，如果现在只有几个各位数 2 6 3 7 ，

那么装入数组后是：

![Image 1][]

修改相应的位置后：

那么再由后往前扫描，7 -> 3 -> 6 -> 2

对应到位置后为：2 3 6 7 已经排好序了。。。

那么对于两位呢？我们想象一下，例如一趟后的顺序是：23 34 26 27 17 我们可以看看个位数，显然是排序好的一次！那么再有10位数处理，10位数大的必然放到后面，由于个位数已经排好序，那么对于同样十位数的数据在第二次排序的时候，必有前面的数十位数==后面数的十位数，前面的个位数 < 后面个位数( 因为算法稳定性 )。所以就这样结束了。。。。

不好意思，语言表达不好啊，哎，给一个动画链接：http://www.cs.usfca.edu/~galles/visualization/radix_sort.html

CODE：( 在九度OJ上已经通过，不过最后一个超级大数据的时候TLE了,5555…，但是算法实现应该正确 )

#include <stdio.h>
#include <stdlib.h>
void radix_count(int* idx, int m, int* p_data, int len)
{
    int* p_count  = (int*)malloc(sizeof(int)* m);    
    int* p_sort  = (int*)malloc(sizeof(int) * len);   
    int i = 0;
     for (i = 0; i < m; ++i)
    {
        p_count[i] = 0;
    }
    for (i = 0; i < len; ++i)    
    {
        ++p_count[idx[i]];
    }
    for (i = 1; i < 10; ++i)    
    {
        p_count[i] += p_count[i - 1];
    }   
    for (i = len - 1; i >= 0; --i)
    {
        p_count[idx[i]]--;        
        p_sort[p_count[idx[i]]] = p_data[i];
    }
    for (i = 0; i < len; ++i)
    {
        p_data[i] = p_sort[i];
    }
    free(p_sort);
    free(p_count);
}
void radix_sort(int* p_data, int len)
{
    int* radix_data = (int*)malloc(sizeof(int) * len);
    int start = 1;
    int flag = 0;
    int i;
    while (!flag)
    {
        flag = 1;
        start *= 10;
    i = 0; 
    for (i = 0; i < len; ++i)
        {
            radix_data[i] = p_data[i] % start;
            radix_data[i] /= start / 10;
            if (radix_data[i] > 0)
            {
                flag = 0;
            }
        }
        if (flag)
        {
            break;
        }
        radix_count(radix_data, 10, p_data, len);
    }
    free(radix_data);
}
int main()
{
    int a[1000];
    int i, n;
    while( scanf("%d", &n) != EOF )
    {
        for(i = 0; i < n; i++ )
        {
            scanf("%d", &a[i]);
        }
        radix_sort(a, n); 
        for (i = 0; i < n; ++i)
        {
            printf("%d ", a[i]);
        }
        printf("\n");
    }
    return 0;
}