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

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

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

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

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

那么装入数组后是 ：

![Image 1][]

![1363424135_5355.jpg][]

修改相应的位置后：

![1363424283_2692.jpg][]

那么再由后往前扫描，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][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;
    }

[Image 1]: 
[1363424135_5355.jpg]: https://img-my.csdn.net/uploads/201303/16/1363424135_5355.jpg
[1363424283_2692.jpg]: https://img-my.csdn.net/uploads/201303/16/1363424283_2692.jpg
[http_www.cs.usfca.edu_galles_visualization_radix_sort.html]: http://www.cs.usfca.edu/~galles/visualization/radix_sort.html