Как работает Radix Sort?

Я не знаю, почему мне так тяжело обнимать голову. Я просмотрел страницы wiki и псевдокод (а также фактический код), пытаясь понять, как работают алгоритмы сортировки счисления (относительно ковшей).

Я смотрю на неправильную вещь здесь? Должен ли я смотреть в сортировку ведра? Может ли кто-нибудь дать мне тупой вариант того, как это работает? Для справки, вот кодовый блок, который предположительно выполняет сортировку radix:

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

И я также посмотрел на нерекурсивные решения:

void radixsort(int *a, int arraySize)
{
    int i, bucket[sortsize], maxVal = 0, digitPosition =1 ;
    for(i = 0; i < arraySize; i++) {
        if(a[i] > maxVal) maxVal = a[i];
    }

    int pass = 1; 
    while(maxVal/digitPosition > 0) {
        // reset counter 
        int digitCount[10] = {0};

        // count pos-th digits (keys) 
        for(i = 0; i < arraySize; i++)
            digitCount[a[i]/digitPosition%10]++;

        // accumulated count 
        for(i = 1; i < 10; i++)
            digitCount[i] += digitCount[i-1];

        // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

        for(i = 0; i < arraySize; i++)
            a[i] = bucket[i];

        cout << "pass #" << pass++ << ": ";
        digitPosition *= 10;
    } 

}

В частности, эта линия дает мне проблемы. Я пробовал пропустить его с помощью ручки и бумаги, но я все еще не могу понять, что это делает:

   // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

Ответы

Ответ 1

В математике основание оснований оснований, где десятичное будет основанием 10. Представьте, что у вас есть числа, некоторые из которых имеют более чем одну цифру, например

5, 213, 55, 21, 2334, 31, 20, 430

Для простоты, скажем, вы хотите использовать десятичное основание (= 10) для сортировки. Затем вы начнете с разделения чисел на единицы и последующего объединения их снова; Затем вы разделите числа на десятки и затем снова соедините их; затем сотнями и так далее, пока все номера не будут отсортированы. Каждый раз, когда вы зацикливаете, просто читайте список слева направо. Вы также можете представить, что вы разделяете числа на ведра. Вот иллюстрация с помощью 5, 213, 55, 21, 2334, 31, 20, 430

Отдельно по единицам:

  • нули: 20, 430

  • : 21, 31

  • двойки:

  • threes: 213

  • fours: 2334

  • fives: 5, 55

    Назад вместе: 20, 430, 21, 31, 213, 2334, 5, 55

Чтобы вернуть их обратно, сначала прочтите ведро zeroes, затем ведро ones, затем и так далее, пока вы не прочитаете ведро nines.

Разделить на десятки:

  • нули: 05

  • : 213

  • twos: 20, 21

  • тройки: 430, 31, 2334,

  • четверок:

  • пять: 55

    Назад вместе: 5, 213, 20, 21, 430, 31, 2334, 55

Отдельно сотнями:

  • нули: 005, 020, 021, 031, 055

  • из них:

  • twos: 213

  • тройки: 2334

  • fours: 430

  • пятерок:

    Назад вместе: 5, 20, 21, 31, 55, 213, 2334, 430

Разделить на тысячи:

  • нули: 0005, 0020, 0021, 0031, 0055, 0213, 0430

  • из них:

  • twos: 2334

  • троек:

  • четверок:

  • пятерок:

    Назад вместе: 5, 20, 21, 31, 55, 213, 430, 2334

Теперь вы закончили. Я видел хороший код для этого в Geekviewpoint как в Java, так и в python

Ответ 2

Подумайте о колоде карт. Сначала вы сортируете его по костюмам в четырех сваях. Затем вы кладете эти четыре сваи друг на друга и теперь сортируете по 13 свай по рангу. Поместите их вместе, и теперь у вас есть сортированная колода.

Ответ 3

Это основной поток quicksort.

Для 1-го прохождения: мы сортируем массив по наименьшей значащей цифре (1-е место) с использованием сортировки подсчета. Обратите внимание, что 435 ниже 835, потому что 435 произошло ниже 835 в исходном списке.

Для второго прохода: мы сортируем массив на основе следующей цифры (10-е место) с использованием сортировки подсчета. Обратите внимание, что здесь 608 ниже 704, потому что 608 произошло ниже 704 в предыдущем списке и аналогично для (835, 435) и (751, 453).

Для третьего прохода: мы сортируем массив на основе наиболее значимой цифры (место 100 с) с использованием сортировки подсчета. Обратите внимание, что здесь 435 ниже 453, потому что 435 произошло ниже 453 в предыдущем списке и аналогично для (608, 690) и (704, 751).

Подробнее... вы можете ссылаться на этот блог на codingeek и иметь четкое понимание.