桶排序、计数排序和基数排序

桶排序

桶排序是一种用空间换取时间的排序，桶排序重要的是它的思想，而不是具体实现，时间复杂度最好可能是线性O(n)，桶排序不是基于比较的排序而是一种分配式的。

桶排序的思想为：将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。当然桶排序选择的方案跟具体的数据有关系，桶排序是一个比较广泛的概念，并且计数排序是一种特殊的桶排序，基数排序也是建立在桶排序的基础上。在数据分布均匀且每个桶元素趋近一个时间复杂度能达到O(n),但是如果数据范围较大且相对集中就不太适合使用桶排序。

计数排序

计数排序是一种特殊的桶排序，每个桶的大小为1，每个桶不在用List表示，而通常用一个值用来计数。

在设计具体算法的时候，先找到最小值min，再找最大值max。然后创建这个区间大小的数组，从min的位置开始计数，这样就可以最大程度的压缩空间，提高空间的使用效率。

public static void countSort(int a[])
{
  int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE;
  for(int i=0;i<a.length;i++)//找到max和min
  {
    if(a[i]<min) 
      min=a[i];
    if(a[i]>max)
      max=a[i];
  }
  int count[]=new int[max-min+1];//对元素进行计数
  for(int i=0;i<a.length;i++)
  {
    count[a[i]-min]++;
  }
  //排序取值
  int index=0;
  for(int i=0;i<count.length;i++)
  {
    while (count[i]-->0) {
      a[index++]=i+min;//有min才是真正值
    }
  }
}

基数排序

基数排序也称为卡片排序，基数排序的原理就是多次利用计数排序(计数排序是一种特殊的桶排序)，但是和前面的普通桶排序和计数排序有所区别的是，基数排序并不是将一个整体分配到一个桶中，而是将自身拆分成一个个组成的元素，每个元素分别顺序分配放入桶中、顺序收集，当从前往后或者从后往前每个位置都进行过这样顺序的分配、收集后，就获得了一个有序的数列。

核心

基数排序就是进行d论计数排序，d是最大数字的长度。每一轮排序就是针对每个数字的某一位做计数排序，每一轮排序的结果是所有元素不一定有序，但是在这一位上是有序。然后在对下一位进行下一轮的计数排序，所有数字在该位上是有序的，该位相等的那些数字在上一位是有序的。所以一共进行d论计数排序之后，所有数字都是有序的。

代码

https://jepson-song.github.io/2021/12/01/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F/