排序算法之基数排序

一、例子演示现有如下序列：{3，44，38，5，47，15，36，32，50}，现在要利用基数排序算法对这9个元素进行从小到大的排序，怎么排呢？首先，排序的初始化状态如图1所示图1：初始化状态第二，将这9个元素按个位分配到相应的位置上，如图2所示...

小C哈哈哈

26198人浏览 · 2021-01-27 21:58:34

小C哈哈哈 · 2021-01-27 21:58:34 发布

一、例子演示

现有如下序列：{3，44，38，5，47，15，36，32，50}，现在要利用基数排序算法对这9个元素进行从小到大的排序，怎么排呢？

首先，排序的初始化状态如图1所示



  图1：初始化状态

第二，将这9个元素按个位分配到相应的位置上，如图2所示



图2：按个位分配后的结果

第三，将第二步分配好的结果按顺序取出，因为是按个位排序的，所以取出来的元素一定是按个位有序的，如图3所示



图3：将元素按顺序取出

第四，将元素按十位放入到相应的位置，上一步的数是按个位有序的，现在按十位放入相应的位置，放入之后，对于每个位置而言，都是大数在上面，小数在下面，如图4所示



图4：将元素按十位放入到相应的位置

第五，因为是从小到大排序，将元素从左往右，从下到上依次取出，如图5所示



图5：最终结果

二、算法思想

排序算法是一种非比较算法，其原理是将整数按每个位数分别比较。它利用了桶的思想。代码确实不怎么好写，还是需要仔细分析和钻研代码的。

三、代码实现

#include<bits/stdc++.h>
using namespace std;

int temp[100];
int bucket[10];

int maxBit(int data[],int n)
{
	//行这些代码在求n个元素的最大值 
	int maxData = data[0];
	for(int i=1;i<n;i++)
	{
		if(maxData<data[i])
			maxData=data[i];
	}
	
	//这些代码在求最大值的位数是多少 
	int d=1;    //d用来计数最大值的位数，因为既然是一个数，肯定至少有1位，所以d初始化为1 
	while(maxData>=10)  //将最大值不断/10，计算位数 
	{
		maxData/=10;
		d++;
	}
	return d;
} 
void radixsort(int data[],int n)  //基数排序 
{
	int d = maxBit(data,n);  //求出最大位数
	int i,j,k;
	int radix = 1;
	for(i=1;i<=d;i++)   //进行d次排序
	{
	    for(j=0;j<10;j++)   //每次分配前清空计数器
		{
			bucket[j]=0;
		}
		for(j=0;j<n;j++)    //统计每个桶的元素个数 
		{
			k=(data[j]/radix)%10;
			bucket[k]++;
		}
		
		//关键代码1 
	    for(j = 1; j < 10; j++)
            bucket[j] = bucket[j - 1] + bucket[j]; 
       
       //关键代码2 
		for(j = n-1; j>=0; j--) 
        {
            k = (data[j] / radix) % 10;
            temp[bucket[k] - 1] = data[j];
            bucket[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = temp[j];
            
        radix = radix * 10;  //个位  -》 十位  -》百位 -》…… 
	} 
}

int main()
{
	int a[4]={2,1,34,4};   
	radixsort(a,4);         //a十待排序的数组 ，4是元素个数 
	for(int i=0;i<4;i++)
		cout<<temp[i]<<" ";
	return 0;
}

四、代码思路分析

首先，因为基数排序是一个按位数比较的排序方法，因此在n个元素中，我们需要找出这n个元素的最大值（或者说算出这n个元素中最长位数），找出最大值是为了求n个元素中的最长位数，比如说：{2,1,34,4}，这4个元素中的最长位数是2位（34就是两位），因为是按位排序，所以有x位，就要进行x次排序才能得到正确结果。所以，我们第一步应该写关于求最长位数的代码。我不妨把这个代码封装成一个函数，函数的名字叫做maxBit，这个函数的实现这里提供了两种方式：

第一种方式：求出最大值，将最大值不断/10，求最大值的位数，最大值的位数就是这n个元素的最长位数
int maxBit(int data[],int n)
{
	//21~27行这些代码在求n个元素的最大值 
	int maxData = data[0];
	for(int i=1;i<n;i++)
	{
		if(maxData<data[i])
			maxData=data[i];
	}
	
	//30~36这些代码在求最大值的位数是多少 
	int d=1;    //d用来计数最大值的位数，因为既然是一个数，肯定至少有1位，所以d初始化为1 
	while(maxData>=10)  //将最大值不断/10，计算位数 
	{
		maxData/=10;
		d++;
	}
	return d;
} 
第二种方式：遍历n个元素，对于某一个元素和p比较，如果比p大，就扩大p的值，同时位数+1
int maxBit(int data[],int n)
{
	//行这些代码在求n个元素的最大值 
	int maxData = data[0];
	for(int i=1;i<n;i++)
	{
		if(maxData<data[i])
			maxData=data[i];
	}
	
	//这些代码在求最大值的位数是多少 
	int d=1;    //d用来计数最大值的位数，因为既然是一个数，肯定至少有1位，所以d初始化为1 
	int p=10;   //辅助求最长位数
	for(int i=0;i<n;i++)
	{
		while(data[i]>=p)   //一旦发现n个元素中有大于等于p的，那么位数加1，p*10
		{
			   p*=10;
				d++;
	    }
	}
	return d;
} 
其次，求出最大位数之后我们就可以开始排序了，x位的话根据咱们的例子演示需要排x次序，首先是按个位，然后按十位，然后按百位……以此类推，所以肯定需要一个x次的循环，这里不妨使用for循环，在for循环中我们需要做几件事情，因为我们是利用桶的思想来进行排序，要将元素放入到对应的不同的桶中，对于每一次排序我们都需要清空桶，也就是将0-9这10个桶全部置为0，个位排完置为0，重新计数，十位排完置为0，也重新计数，以此类推……,代码如下
for(j=0;j<10;j++)   
{
		bucket[j]=0;   //bucket代表桶，这是一个数组  定义为：int bucket[10];
} 
置为0之后，我们需要统计一下，当前这一轮排序，每一个桶中相应放进了多少个元素，代码如下：
for(j=0;j<n;j++)    //统计每个桶的元素个数 
{
    k=(data[j]/radix)%10;   //radix初始值为1，一开始是按个位排序，所以初始值为1
                            //data是待排序的数组，%10代表取得最末位的元素
    bucket[k]++;            //对应的编号的桶元素个数+1
}
之后，这一步很多人无法理解，需要认真看，这一步要做的事情就是（用语言不好描述，不如来看例子），我们还是以第一步举的{2,1,34,4}这4个元素为例，第一次是按个位排序的，按照这个桶分配的话就是下图

接下来就很关键了，我们要如何取出这些已经按个位排好序的数字呢？我们现在是4个元素，我们如何才能将这4个元素有序取出呢？，我现在不妨开辟一个空间为：int temp[4];，到底怎么取呢？你还记得我们在上一步统计了每一个桶里面放的元素个数吗？在这里具体表示就是如下图：

这个时候我们就要思考，如何建立一种映射关系让temp里面是元素是按个位有序排列的呢？，我们需要更新bucket数组的值，我们看下图：

我们还是用{2,1,34,4}这4个元素来说明这个问题，我们开辟了一个空间temp[4]，第一次是用来存个位排序后的结果的，要想按正确的顺序存入temp，必须要更新bucket的值，bucket更新后的值如上图所示。现在2，1，34，4，这4个元素中的最后一个元素是4，说明个位是4，我们需要找到bucket[4]这个元素的值为4，我们已经统计过了以1，2，3为个位的元素有3个，而4对应的bucket[4]的数值为4，现在要将4存入到temp中，需要这样存储：temp[bucket[4]-1]=data[3]存储（这里data[4]={2,1,34,4}），bucket中的4在第一轮中代表的是个位，存完之后，需要将bucket[4]的值-1，那么bucket[4]的值此时为3。接下来就是倒2个元素34，它的个位也是4，于是，temp[bucket[4]-1=data[2]，因为bucket[4]里面的值已经从4变为3了，所以temp[3-1]=data[2]，所以temp[2]=34;接下来就是倒3个元素1了，他的个位是1，于是，temp[bucket[1]-1]=data[1]，temp[1-1]=data[1]，temp[0]=1；接下来就是倒4个元素，也就是第1个元素2了，2的个位是2，于是,temp[bucket[2]-1]=data[0]，temp[1]=2;所以最终，temp中元素为{1，2，34，4}，这个时候可以发现，temp中的元素已经按个位有序了。之后我们更新data数组的值，将temp中的元素有序复制给data数组。

第三，我知道有人肯定想问，为什么2，1，34，4这4个元素我们在代码中要从后往前判断，而不从前往后呢？我们不妨往下看，上一轮按个位比完之后，接下来就是要按十位比较了。拿着{1，2，34，4}，按十位比较，我们看下图：

因为我们的最长位数为2，现在排序趟数进入了第二趟，和第一趟一样，先将bucket的数值全部清0，然后统计不同的桶中各自有多少个元素，之后为了能够方便放进temp中，更新桶的值，如下图：

我们拿着{1，2，34，4}这四个元素开始放值到temp中，一定要记得，此时我们是按十位存放，而不是个位了，我们按正常的顺序从后往前放,放的位置为，bucket[data[3]/radix%10]-1，此时radix已经由第一步的1变成10了，因为现在是按十位比较，于是，temp[bucket[data[3]/radix]-1]=temp[2]=4,然后bucket[data[3]/radix]的值-1，变为2了，然后读入倒二个元素34，34的十位为3，于是就是temp[bucket[3]-1]=temp[4-1]=temp[3]=34,接下来就是读入元素2了，2的十位为0，于是就是temp[bucket[0]-1]=temp[2-1]=temp[1]=2，此时bucket[0]的值需要-1，就变为1了，然后接下来读入的元素就是1了，1的十位为0，于是就是temp[bucket[0]-1]=temp[0]=1，所以最终temp的结果为{1,2,4,34};再将temp结果重新赋值给data数组，此时控制排序的循环结束。data数组已经按照从小到大排好序了。

这个时候我们思考，如果我们读入数据的时候不是倒序读入，而是正序读入，会发生什么情况呢？首先读入1，因为十位是0，所以temp[bucket[0]-1]=1；此时temp[2]=1;就出现问题了，1不可能放在temp[2]这个位置，因为这已经是最后一轮排序了。

倒序读取是为了保证同一个桶上面的数据按某一位在temp中升序，最后才能保证得到的序列是正确的

五、总结

基数排序看着思路挺简单的，但是代码实现起来并没有那么简单，代码中有好几个点需要注意，比如：更新bucket的值，为什么需要更新bucket的值？再比如：为什么将值放入temp的时候元素需要倒序读入？这两个问题都是我们需要去思考的，如果这两个题搞明白，代码自然而然就会编写了。😄这一期我们就讲到这里啦！我们下期再见，若有问题🤭，欢迎加微信：Q1313135进行讨论沟通👈