八大排序——基数排序

  基数排序

  基数排序是在八大排序中相对来说叫简单的一种排序方法，基数排序也可以称作是“桶排序”，顾名思义，就是将数据放入一个一个地桶里面。在这里，我以一组数据“25,78,58,99,105,254,763,365,47,33,10,87”为例，来为大家先演示一遍基数排序的过程，在总结一下编程的思路，最后再将代码展示出来，这里，请大家注意我编程的思路，回去可以自己根据思路，将代码实现一下。编程不是要将代码给背过，而是要记住这种思路，根据思路将代码写出来。

  一.基数排序的过程演示

   先查看各个待排序数的个位数，按个位数将数字装入对应的桶中，比如说，第一个数字25的个位数是5，那么将它放到下标是5的桶中，以此类推。

   如图所示，已经将所有数据都放入到桶中，桶结构我们可以使用栈或队列来写，但栈是先进后出，可能会导致我们的顺序变成和原来是相反的情况，导致乱序，所以为了保证数据不会乱序，我们应该用队列来写，至于原因在这里，我不赘述，大家可以自己用我的数据，按栈来推一下，可以发现在第三次中数据混乱，大数排在小数前面。

  桶中数据出队列后，数据为“10,763,33,254,25,105,365,47,87,78,58,99”。

  这次查看的是十位数，假如十位数是2，则将数字放入到下标是2的桶中，以此类推。

   桶中数据出队列后，数据为“105，10，25，33，47，254，58，365，763，78，87，99”。（少写了一个78）

 

  这次查看的是百位数，如果是二位数，几百位数字为0，则将数据放在下标为0的桶中，其余百位数字为多少就放入到下表同样为该数字的桶中，以此类推。  

  桶中数据出队列后，数据为“10，25，33，47，58，78，87，99，105，254，365，763”。此时，数据从小到大，排序完成。

二.编程思路

    基数排序的过程即为如此，那么下来我们来理一下编程的思路：

   1.这里桶这个容器，我们用队列来实现，那么我们需要十个队列来存储0-9这十个数字，并且这十个队列有多大，最坏的情况就是所有的数字都在同一个队列里面，那么我们应该给每一个队列申请数据的长度来存储数据，在设一个head和tail初始化来存储数据。

   2.这里最大的数据是三位数，而我们一共也需要排序三次，才可以使数据有序，显而易见，基数排序的次数其实就是最大数据的位数。那么第一步我们需要找出最大数据，再进一步找出它的位数，知道排序的次数。

   3.知道了循环次数，那么我们就清楚了循环退出的条件，这也是我们的大条件。在下一步的小条件是，我们是按照位数来作为循环条件，比如我们第一次循环是个位数上的数字，那么我们需要清楚数据在相应的个位数是多少来将数据放入到相应的桶中，那么下一步我们需要知道数据就是按位数来分割，那么该位数上的数据到底是多少。最后按数据的个数循环，将数据保存到队列中，再将队列按顺序出队，再出到我们保存数据的数组中。要注意的是，我们将数据出队后，应将head和tail都置为空。

三.代码展示

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<malloc.h>
#include<unistd.h>

int GetMaxwidth(int *s, int len)    //获得数组中的最大元素，并获得其长度
{
	int i = 1;
	int max = s[0];
	int count = 0;
	for (; i<len; i++)
	{
		if (max<s[i])
		{
			max = s[i];
		}
	}
	while (max>0)
	{
		max /= 10;
		count++;
	}
	return count;
}

int GetRadix(int a, int m)    //获得数据在当前位数下的数字
{
	int n;
	int i;
	for (i = 0; i<m; i++)
	{
		n = a % 10;
		a /= 10;
	}
	return n;
}

void CardinalSort(int *s, int len)
//基数排序
{
	int width = GetMaxwidth(s, len);
	int i = 0;
	int j = 0;
	int radix;
	Que que[10];
	for (i = 0; i<10; i++)                   //初始化队列     
	{
		que[i].data = (int *)malloc(sizeof(int)* len);
		que[i].head = que[i].tail = 0;
	}

	for (i = 1; i <= width; i++)          //大循环条件
	{
		for (j = 0; j<len; j++)
		{
			radix = GetRadix(s[j], i);    //获得当前位数下数据
			que[radix].data[(que[radix].tail)++] = s[j];      
            //将数据存入到对应的下标的队列中
		}

		int count = 0;
		for (j = 0; j<10; ++j)            //按照队列个数来遍历数据
		{
			while (que[j].head != que[j].tail)   //如果队列不为空的情况下 
			{
				s[count++] = que[j].data[(que[j].head)++];    
                //将队列中的数据出队列放入到原数组中
			}
			que[j].head = que[j].tail = 0;
            //置队列的头和尾为空
		}
	}
}

void Print(int *s, int len)         //打印数据
{
	int i;
	for (i = 0; i<len; i++)
	{
		printf("%d ", s[i]);
	}
	printf("\n");
}

int main()
{
	int s[] = { 25, 78, 58, 99, 105, 254, 763, 365, 47, 33, 10, 87 };
	int len = sizeof(s) / sizeof(s[0]);

	CardinalSort(s, len);
	Print(s, len);
	return 0;
}

结果如下：

结果得证。