各种排序算法综合(5)

都是算法程序

ext;
} SLCell;

typedef struct
{
SLCell r[MAX_SPACE];
int recnum;//静态链表的当前长度
} SList;

typedef struct
{
int key;
int front;
int rear;
} KeyQueue;//关键字的每个值有一个队列

void RadixSort(char a[][NUM_OF_KEY], int len);
//分配算法，根据是第i次，将SL，分配到KQ队列中
void Distribute(SList *SL, KeyQueue *KQ, int time);
//收集算法，根据队列KQ重新整理静态链表SL,最后清理KQ为0
void Collect(SList *SL, KeyQueue *KQ);
int main(int argc, char *argv[])
{
char a[NUM][NUM_OF_KEY] = { "278", "109", "063", "930", "589",
"184", "505", "269", "008", "083"};
int i = 0, j = 0;

int len = NUM;
RadixSort(a, len);
for(; i < NUM; i++)
{ for(j = 0; j < NUM_OF_KEY; j++)
printf("%c", a[i][j]);
printf("\n");
}
return 0;
}

void RadixSort(char a[][NUM_OF_KEY], int len)
{
int i = 0, j, tmp;
SList SL;
KeyQueue KQ[RADIX] = {0};
SLCell tmpCell;

memset(&SL, 0, sizeof(SList));
SL.recnum = len+1;
for(; i < len; i++)
{
memcpy(SL.r[i+1].keys,&a[i][0], NUM_OF_KEY);
SL.r[i].next = i+1;//链表的头指针指向第一个元素
}
SL.r[i].next = 0;

for(i = 0; i < RADIX; i++)
KQ[i].key = i;

//几位数就要进行几次分配和收集.从最低关键字开始
for(i = NUM_OF_KEY - 1; i >= 0; i--)
{
Distribute(&SL, KQ, i);
Collect(&SL, KQ);
}

//根据SL.r[i].next调整SL成为顺序表
for(tmp = SL.r[0].next, i = 1; i < SL.recnum; i++)
{
j = tmp;
while(j < i) j = SL.r[j].next;
if(j != i)//位置需要调整
{
memcpy(&tmpCell, &SL.r[i], sizeof(SLCell));
memcpy(&SL.r[i], &SL.r[j], sizeof(SLCell));
tmp = SL.r[i].next;
SL.r[i].next = j;
memcpy(&SL.r[j], &tmpCell, sizeof(SLCell));
}
else
tmp = SL.r[i].next;
}

for(i = 0; i < len; i++)
memcpy(&a[i][0], SL.r[i+1].keys, sizeof(SL.r[i+1].keys));
}

//分配算法，根据是第time次(即SL.r.keys[time])，将SL，分配到KQ队列中
void Distribute(SList *SL, KeyQueue *KQ, int time)
{
int i = 0, key;
do
{
i = SL->r[i].next;
key = SL->r[i].keys[time] - '0';
if(!KQ[key].front)
KQ[key].front = i;
else
SL->r[KQ[key].rear].next = i;
KQ[key].rear = i;
}
while(SL->r[i].next);
}

//收集算法，根据队列KQ重新整理静态链表SL,最后清理KQ为0
void Collect(SList *SL, KeyQueue *KQ)
{
int i = 0, j;


//置静态链表SL.r[0].next
for(i = 0; i <= RADIX; i++)
{
if(KQ[i].front)
{
SL->r[0].next = KQ[i].front;
break;
}
}

//将