radixsort.cpp

数据结构c++-书的一些源代码

#include <iostream.h>
#include "datatype.h"

#include "LinQueue.h"
void RadixSort(datatype a[], int n, int m, int d)
//对对象a[0]--a[n-1]进行关键码为m位d进制整型数值的基数排序
//桶采用链式队列结构
{
	int i, j, k, l, power = 1;
	LinQueue<datatype> *tub = new LinQueue<datatype>[d];

	//进行m次排序
	for(i = 0; i < m; i++)
	{
		if(i == 0) power = 1;
		else power = power *d;

		//将对象按关键码第k位的大小放到相应的队列中
		for(j = 0; j < n; j++)
		{
			k = a[j].key /power - (a[j].key /(power * d)) * d;
			tub[k].QInsert(a[j]);
		}

		//顺序回收各队列中的对象
		for(j = 0, k = 0; j < d; j++)
			while(!tub[j].QueueEmpty())
				a[k++] = tub[j].QDelete();
	}
}

void main(void)
{
	datatype test[]={60,55,48,37,10,90,84,36};
	int n = 8, m = 2, d = 10;
	
	RadixSort(test, n, m, d);
	for(int i = 0; i < n; i++)
		cout << test[i].key << "  ";
}