【408数据结构与算法】—基数排序（桶排序）（二十三）

//基数排序
void RadixSort(int* arr, int n)
{
  //max为数组中最大值
  int max = arr[0];
  int base = 1;
  //找出数组中的最大值
  for (int i = 0; i < n; i++)
  {
    if (arr[i] > max)
    {
      max = arr[i];
    }
  }
  //循环结束max就是数组最大值
  //临时存放数组元素的空间
  int* tmp = (int*)malloc(sizeof(int)*n);
  //循环次数为最大数的位数
  while (max / base > 0)
  {
    //定义十个桶，桶里面装的不是数据本身，而是每一轮排序对应（十、白、千...）位的个数
    //统计每个桶里面装几个数
    int bucket[10] = { 0 };
    for (int i = 0; i < n; i++)
    {
      //arr[i] / base % 10可以取到个位、十位、百位对应的数字
      bucket[arr[i] / base % 10]++;
    }
    //循环结束就已经统计好了本轮每个桶里面应该装几个数
    //将桶里面的元素依次累加起来，就可以知道元素存放在临时数组中的位置
    for (int i = 1; i < 10; i++)
    {
      bucket[i] += bucket[i - 1];
    }
    //循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置
    //开始放数到临时数组tmp
    for (int i = n - 1; i >= 0; i--)
    {
      tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
      bucket[arr[i] / base % 10]--;
    }
    //不能从前往后放，因为这样会导致十位排好了个位又乱了，百位排好了十位又乱了
    /*for (int i = 0; i < n; i++)
    {
      tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
      bucket[arr[i] / base % 10]--;
    }*/
    //把临时数组里面的数拷贝回去
    for (int i = 0; i < n; i++)
    {
      arr[i] = tmp[i];
    }
    base *= 10;
  }
  free(tmp);
}