排序算法之计数&基数排序

曾经终败给现在 2022-07-14 08:00 160阅读 0赞

**计数排序>**

给定一组待排序的数据，找到这组数据中的最大值，然后开辟一个最大值加1的数组，用memset初始化为全0，然后再次遍历原数组，使得这个新开辟的数组中存储的是该数字出现的次数，此时只需要将新数组的内容写入原数组即可.

![Center][]

我们发现计数排序其实利用的是哈希的思想来统计次数,是一种非比较的排序,它的时间复杂度为O(N+范围),因为计数排序是一种以空间换取时间的排序算法.

**计数排序的优化>**

如果给定这样一组数据"1001,1002,1003",那仫按照之前的思路我们就需要开辟1004块空间，很明显存在极大的空间浪费.要优化它只能从减小开辟空间的个数入手了.

其实我们可以找出一组数据中的最大值和最小值，此时开辟的辅助数组只需要开辟max-min+1块即可，在统计次数要重新映射进辅助数组.

void CountSort(int *a,int size)
    {
    	assert(a);
    	int max=a[0];
    	int min=a[0];
    	//找到最大最小值
    	for (int i=0;i<size;++i)
    	{
    		if(a[i] > max)
    			max=a[i];
    		if(a[i] < min)
    			min=a[i];
    	}
    	int range=max-min+1;
    	int *tmp=new int[range];
    	memset(tmp,0,sizeof(int)*range);
    	//统计数字出现的次数
    	for (int i=0;i<size;++i)
    	{
    		tmp[a[i]-min]++;
    	}
    	//还原初始数组
    	int index=0;
    	for (int i=0;i<range;++i)
    	{
    		while (tmp[i]--)
    		{
    			a[index++]=i+min;
    		}
    	}
    	delete[] tmp;
    }

**基数排序>**

基数排序是另一种非比较的排序，类似哈希桶.它的主要思想是:从低位开始将一组序列按照这一位值的大小放至相应的编号0~9中。等到低位排完之后再按照类似的想法继续排次低位，直至排到最高位为止，此时这个序列就是有序的序列.

int GetMaxDigit(int *a,int size)
    {
    	//标识数量级
    	int base=10;
    	//统计最大数据的位数
    	int digit=1;
    	for (int i=0;i<size;++i)
    	{
    		while (a[i] >= base)
    		{
    			++digit;
    			base *= 10;
    		}
    	}
    	return digit;
    }
    void LSDSort(int *a,int size)
    {
    	assert(a);
    	int base=1;
    	int digit=GetMaxDigit(a,size);
    	int *count=new int[10];
    	int *start=new int[10];
    	int *tmp=new int[size];
    	while(digit--)
    	{
    		//统计数字出现的次数
    		memset(count,0,sizeof(int)*size);
    		for (int i=0;i<size;++i)
    		{
    			count[(a[i]/base)%10]++;
    		}
    		//求每组数据的起始位置
    		start[0]=0;
    		for (int i=1;i<10;++i)
    		{
    			start[i]=start[i-1]+count[i-1];
    		}
    		//将数据写入tmp中
    		for (int i=0;i<size;++i)
    		{
    			int num=(a[i]/base)%10;
    			tmp[start[num]]=a[i];
    			start[num]++;
    		}
    		//将tmp中的内容写入a中
    		for (int i=0;i<size;++i)
    		{
    			a[i]=tmp[i];
    		}
    		base *= 10;
    	}
    	delete[] tmp;
    }

在上述找最大位的方法先设置数量级base=10,digit统计位数=1，遍历数组，如果存在大于等于数量级的数就更新数量级统计位数加1.当然这个方法不太好理解，另一种求位数的方法是:先遍历一遍数组找到数组中的最大值，求出最大值的位数.

基数排序的时间复杂度为**O(N\*digit),**digit是这组待排序数据中的最大位，它的空间复杂度为O(N),基数排序是一种稳定的排序算法.

在这里就分享结束啦~~~

[Center]: /images/20220714/74320b8a57334f2e89bd1a154714f10d.png