Я не знаю, почему мне так трудно уложить это в голове. Я просмотрел вики-страницы и псевдокод (а также фактический код), пытаясь понять, как работают алгоритмы сортировки по основанию (относительно корзин).
Я смотрю на неправильную вещь здесь? Может быть, мне стоит заняться сортировкой ведра? Может ли кто-нибудь дать мне упрощенную версию того, как это работает? Для справки, вот кодовый блок, который предположительно выполняет сортировку по основанию:
// 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];
