锐客网

  1. 首页 > it技术 > >

C/C++|【算法导论】基数排序

c

基数排序 时间复杂度：O(n).
基本思路：两个数比较大小，我们的直观感觉是先比较高位，若相同则比较低位。但是这样做需要记录额外的数据，浪费空间。而基数排序则是先比较低位，再比较高位。通过各个位的比较进行排序，如果数组元素最大有N位，则总共需要N次排序。注意：按位排序必须是稳定排序，所以在这我选择了计数排序。具体操作见下图：
C/C++|【算法导论】基数排序
文章图片

具体实现如下：

#include #include #includevoid CountSort(int* arrayA,int* arrayD,int n,int k); void RadixSort(int* arrayA,int n); void main() { int arrayD[]={1046,2084,9046,12074,56,7026,8099,17059,33,1}; int n=sizeof(arrayD)/sizeof(int); RadixSort(arrayD,n); for(int i=0; i=0; j--) { arrayB[arrayC[arrayA[j]]-1]=arrayD[j]; arrayC[arrayA[j]]=arrayC[arrayA[j]]-1; //进行计数排序 } for(int i=0; i


注意：我是在vs2008上运行的，与vc 6.0有点区别，主要是循环体中的循环变量的作用域，出错体现在循环变量的重复定义上。例如：在vs2008或vs2010上，程序为：
#include
void main()
{
int i=0;
for(int i=0; i<5; i++)
printf("%d ",i);
}

则在VC 6.0上需改为：
【C/C++|【算法导论】基数排序】#include
void main()
{
int i=0;
for(i=0; i<5; i++)
printf("%d ",i);
}

原文：http://blog.csdn.net/tengweitw/article/details/9670303
作者：nineheadedbird

    推荐阅读


    上一篇：Spring的@PostConstruct与ApplicationContextAware冲突问题

    下一篇：python|python opencv入门 背景减除算法法（42）