我不知道为什么这对我来说很难缠住我的头。我浏览了 wiki 页面和伪代码(以及实际代码),试图了解基数排序算法是如何工作的(关于存储桶)。
我在这里寻找错误的东西吗?我应该研究桶排序吗?有人可以给我一个简化版的它是如何工作的吗?作为参考,这是一个据称执行基数排序的代码块:
// 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];