菏泽网站设计培训/成都seo经理

• “分配-收集”方法
  
  基数：每个单位的 数位 或者 字符的值集 的大小（0到9，a到z）
  

• 链式基数排序
  
  
  
  
  “分配” 和 “收集” 的 实际操作 仅为 修改链表中的指针 和 设置队列的头尾指针。

• 算法如下

#define MAX_NUM_OF_KEY 8 //关键字项数的最大值
#define RADIX 10 // 关键字基数，此时是十进制整数的基数
#define MAX_SPACE 10000typedef struct
{KeysType keys[MAX_NUM_OF_KEY]; // 关键字InfoType otheritems; // 其他数据项int next;
}SLCell; // 静态链表的结点类型typedef struct
{SLCell r[MAX_SPACE]; // 静态链表的可利用空间int keynum; //当前关键字的个数int recnum; // 静态链表的当前长度
} SLList; //静态链表类型typedef int ArrType[RADIX];

• 链式基数排序中一趟分配的算法

void Distribute(SLCell &r, int i, ArrType &f, ArrType &e)
{// 静态链表 L 的 r 域中记录已按（keys[0] , ... , keys[i-1]）有序。// 本算法按第 i 个关键字 keys[i] 建立 RADIX 个子表，使同一子表中记录的 keys[i] 相同。// f[0 .. RADIX-1] 和 e[0 .. RADIX-1] 分别指向各子表中第一个和最后一个记录。for(j=0; j<Radix; j++){f[j] = 0;}for(p=r[0].next; p; p=r[p].next){// 将当前记录的第 i 个关键字映射到 [0 .. RADIX-1]j = ord(r[p].keys[i]); // 插入第j 个子表中if(!f[j]){f[j] = p;}else{r[e[j]].next = p;}e[j] = p;}
}

• 链式基数排序中一趟收集算法

void Collect(SLCell &r, int i, ArrType f, ArrType e)
{// 本算法按 keys[i] 自小至大 将 f[0 .. RADIX-1] 所指各子表依次链接成一个链表// e[0 .. RADIX-1] 为各子表的尾指针for(j=0; !f[j]; j=succ(j));//找到第一个非空子表，succ为求后继函数r[0].next = f[j]; //r[0].next 指向第一个非孔子表中第一个结点t = e[j];while(j < RADIX){for(j = succ(j);j<RADIX-1 && !f[j];j = succ(j) ); // 找下一个非空子表if(f[j]) // 链接两个非空子表{r[t].next = f[j];t = e[j];}}r[t].next = 0;
}

• 链式基数排序算法

void RadixSort(SLList &L)
{// L 是采用静态链表表示的顺序表// 对 L 作基数排序，使 L 成为按关键字自小到大的有序静态链表，L.r[0] 为头结点for(i=0; i<L.recnum; i++){L.r[i].next = i+1;}L.r[L.recnum].next = 0;for(i=0; i<keynum; i++) // 按最低位优先依次对各关键字进行收集和分配{Distribute(L.r, i, f, e); // 第 i 趟分配Collect(L.r, i, f, e); // 第 i 趟收集}
}

• 基数排序的 时间复杂度 ：O(d * ( n + rd ))
  分配：把整个记录扫描了一遍，为O( n )
  收集：把所有的队列扫描了一遍，为O( r * d )
  n 为记录的数目
  d 为关键字的个数
  r 为基