队列排序（基数排序）

时间：2010-10-27 来源：woxf

　　用队列来表示这些箱子就可以实现这个算法。每一位数字一共需要九个队列。用取余运算和整除运算就可以确定个位上的数字及十位上的数字。剩下的事情就是把数添加到适当的队列内，根据个位上的数字再把数从队列中取出进行重新排序，随后根据十位上的数字重复上述操作。

代码如下：

代码

 1 using System.Collections;
 2 
 3  namespace ConsoleApplication8
 4 {
 5     class Program
 6     {
 7         static void Main(string[] args)
 8         {
 9             Queue[] numQueue = new Queue[10];//定义是个队列——是个箱子
10             int[] nums = new int[] { 91, 46, 85, 15, 92, 35, 31, 22 };//等待排序的数组
11             for (int i = 0; i < 10; i++)
12             {
13                 numQueue[i] = new Queue();//每一个箱子也是一个队列
14                 
15             }
16             RSort(numQueue, nums, DigitType.ones);//基于个位数上的数字进行装箱，即把个位数相同的数放入同一个箱子
17             BuildArray(numQueue, nums);//排序，把箱子里的数据重新取出来放在数组中
18             Console.WriteLine();
19             Console.WriteLine("First pass results: ");
20             DisplayArray(nums);//显示每一次排序后的数据
21 
22             RSort(numQueue, nums, DigitType.tens);//基于十位数上的数字进行装箱，即把十位数相同的数放入同一个箱子
23             BuildArray(numQueue, nums);//排序，把箱子里的数据重新取出来放在数组中
24             Console.WriteLine();
25             Console.WriteLine("Second pass results: ");
26             DisplayArray(nums);
27             Console.WriteLine();
28             
29             Console.ReadKey();
30         }
31         enum DigitType { ones = 1, tens = 10 }//定义枚举，是排各位数还是排十位数
32         /// <summary>
33         /// 显示数据
34         /// </summary>
35         /// <param name="n——数组"></param>
36         static void DisplayArray(int[] n)
37         {
38             for (int x = 0; x <= n.GetUpperBound(0); x++)
39                 Console.Write(n[x] + " ");
40         }
41         /// <summary>
42         /// 装箱，把位数相同的数放入同一个箱子
43         /// </summary>
44         /// <param name="que 队列——箱子"></param>
45         /// <param name="n——数组"></param>
46         /// <param name="digit——位数，各位或十位"></param>
47         static void RSort(Queue[] que, int[] n, DigitType digit)
48         {
49             int snum;
50             for (int x = 0; x <= n.GetUpperBound(0); x++)
51             {
52                 if (digit == DigitType.ones)
53                     snum = n[x] % 10;//取模运算，返回余数。箱子标号，即个位数相同的放入对应的箱子
54                 else
55                     snum = n[x] / 10;//整除，返回整数商。箱子标号，即十位数相同的放入对应的箱子
56                 que[snum].Enqueue(n[x]);//装箱
57             }
58         }
59         /// <summary>
60         /// 从装好箱的数据重新取出来
61         /// </summary>
62         /// <param name="que——装好箱的队列"></param>
63         /// <param name="n——数组，存放上述队列上的数据"></param>
64         static void BuildArray(Queue[] que, int[] n)
65         {
66             int y = 0;
67             for (int x = 0; x <= 9; x++)
68             {
69                 while (que[x].Count > 0)//判断箱子里是否有数据
70                 {
71                     n[y] = Int32.Parse(que[x].Dequeue().ToString());//若有数据，从箱子里取出
72                     y++;
73                 }
74             }
75         }
76 
77     }
78 }
79