#include <iostream>
using namespace std;
int findmax(int arr[], int len)
{
int max = arr[0];
for (int i = 0; i < len; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
int Bit(int max,int radix)
{
int bit = 1;
int leftradix = max;
while ((leftradix = leftradix / radix) > 0)
{
++bit;
}
return bit;
}
void clear(int array[], int len)
{
for (int i = 0; i < len; i++)
{
array[i] = 0;
}
}
int getradixvalue(int data, int radix, int bit)
{
for (int i = 0; i <bit; i++)
{
data /= radix;
}
return data % radix;
}
void radixsort(int arr[], int len, int radixvalue)
{
int max = findmax(arr, len);
int countsize = radixvalue;
int* countarray = new int[countsize]();
int radixbit = Bit(max, radixvalue);
int* tempArr = new int[len]();
for (int i = 0; i < radixbit; i++)
{
clear(countarray, countsize);
for (int j = 0; j < len; ++j)
{
int curadixvalue = getradixvalue(arr[j], radixvalue, i);
++countarray[curadixvalue];
}
for (int c = 1; c < countsize; c++)
{
countarray[c] += countarray[c - 1];
}
for (int j = len - 1; j >= 0; --j)
{
int curradixvalue = getradixvalue(arr[j], radixvalue, i);
tempArr[--countarray[curradixvalue]] = arr[j];
}
for (int j = 0; j < len; j++)
{
arr[j] = tempArr[j];
}
}
delete tempArr;
}
void PrintArray(int array[], int len)
{
for (int i = 0; i < len; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
int main()
{
int array1[5] = { 123,321,242,222,100 };
radixsort(array1, 5, 10);
PrintArray(array1,5);
int array2[3] = { 801,125,109 };
radixsort(array2, 3, 10);
PrintArray(array2, 3);
int array3[5] = { 250,125,109,402,303 };
radixsort(array3, 5, 10);
PrintArray(array3, 5);
}