Я не знаю, почему мне так тяжело обнимать голову. Я просмотрел страницы 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];
