计数排序
计数排序是建立在这样的前提条件下的:假设n个输入元素的每一个都是0到k区间内的一个整数,其中k为某个整数。因此我们后面所写的程序也只是针对0到k之间的元素进行排序,
换句话说,排序元素中不能有负数。
基本思想:
对一个输入元素x,先确定所有输入元素中小于x的元素个数,那么排序后x所在的位置也就明确了。比如,所有的输入元素中有10个元素小于x,那么排好序后x的位置序号就应该是11。
当然,如果有相同元素,自然要放到相邻的位置上。
/*
第一种形式实现计数排序
计数排序后的顺序为从小到大
arr[0...len-1]为待排数组,每个元素均是0-k中的一个值
brr[0...len-1]为排序后的输出数组
crr[0...k]保存0...k中每个值在数组arr中出现的次数
*/
void count_sort(int *arr,int *brr,int *crr,int len,int k)
{
int i,j=0;
for(i=0;i<=k;i++)
crr[i]=0;
//统计数组arr中每个元素重复出现的个数
for(i=0;i<len;i++)
crr[arr[i]]++;
//求数组arr中小于等于i的元素个数
for(i=1;i<=k;i++)
crr[i]+=crr[i-1];
//把arr的元素放到brr 对应的位置
for(i=len-1;i>=0;i--)
{
brr[crr[arr[i]]-1]=arr[i];
crr[arr[i]]--;
}
}
/*
第二种形式实现计数排序
计数排序后的顺序为从小到大
arr[0...len-1]为待排数组,每个元素均是0-k中的一个值
crr[0...k]保存0...k中每个值在数组arr中出现的次数
*/
void count_sort(int *arr,int *crr,int len,int k)
{
int i,j=0;
for(i=0;i<=k;i++)
crr[i]=0;
for(i=0;i<len;i++)
crr[arr[i]]++;
for(i=0;i<=k;i++)
while((crr[i]--)>0)
{
arr[j++]=i;
}
}
1、不是基于比较的排序,因此可以达到线性排序时间;
2、采取空间换时间的思想,需要brr和crr等辅助空间,但是时间复杂度仅为O(n+k);
3、稳定性好,这也是计数排序最重要的一个特性。
基数排序;
基数排序采取的是多关键字比较的策略,且每个关键字对排序的影响不同,根据关键字影响的主次,有两种排序方法:
1、先根据影响最大的关键字来排序,而后在该关键字相同的情况下,再根据影响次之的关键字来排序,依此类推,直到最后按照影响最小的关键字排序后,序列有序。我们称这个为先高位后低位。
2、先根据影响最小的关键字来排序,而后再对全部的元素根据影响次小的关键字来排序,依此类推,直到最后按照影响最大的关键字排序后,序列有序。我们称这个为先低位后高位。
/*
在第一种计数排序的实现形式上做了些修改
计数排序后的顺序为从小到大
arr[0...len-1]为待排数组,我们这里采用三位数
brr[0...len-1]为排序后的有序数组
w[0...len-1]用来保存取出的每一位上的数,其每个元素均是0-k中的一个值
crr[0...k]保存0...k中每个值出现的次数
*/
void count_sort(int *arr,int *brr,int *w,int *crr,int len,int k)
{
int i;
for(i=0;i<=k;i++)
crr[i]=0;
//统计数组w中每个元素重复出现的个数
for(i=0;i<len;i++)
crr[w[i]]++;
//求数组w中小于等于i的元素个数
for(i=1;i<=k;i++)
crr[i]+=crr[i-1];
//把arr中的元素放在brr 中对应的位置上
for(i=len-1;i>=0;i--)
{
brr[crr[w[i]]-1]=arr[i];
//如果有相同的元素则放到下一位置
crr[w[i]]--;
}
//再将brr的元素复制给arr
for(i=0;i<len;i++)
arr[i]=brr[i];
}
/*基数排序*/
void basic_sort(int *arr,int *brr,int *w,int *crr,int len,int k,int d)
{
int i,j,val=1;
//从低位到高位依次进行计数排序
for(i=1;i<=d;i++)
{
//w中保存的是arr中每个元素对应位上的数
//范围在0-k之间
for(j=0;j<len;j++)
w[j]=(arr[j]/val)%10;
//对当前位进行计数排序
count_sort(arr,brr,w,crr,len,k);
val*=10;
}
}
1、同样不是基于比较的排序,因此可以达到线性排序时间;
2、同样采取空间换时间的思想,需要额外的辅助空间,但是时间复杂度仅为O(d(n+k));
3、基数排序的稳定性同样也很好。
分享到:
相关推荐
算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序
简单的十大排序,c++代码实现,堆,冒泡,快速,计数,基数,归并,简单排序等
排序算法中的基数排序,更重要的是会算时间复杂度,基数排序可以说是以计数排序位基础的,只不过变成了一位一位来或者一个字节一个字节来,每位或者每个字节都过了一遍,则排序完毕。很简单的程序,在code::block IDE...
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
基数排序是另一种线性的排序算法,但比起计数排序,更适用于排序的元素比较大的情况,其关键之处在于对于每一位的排序必须使用稳定的排序算法,而计数排序是较好的选择。
排序n个元素,元素为随机生成的1..65535的正整数,n的取值为:23,26,29,212,215,218,221 算法:直接插入排序,快速排序,归并排序,堆排序,基数排序,计数排序。
A_算法在BDD变量最优排序方法中的应用
本文实例讲述了JS实现的计数排序与基数排序算法。分享给大家供大家参考,具体如下: 计数排序 计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在...
基数排序的关键思想是按照数字的个位、十位、百位等逐个进行计数排序,从最低位到最高位。在每个位上,使用计数排序来稳定地排序数组。通过多次迭代,对所有位进行排序后,最终得到有序的数组。 在示例代码中,我们...
基数排序的排序工作在线性时间之内就可以完成,速度非常之快,这里给出了基于计数排序和桶排序的两种类型的基数排序算法
时间复杂度达到O(n)的不同于sort给予比较的O(nlogn)排序,是基于计数的一种线性排序方法,效率非常优秀。
快速排序
在这份文档中,我用C语言实现了排序算法的多种方法,包括插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、桶排序和基数排序。这些算法可以帮助我们对数据进行有效的排序和整理,以便更好地处理和分析...
但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。 算法的步骤如下: 找出待排序的数组中最大和最小的元素 统计数组中每个值为i的元素出现的次数,存入数组C的第i项 对所有的计数累加
针对大多数排序算法只考虑了记录本身的大小和记录相对位置,而忽略了记录内部特征,提出一种...实验结果表明,对于密度高、范围宽、特征位数多的大数组排序问题,该算法的性能优于基数排序、计数排序、静态排序等算法。
O(n)时间完成,是排序中性能最好的!适用于初学者以及有一定水平的学生哦!!!