排序算法(六)非比较排序----计数排序和基数排序

发布于:2021-11-27 08:16:47

前边的几篇文章介绍的几种排序算法都是比较排序,接下来的文章将会介绍两种非比较排序。


计数排序:

计数排序通过哈希的方法将一组数据映射到一个数组里,最后将数组中的数依次读取,并写进原来的数组,读出的数据就是有序的。




综合以上图片的分析,我们知道,保存数据信息的数组(即就是计数的count数组)的大小应该是最大数与最小数之差再加1.


下边请看代码实现:

//计数排序
void CountSort(int a[],int n)
{
assert(a);
//找到数组中的最大元素和最小元素
int min = a[0];
int max = a[0];
for(int i = 1; i < n; ++i)
{
if(a[i] > max)
max = a[i];
if(a[i] < min)
min = a[i];
}
int range = max - min + 1;

//开辟range大的count数组
int* count = new int[range];
memset(count,0,sizeof(int) * range);

//写count数组
for(int i = 0; i < n; ++i)
{
count[a[i] - min]++;
}

//读count数组,并写a数组
int index = 0;
for(int i = 0; i < range; ++i)
{
while(count[i]--)
{
a[index++] = i + min;
}
}
}


计数排序,是比较快的排序,但是它却有一定的缺陷。如果数据过于分散,计数排序的空间复杂度是比较高的(count数组比较大)。如果数据很集中,计数排序就是比较快的。


基数排序 :


对一组数据进行排序,先按照其个位进行排序,然后按照十位进行排序,依次类推。







下边给出代码实现:



//求最大数的位数
int GetMaxDigit(int a[],int n)
{
int base = 10;
int digit = 1;
int i = 0;
for(int i = 0; i< n ; ++i)
{
while(a[i] >= base)
{
digit ++;
base *= 10;
}
}
return digit;
}
//基数排序
void LSDSort(int a[],int n)
{
assert(a);
int digit = GetMaxDigit(a,n);
int base = 1;
//定义一个count数组
int count[10] = {0};
int start[10] = {0};
int* tmp = new int[n];
while(digit--)
{
memset(count,0,sizeof(int) * 10);
start[0] = 0;
//写count数组
for(int i = 0; i < n; ++i)
{
count[(a[i]/base) % 10]++;
}
//写start数组
for(int i = 1; i < 10; ++i)
{
start[i] = start[i - 1] + count[i - 1];
}
//读a数组,写tmp数
int num = 0;
for(int i = 0; i < n; ++i)
{
num = (a[i]/base) % 10;
tmp[start[num]] = a[i];
start[num]++;
}
//将tmp数组写回a数组
for(int i = 0; i < n; ++i)
{
a[i] = tmp[i];
}
base *= 10;
}
delete[] tmp;
}






根据上图的分析,需要按照最大的数的每个位都进行排序之后,整个数组才会有序。


基数排序的缺陷:适用于数据比较集中的情况,不能对负数进行排序。


如果对以上的 ?求最大数的位数 ?的那种办法不能理解,你可以采用一种理解起来比较简单但是稍微麻烦的办法:找出最大的数,然后求出他的位数。




相关推荐

最新更新

猜你喜欢