排序之基数排序

一、数据结构
        约定排序均为升序排序，要排序的记录存储在线性表中，线性表由排序关键字和其它域组成，其定义如下：
        struct element
        {
            int key[d];            // d为关键字的位数
            int next;    
        };
        element rsqlist[n];
      
二、算法思想
        基数排序的思想类似于扑克牌排队的方法。一般地，记录r[i]的关键字为r[i].key，r[i].key是由d位数字组成，即k¹_ik²_i^k^d_i，每一个数字表示关键字的一位，其中k_¹为最高位，k^d是最低位，每一位的值都在0<=kⁱ
三、程序实现
        实现基数排序的函数如下：
        void radixsort(rsqlist r, int p, int d, int n)        // 排序元素r[1]~r[n]      
        {
            int f[rd], e[rd];                                     // 队的头、尾指示器，rd是基数，二进制数rd为2，十进制数rd为10
            for (k=1; k<=n-1; k++)
            {
                r[k].next = k + 1;
            }  
            r[n].next = 0;
            p = 1;                                                 // 原始数据串成静态链表，头指针为p
            for (i=d; i>0; i--)                                   // 从最后一位关键字开始
            {
                for (j=0; j                 {
                    f[j] = 0;                                      // 对指示器初值
                }
                while (0 != p)
                {
                    k = r[p].key[i];                            // 找到对号为k
                    if (0 == f[k])
                    {
                        f[k] = p;
                    }
                    else
                    {
                        r[e[k]].next = p;
                    }
                    e[k] = p;
                    p = r[p].next;                             // 进行分配
                }
                j = 0;
                while (0 == f[j])
                {
                    j++;                                          // 寻找第一个非空队
                }
                p = f[j];
                t = e[j];
                while (j < rd-1)
                {
                    j++;
                    if (0 != f[j])
                    {
                        r[t].next = f[j];
                        t = e[j];
                    }                                               // 进行收集
                    r[t].next = 0;                             // 收尾
                }
            }
        }
        基数排序算法的时间复杂度是O(d*(rd+n))，其中rd是基数，d为关键字的位数，n是元素个数，它是一种稳定的排序方法。