基数排序是一种很容易了解但是比较难完成(优化)的算法。基数排序也称为卡片排序，基数排序的原理就是屡次应用计数排序(计数排序是一种特殊的桶排序)，但是和前面的普通桶排序和计数排序有所区别的是， 「基数排序并不是将一个全体分配到一个桶中」 ，而是将本身拆分红一个个组成的元素，每个元素辨别顺序分配放入桶中、顺序搜集，当从前往后或许从后往前每个位置都停止过这样顺序的分配、搜集后，就取得了一个有序的数列。 

假设是数字类型排序，那么这个桶只需求装0-9大小的数字，但是假设是字符类型，那么就需求留意ASCII的范围。

所以遇到这种状况我们基数排序思想很复杂，就拿 934，241，3366，4399这几个数字停止基数排序的一趟进程来看，第一次会依据各位停止分配、搜集： 

分配和搜集都是有序的，第二次会依据十位停止分配、搜集，此次是在第一次个位分配、搜集基础上停止的，所以一切数字单看个位十位是有序的。 

而第三次就是对百位停止分配搜集，此次完成之后百位及其以下是有序的。 

而最后一次的时分停止处置的时分，千位有的数字需求补零，这次终了后后千位及以后都有序，即整个序列排序完成。 

复杂实现代码为：

static void radixSort(int[] arr)//int 类型 从右往左 

{ 

  List<Integer>bucket[]=new ArrayList[10]; 

  for(int i=0;i<10;i++) 

  { 

    bucket[i]=new ArrayList<Integer>(); 

  } 

  //找到最大值 

  int max=0;//假定都是正数 

  for(int i=0;i<arr.length;i++) 

  { 

    if(arr[i]>max) 

      max=arr[i]; 

  } 

  int divideNum=1;//1 10 100 100……用来求对应位的数字 

  while (max>0) {//max 和num 控制 

    for(int num:arr) 

    { 

      bucket[(num/divideNum)%10].add(num);//分配 将对应位置的数字放到对应bucket中 

    } 

    divideNum*=10; 

    max/=10; 

    int idx=0; 

    //搜集 重新捡起数据 

    for(List<Integer>list:bucket) 

    { 

      for(int num:list) 

      { 

        arr[idx++]=num; 

      } 

      list.clear();//搜集完需求清空留下次继续运用 

    } 

  } 

} 

当然，基数排序还有字符串等长、不等长、一维数组优化等各种完成需求需学习，详细可以参考群众号内其他文章。

(责任编辑：admin)