基数排序

#include <iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

void countingSort(int arr[], int n, int place) {
  int output[n];
  int count[N];

  for (int i = 0; i < N; ++i) count[i] = 0;

  for (int i = 0; i < n; i++) count[(arr[i] / place) % 10]++;

  for (int i = 1; i < N; i++) count[i] += count[i - 1];

  for (int i = n - 1; i >= 0; i--) {
    output[count[(arr[i] / place) % 10] - 1] = arr[i];
    count[(arr[i] / place) % 10]--;
  }

  for (int i = 0; i < n; i++) arr[i] = output[i];
}

void radixsort(int arr[], int n) {
  int max = maxm(arr, n);
  for (int place = 1; max / place > 0; place *= 10) countingSort(arr, n, place);
}

int main() {
  int n = 5;
  int arr[5] = {1851, 913, 1214, 312, 111};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  radixsort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}