数据结构 多关键字排序

数据结构 多关键字排序

实验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;
}