穿孔卡片排序

#include <vld.h>
#include <queue>
#include <iostream>
#include <iomanip>
#include "_CRandom.h"

using namespace std ;
/*
* 描 述：在早期计算中，常用排序机来对一组穿孔卡片排序。即排序机上有十个箱子，把数放入，排序后拿出
* 假定卡片上的数为两位整数，范围为00~99。
* 排序机有十个箱子，编号0~9。排序机处理卡片两遍，第1遍处理个位数，第2遍处理十位数。
* 比如编号1里面放十位数为1的，编号2里放十位数为2的。然后取卡片通过排序机时掉入相应的箱子里。
* 这种方法称为基数排序。 
* 步骤 ：按个位分到箱子，拿出，按十位分到箱子，拿出，输出结果
* 摘 要：穿孔卡片派序

* 作 者：

* 完成日期：
*/
enum DigitKind{ones, tens};
void Collect(queue<int> digitQueue[], int L[]);
void Distribute(int L[], queue<int> digitQueue[], int n, DigitKind kind);

int main()
{
	int i=0;
	int L[50];
	_CRandom _rand;
	queue<int> digitQueue[10];
	
	srand( (unsigned)time( NULL ) );
		
	for(i=0; i<50; i++)
	{
		L[i]=_rand.getINT(100);
	}

	//打印随机数
	cout<<"排序前: "<<endl;
	for(i=0; i<50; i++)
	{
		cout<<setw(4)<<L[i];
		if( (i+1)%10==0)
		{
			cout<<endl;
		}
	}
	Distribute(L, digitQueue, 50, ones);
	Collect(digitQueue, L);
	Distribute(L, digitQueue, 50, tens);
	Collect(digitQueue, L);

	cout<<endl<<endl<<endl;
	cout<<"排序后: "<<endl;
	for(i=0; i<50; i++)
	{
		cout<<setw(4)<<L[i];
		if( (i+1)%10==0)
		{
			cout<<endl;
		}
	}

	return 0;
}


void Distribute(int L[], queue<int> digitQueue[], int n, DigitKind kind)
{
	int i;
	for(i = 0; i<n; i++)
	{
		//个位
		if(kind == ones)
		{
			digitQueue[L[i] % 10].push(L[i]);
		}
		//十位
		else
		{
			digitQueue[L[i]/10].push(L[i]);
		}
	}
}

void Collect(queue<int> digitQueue[], int L[])
{
	int i=0, digit=0;
	for(digit=0; digit<10; digit++)
	{
		while( !digitQueue[digit].empty())
		{
			L[i++] = digitQueue[digit].front();
			digitQueue[digit].pop();
		}
	}
}

/*
排序前:
  53  24  27  25  18  21  52  39  75  42
   4  57  54  57  70   9  73  36  91  45
  23  89  47  81  80  38  14  95  95  40
  51  49  19  35   5  26  57  13  33  68
  13  18  71   2  71  85  36  78  14  28



排序后:
   2   4   5   9  13  13  14  14  18  18
  19  21  23  24  25  26  27  28  33  35
  36  36  38  39  40  42  45  47  49  51
  52  53  54  57  57  57  68  70  71  71
  73  75  78  80  81  85  89  91  95  95
Press any key to continue

*/

图法：
比如数
31，46，85，15，92，35，91，22

队列有10个，0~9，按个位放入数据
0   1   2   3  4  5  6  7  8  9
    31  92        85 46
    91  22        15
                  35

按队列读出得
31 91 92 22 85 15 35 46

按十位放入
0   1   2   3  4  5  6  7  8  9
    15  22  31 46          85 91
            35                92

读出
15 22 31 35 46 85 91 92

算法复杂度
复杂度为O(2N)。扩展到对m位的n个数排序，复杂度为O(mn).但是在空间上消耗很大，至少要10个队列。队列中需要有front,rear指针，计数器，数组，对内存管理等等。如果数据量和位数增大，mn所需要的性能更大，
还有个问题，比如遇上负数可能还要另外开个队列来进行维护等等。。。