实验7 多关键字排序
一、实验目的
了解多关键字的使用范围；编写程序实现多关键字的排序。
二、实验原理
依次根据某位进行排序，排好序后更新a[i]，最后得到的就是根据每位排好序的a[i]
LSDSort()函数：cnt数组用来存放某位的个数，tmp数组存放a[i]数据，根据cnt[ ] 中的数据得到tmp中存放哪一个a[i]
三、参考程序
#include <stdio.h>
#include <stdlib.h>
#define RADIX 101 //基数，分数有 101 种可能
#define K 3 //关键字，有 3 个关键字
struct tagMark
{
int key[K]; //有 K 个关键字
}a[8] = {{1,2,3}, {0,2,3}, {5,4,6}, {6,2,6}, {4,4,1}, {0,1,4},
{60,30,6}, {60,20,6}};
/*a：待排序的数组地址
size：元素数量
radix：基数
k：关键字数量
*/
void LSDSort(struct tagMark *a, int size, int radix, int k)
{
int *cnt = (int *)malloc(sizeof(int) * radix), i;
struct tagMark *tmp = (struct tagMark *)malloc(sizeof(struct tagMark) * size); //待排序的记录的数量
while (k--)
{
//初始化cnt[i]
for (i = radix-1; i >= 0; --i)
cnt[i] = 0;
//计数
for (i = size; i > 0; )
++cnt[a[--i].key[k]];
//累加cnt
for (i = 0; i < radix; ++i)
cnt[i + 1] += cnt[i];
//按顺序把a[i]放入tmp中
for (i = size; i > 0; )
{
--i;
tmp[--cnt[a[i].key[k]]] = a[i];
}
//把a[i]按照某一位排好的序，重新排序
for (i = size; i > 0; )
{
--i;
a[i] = tmp[i];
}
}
free(cnt);
free(tmp);
}
int main()
{
int i, j;
LSDSort(a, 8, RADIX, K); //对 8 个记录进行排序
//输出
for (i = 0; i < 8; ++i, putchar('\n'))
for (j = 0; j < K; ++j)
printf("%d ", a[i].key[j]);
return 0;
}