Question

#include <iostream>
#include <cmath>
using namespace std;

int length_A, digit;

void Print(int *A, int start, int end)
{
  int i;
  for(i = start; i <= end; i++)
  {
    if(i == start)cout<<'{';
    else cout<<' ';
    cout<<A[i];
  }
  cout<<'}'<<endl;
}

//计数排序
void Counting_Sort(int *A, int *B, int k)
{
  int i, j;
  //将 C 数组初始化为 0，用于计数
  int *C = new int[k+1];
  for(i = 0; i <= k; i++)
    C[i] = 0;
  //C[j]表示数字 j 在数组 A 中出现的次数
  for(j = 1; j <= length_A; j++)
    C[A[j]]++;
  //C[i]表示所以<=i 的数字出现过的次数
  for(i = 1; i <= k; i++)
    C[i] = C[i] + C[i-1];
  //初始化 B 为 0，B 用于输出排序结果
  for(i = 1; i <= length_A; i++)
    B[i] = 0;
  for(j = length_A; j >= 1; j--)
  {
    //如果<=A[j]的数字的个数是 x,那么排序后 A[j]应该出现在第 x 个位置，即 B[x]=A[j]
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
  delete C;
}
//基数排序调用的稳定排序
void Stable_Sort(int *A, int *B, int k, int d)
{
  int i, j;
  //将 C 数组初始化为 0，用于计数
  int *C = new int[k+1];
  for(i = 0; i <= k; i++)
    C[i] = 0;
  int *D = new int[length_A+1];
  for(j = 1; j <= length_A; j++)
  {
    //D[j]表示第[j]个元素的第 i 位数字
    D[j] = A[j] % (int)pow(10.0, d) / (int)pow(10.0, d-1);
    //C[j]表示数字 D[j]在数组 A 中出现的次数
    C[D[j]]++;
  }
  //C[i]表示所以<=i 的数字出现过的次数
  for(i = 1; i <= k; i++)
    C[i] = C[i] + C[i-1];
  //初始化 B 为 0，B 用于输出排序结果
  for(i = 1; i <= length_A; i++)
    B[i] = 0;
  for(j = length_A; j >= 1; j--)
  {
    //如果<=D[j]的数字的个数是 x,那么排序后 A[j]应该出现在第 x 个位置，即 B[x]=A[j]
    B[C[D[j]]] = A[j];
    C[D[j]]--;
  }
  delete []C;
  delete []D;
}
//基数排序
void Radix_Sort(int *A, int *B)
{
  int i, j;
  //依次对每一位进行排序，从低位到高位
  for(i = 1; i <= digit; i++)
  {
    Stable_Sort(A, B, 9, i);
    //输入的是 A，输出的是 B，再次排序时要把输出数据放入输出数据中
    for(j = 1; j <= length_A; j++)
    A[j] = B[j];
  }
}

int main()
{
  cin>>length_A>>digit;
  int *A = new int[length_A+1];
  int *B = new int[length_A+1];
  int i;
  //随机产生 length_A 个 digit 位的数据
  for(i = 1; i <= length_A; i++)
  {
    A[i] = 0;
    while(A[i] < (int)pow(10.0, digit-1))
      A[i] = rand() % (int)pow(10.0, digit);
  }
  Print(A, 1, length_A);
//  Counting_Sort(A, B, 9);
  Radix_Sort(A, B);
  Print(A, 1, length_A);
  delete []A;
  delete []B;
  return 0;
}