关于算法:八大排序算法16张图带你彻底搞懂基数排序

原创公众号：bigsai 转载需分割作者

前言

在排序算法中，大家可能对桶排序、计数排序、基数排序不太理解，不太分明其算法的思维和流程，也可能看过会过然而很快就遗记了，然而不要紧，侥幸的是你看到了本篇文章。本文将通俗易懂的给你解说基数排序。

基数排序，是一种原理简略，但实现简单的排序。很多人在学习基数排序的时候可能会遇到以下两种状况而浅尝辄止：

• 一看原理，这么简略，懂了懂了(顺便溜了)
• 再一看代码，这啥啥啥啊？这些的必定有问题(不看溜了)

要想深刻了解基数排序，必须搞懂基数排序各种模式 (数字类型、等长字符类型、不等长字符) 各自实现办法，理解其中的分割和区别，并且也要把握空间优化的办法(非二维数组而仅用一维数组)。上面跟着我具体学习基数排序吧！

基数排序原理

首先百度百科看看基数排序的定义：

基数排序（radix sort）属于“调配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素调配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，基数排序法的效率高于其它的稳定性排序法。

基数排序也称为卡片排序，简而言之，基数排序的原理就是屡次利用计数排序(计数排序是一种非凡的桶排序)，然而和后面的一般桶排序和计数排序有所区别的是，基数排序并不是将一个整体调配到一个桶中，而是将本身拆分成一个个组成的元素，每个元素别离程序调配放入桶中、程序收集，当从前往后或者从后往前每个地位都进行过这样程序的调配、收集后，就取得了一个有序的数列。

在具体实现上如果从左往右那就是 最高位优先 (Most Significant Digit first) 法，简称 MSD 法；如果从右往左那就是 最低位优先 (Least Significant Digit first) 法，简称 LSD 法。然而不论从最高位开始还是从最低位开始要保障和雷同位进行比拟，你须要留神的是如果是 int 等数字类型须要保障从右往左 (从低位到高位) 保障对齐，如果是字符类型的话须要从左往右 (从高位到低位) 保障对齐。

你可能会问为啥不间接将这个数或者这个数依照区间范畴放到对应的桶中，一方面基数排序可能很多时候解决的是字符型的数据，不不便放入某个桶中，另一方面如果数字很大，不不便间接放入桶中。并且基数排序并不需要替换，也不须要比拟，就是屡次调配、收集失去后果。

所以遇到这种状况咱们基数排序思维很简略，就拿 934，241，3366，4399 这几个数字进行基数排序的一趟过程来看，第一次会依据各位进行调配、收集：

调配和收集都是有序的，第二次会依据十位进行调配、收集，此次是在第一次个位调配、收集根底上进行的，所以所有数字单看个位十位是有序的。

而第三次就是对百位进行调配收集，此次实现之后百位及其以下是有序的。

而最初一次的时候进行解决的时候，千位有的数字须要补零，这次结束后后千位及当前都有序，即整个序列排序实现。

想必看到这里基数排序的思维你也曾经懂了吧，然而尽管懂你不肯定可能写出代码来，持续看看上面的剖析和实现。

数字类型基数排序

有很多时候也有很多时候对基数排序的解说也是基于数字类型的，而数字类型这里就用 int 来实现，对于数字类型的基数排序你须要留神的有以下几点：

• 无论是最高位优先法还是最低位优先法进行遍历须要保障数字各位、十位、百位等对齐，这里我应用最低位优先法从个位开始向上。
• 数字类型的基数排序须要十个桶(0-9)，你能够应用二维数组，第一维度长度为 10 示意十个数字，第二个维度为数组长度，用来存储数字(因为最坏状况可能以后位数字一样)。但这样无疑太节约内存空间了，你能够应用 List 或者 Queue 代替，这里就用 List 了。
• 具体实现要先找到最大值确定最高多少位，用来进行遍历时候确认。
• 收集的时候借助一个自增参数遍历收集。
• 每次收集结束十个桶 (bucket) 须要清空待下次收集。

实现的代码为：

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();// 收集完须要清空留下次持续应用}
  }
}

等长字符串基数排序

除了数字之外，等长字符串也是经常遇到的形式，其次要办法和数字类型差不多，这里也看不出策略上的不同。低位优先法或者高位优先法都可应用(这里仍旧低位从右向左)。

在实现细节方面，和后面的数字类型区别不是很大，然而因为字符串是等长的遍历更加不便容易。但须要额定留神的是：

• 字符类型的桶 bucket 不是 10 个而是 ASCII 字符的个数(依据理论须要查看 ASCII 表)。其实就是利用 char 和 int 之间关系能够间接依照每个字符进行顺序存储。

具体实现代码为：

static void radixSort(String arr[],int len)// 等长字符排序状况 长度为 len
{List<String>buckets[]=new ArrayList[128];
  for(int i=0;i<128;i++)
  {buckets[i]=new ArrayList<String>();}
  for(int i=len-1;i>=0;i--)// 每一位上进行操作
  {for(String str:arr)
    {buckets[str.charAt(i)].add(str);// 调配
    }
    int idx=0;
    for(List<String>list:buckets)
    {for(String str:list)
      {arr[idx++]=str;// 收集
      }
      list.clear();// 收集完该 bucket 清空}
  }
}

非等长字符串基数排序

等长的字符串进行基数排序时候很好遍历，那么非等长的时候该如何思考呢？这种非等长不能像解决数字那样粗犷的计算当成 0 即可。字符串的大小是从返回后进行排列的 ( 和长度没关系)。例如看上面字符串，“d”这个字符串即便很短然而在排序仍然放在最初面。你晓得该怎么解决吗？

"abigsai"
"bigsai"
"bigsaisix"
"d"

如果 高位优先 ，后面一旦比拟过各个字符的桶(bucket) 就要固定下来，也就是在进行右面下一个字符调配、收集的时候要标记空间，即下次进行调配收集的后面是‘a’字符的一组，‘b’字符一组，并且不能越界，实现起来很麻烦这里就不具体解说了有趣味的能够自行钻研一下。

而本篇实现的是 低位优先。低位优先采纳什么思路呢？很简略，跟我看图解。

第一步，先将字符依照长度进行调配到一个桶 (bucket) 中，申明一个List<String>wordLen[maxlen+1]; 在遍历字符时候，以字符长度为下表 index，将字符串程序退出进去。其中 maxlen 为最长字符串长度，之所以要 maxlen+ 1 是因为须要应用 maxlen 下标(0-maxlen)。

第二步，调配实现遍历收集到原数组中，这样原数组 在长度上绝对有序。

这样就能够进行基数排序啦，当然，在开始的时候并不是全副都进行调配收集，而是依据长度缓缓递加，长度能够达到 6 位调配、收集，长度达到 5 的调配、收集……长度为 1 的进行调配、收集。这样进行一遭就很完满的进行完基数排序，因为咱们借助依据长度收集的桶能够很容易晓得以后长度开始的 index 在哪里。

具体实现的代码为：

static void radixSort(String arr[])// 字符不等长的状况进行排序
{
    // 找到最长的那个
    int maxlen=0;
    for(String team:arr)
    {if(team.length()>maxlen)
            maxlen=team.length();}
    // 一个对长度分  一个对具体字符分，先用长度来找到
    List<String>wordLen[]=new ArrayList[maxlen+1];// 用长度先统计各个长度的单词
    List<String>bucket[]=new ArrayList[128];// 依据字符来划分
    for(int i=0;i<wordLen.length;i++)
        wordLen[i]=new ArrayList<String>();
    for(int i=0;i<bucket.length;i++)
        bucket[i]=new ArrayList<String>();
    // 先依据长度来一下
    for(String team:arr)
    {wordLen[team.length()].add(team);
    }
    int index=0;// 先进行一次 (依照长度分) 的桶排序使得数组长度初步有序
    for(List<String>list:wordLen)
    {for(String team:list)
        {arr[index++]=team;
        }
    }
    // 而后 先进行长的 从后往前进行
    int startIndex=arr.length;
    for(int len=maxlen;len>0;len--)// 每次长度雷同的要进行基数一次
    {
        int preIndex=startIndex;
        startIndex-=wordLen[len].size();
        for(int i=startIndex;i<arr.length;i++)
        {bucket[arr[i].charAt(len-1)].add(arr[i]);// 利用字符桶从新装
        }
        // 从新收集
        index=startIndex;
        for(List<String>list:bucket)
        {for(String str:list)
            {arr[index++]=str;
            }
            list.clear();}
    }
}

空间优化 (等长字符) 基数排序

下面无论是等长还是不等长，应用的空间其实都是跟二维相干的，咱们能不能应用一维的空间去解决这个问题呢？当然能啊。

在应用空间的整个思路是差不多的，然而这里为了让你可能了解咱们在解说的时候解说 等长字符串的状况。

先回顾刚刚讲的等长字符串，就是从个位进行遍历，在遍历的时候将数据放到对应的桶外面，而后在进行收集的时候放回原数组。

你是否发现什么法则？

• 一个字符串收集的时候放的地位其实它 只须要晓得它后面有多少个就能够确定！
• 并且 以后地位字符如果雷同 那么就是依据 arr 中绝对程序来进行以后轮。

所以咱们能够尝试来动静保护这个 int bucket[]。第一次进行只记录次数，第二次进行叠加示意比以后地位 + 1 编号小的元素的个数。

然而这样解决不太好晓得比以后地位小的有多少，所以咱们在调配的时候向下挪一位，这样 bucket[i]就能够示意比以后地位小的元素的个数。

咱们在进行收集的时候须要再次遍历 arr，但咱们须要一个长期数组 String value[]贮存后果 (因为 arr 没遍历完前面不能应用)，而进行遍历的规定就是：遍历 arr 时候对应字符串 str，该位字符对应bucket[str.charAt(i)] 桶中数字就是要放到 arr 中的编号(多少个比它小的就放到第多少位)，搁置之后要对 bucket 以后位自增(因为下一个这个地位字符串要把这个 str 思考进去)。这样到最初即可实现排序。

第一趟遍历 arr 前两个字符串局部过程如下：

第一趟两头两个字符串解决状况：

第一趟最初两个字符串解决状况：

就这样即可实现一趟操作，一趟实现记得将 value 的值赋值到 arr 中，当然有办法应用指针援用能够防止替换数据带来的工夫影响，但这里为了使大家更加简略了解就间接复制过来。这样实现若干次，整个基数排序即可实现。

具体实现的代码为：

static void radixSortByArr(String arr[],int len)// 固定长度的应用数组进行优化
{
    int charLen=129;// 多用一个

    String value[]=new String[arr.length];
    for(int index=len-1;index>=0;index--)// 不同的地位
    {int bucket[]=new int[charLen];// 贮存 character 的桶
        for(int i=0;i<arr.length;i++)// 调配
        {bucket[(int)(arr[i].charAt(index)+1)]++;
        }
        for(int i=1;i<bucket.length;i++)// 叠加 以后 i 地位示意比本人小的个数
        {bucket[i]+=bucket[i-1];
        }

        for(int i=0;i<arr.length;i++)
        {value[bucket[arr[i].charAt(index)]++]=arr[i];// 两头的 ++ 因为以后地位填充了一个，下次再来同元素就要后移
        }
        System.arraycopy(value,0,arr,0,arr.length);//copy 数组
    }
}

至于不定长的，思路也差不多，这里就留给你优良的你本人去思考啦。

结语

至于基数排序的算法剖析，以定长的状况剖析，假如有 n 数字 (字符串)，每个有 k 位，那么依据基数就要每一位都遍历就是 K 次，每次都是 O(n) 级别。所以差不多是 O(n*k)级别，当然 k 远远小于 n，可能有成千上万个数，然而每个数或者字符失常可没成千上万那么长。

本次基数排序就全讲完啦，那么多张图我想你也应该懂了。

最初我请你们两连事帮忙一下:

1. 点赞、关注一下反对，您的必定是我在平台创作的源源能源。
2. 微信搜寻「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一工夫在公众号分享常识技术。加我还可拉你进力扣打卡群一起打卡 LeetCode。

记得关注、咱们下次再见！