Подготовка.

Суть заключается в поразрядной группировке чисел до тех пор, пока не будет произведена группировка по максимальному существующему среди них разряду. Количество циклов группировки соответствует количеству разрядов в максимальном числе всего массива. Мы разберем случай, когда самое "длинное" число - трехзначное и, следовательно, группировок будет тоже 3.

Для работы с максимальной разрядностью массива нам потребуется знать в лицо максимальный элемент. Чуть позже он нам пригодится.

int getMax(int inputArr[], int length){

    int max = -1;

    for(int i = 0; i < length; i++){
        if (inputArr[i] > max){
            max=inputArr[i];
        }
    }

    return max;
}

Первый этап.

На этапе первого прохода мы смотрим у каждого элемента его самый младший разряд и инкрементируем соответствующую ячейку во вспомогательном массиве. Например, для числа 234 мы прибавляем единицу к 4-му (отсчет ведется с нуля) элементу вспомогательного массива, а для 20 - к нулевому. Таким образом, дойдя до конца, мы получим массив, содержащий информацию о том, сколько чисел с тем или иным младшим разрядом мы имеем в исходном массиве.

Приведена реализация того, что происходит на изображении.

void transposition(int unsortArr[], int length, int sizeOfDiv){

    int outputArr[length]; //массив, который получится после группировки
    int counters[10] = {0}; //вспомогательный массив

    for(int i = 0; i < length; i++){
        counters[(unsortArr[i]/sizeOfDiv)%10] ++;
    }

Наверняка, вы обратили внимание на переменную sizeOfDiv. Она хранит в себе 10 в некоторой степени, что позволяет работать с определенным разрядом каждого числа. Значение этой переменной является параметром и изменяется каждый раз перед вызовом transposition (метод группировки). Приведена реализация вызывающего метода sort.

void sort(int inputArr[], int n){
    int max = getMax(inputArr, n);//вызов метода получения максимального элемента в массиве.

    for(int i = 1; max/i > 0; i*=10){
        transposition(inputArr, n,  i);
    }
}

Второй этап.

Группировка представляет собой расположение чисел исходного массива по возрастанию их n-го разряда, то есть так, чтобы сначала следовали те числа, что с нулями в n-том разряде, затем с единицами, двойками, тройками и т. д. Для реализации этой задачи нам нужно провести довольно простую обработку вспомогательного массива - к каждому последующему его элементу мы будем прибавлять предыдущий.

for(int i = 1; i < 10; i++){
        counters[i] += counters[i-1];
    }

Таким образом, если вы заметили, массив в своих значениях хранит индексы(+1 из-за нуля!!!) элементов, на которых будет располагаться последнее число с разрядом, равным индексу этого элемента. Например, если идут 3 элемента с нулями и 5 элементов с единицами, то на позициях 0, 1, 2 будут располагаться элементы с нулями, а на 3, 4, 5, 6, 7 - с единицами (при реализации следует учитывать, что отсчет начинается с 0).

Забегая вперед, вот так выглядит уже группированный по текущему разряду массив. На изображении ниже можно уловить связь между значениями вспомогательного массива и результатом группировки.

Но не будем торопиться и теперь выполним, непосредственно, саму группировку.

Третий этап.

Как мы уже определили, вспомогательный массив хранит индексы + 1 , на которые нужно расставлять элементы. Для этого идем с конца по исходному массиву и снова узнаем значение его n-разряда. Затем смотрим, какое число располагается во вспомогательном массиве по индексу, равному этому значению разряда (условно назовем его "новое место"), уменьшаем его на 1 и перемещаем обрабатываемое число из исходного массива в новый на "новое место".

Например, если нам встретилось число 105, то смотрим, какое число находится во вспомогательном массиве в 5 ячейке (например, 21) и помещаем число 105 в 20 ячейку нового массива. Нагляднее на анимации:

Реализация:

for(int i = length-1; i >= 0; i--){
        outputArr[--counters[(unsortArr[i]/sizeOfDiv) % 10]] = unsortArr[i];
    }

Для перехода на следующий этап нужно лишь обновить исходный массив, скопировав в него получившийся, чтобы заново производить с ним те же операции:

for(int i = 0; i < length; i++){
        unsortArr[i] = outputArr[i];
    }

Теперь, когда мы получили новый массив, он далеко не похож на отсортированный, но повторив данную последовательность операций со всеми следующими разрядами уже получившегося массива, после обработки максимального последнего разряда, эта последовательность чисел будет отсортирована.

В итоге полный код программы состоит из 3 методов:

void transposition(int unsortArr[], int length, int sizeOfDiv){
    //первый этап
    int outputArr[length]; //массив, который получится после прохода
    int counters[10] = {0}; //вспомогательный массив

    for(int i = 0; i < length; i++){//
        counters[(unsortArr[i]/sizeOfDiv)%10] ++;
    }
    //второй этап
    for(int i = 1; i < 10; i++){
        counters[i] += counters[i-1];
    }
    //третий этап
    for(int i = length-1; i >= 0; i--){
        outputArr[--counters[(unsortArr[i]/sizeOfDiv) % 10]] = unsortArr[i];
    }
    //завершение и подготовка к следующей группировке
    for(int i = 0; i < length; i++){
        unsortArr[i] = outputArr[i];
    }
}

int getMax(int inputArr[], int length){ //Находим максимальный элемент массива.

    int max = -1;

    for(int i = 0; i < length; i++){
        if (inputArr[i] > max){
            max=inputArr[i];
        }
    }
    return max;
}

void sort(int inputArr[], int n){
    int max = getMax(inputArr, n);

    for(int i = 1; max/i > 0; i*=10){
        makeLayer(inputArr, n,  i);
    }

}

Характеристика алгоритма:

Красивая визуализация.

КАПЕЦ-КАКАЯ-КРАСИВАЯ-НО-ДОФИГА-СОВСЕМ-НЕПОНЯТНАЯ-ПОТОМУ-ЧТО-БЫСТРАЯ-ДЛЯ-ПРОСТЫХ-СМЕРТНЫХ ВИЗУАЛИЗАЦИЯ.