基数排序:降序
Radix Sort: Descending
这是我的 RadixSort 函数(升序):
void RadixSort (int a[], int n)
{
int i, m=0, exp=1, b[MAX];
for (i=0; i<n; i++)
{
if (a[i]>m)
m=a[i];
}
while (m/exp>0)
{
int bucket[10]={0};
for (i=0; i<n; i++)
bucket[a[i]/exp%10]++;
for (i=1; i<10; i++)
bucket[i]+=bucket[i-1];
for (i=n-1; i>=0; i--)
b[--bucket[a[i]/exp%10]]=a[i];
for (i=0; i<n;i++){
a[i]=b[i];
}
exp*=10;
}
}
我尝试通过替换
将其更改为降序
for (i=0; i<n;i++) {
a[i]=b[i];
}
与
for (i=0; i<n;i++) {
a[i]=b[n-i-1];
}
但是没有用。
我试过:[705, 1725, 99, 9170, 7013]
但结果是:[9170, 7013, 1725, 99, 705]
最后一个值总是错误的。有什么我遗漏的吗?
问题是试图在每次传递时反转数组,因为基数排序保留了相等值的顺序。第三遍之后,0705 在 0099 (7 > 0) 之前结束。在最后一遍中,最高有效位为 0,因此顺序保持不变,因此 b[0] = 0705, b[1] = 0099,然后反转为 a[] = {..., 0099, 0705}。
不是在每次通过后都反转,而是使用 9 位反转用于存储桶的索引。更改评论:
void RadixSort (int a[], int n){
int i, m=0, exp=1, b[MAX];
for (i=0; i<n; i++)
if (a[i]>m)
m=a[i];
while (m/exp>0)
{
int bucket[10]={0};
for (i=0; i<n; i++)
bucket[9-a[i]/exp%10]++; // changed this line
for (i=1; i<10; i++)
bucket[i]+=bucket[i-1];
for (i=n-1; i>=0; i--)
b[--bucket[9-a[i]/exp%10]]=a[i]; // changed this line
for (i=0; i<n;i++){
a[i]=b[i]; // changed this line
}
exp*=10;
}
}
这是我的 RadixSort 函数(升序):
void RadixSort (int a[], int n)
{
int i, m=0, exp=1, b[MAX];
for (i=0; i<n; i++)
{
if (a[i]>m)
m=a[i];
}
while (m/exp>0)
{
int bucket[10]={0};
for (i=0; i<n; i++)
bucket[a[i]/exp%10]++;
for (i=1; i<10; i++)
bucket[i]+=bucket[i-1];
for (i=n-1; i>=0; i--)
b[--bucket[a[i]/exp%10]]=a[i];
for (i=0; i<n;i++){
a[i]=b[i];
}
exp*=10;
}
}
我尝试通过替换
将其更改为降序for (i=0; i<n;i++) {
a[i]=b[i];
}
与
for (i=0; i<n;i++) {
a[i]=b[n-i-1];
}
但是没有用。 我试过:[705, 1725, 99, 9170, 7013]
但结果是:[9170, 7013, 1725, 99, 705]
最后一个值总是错误的。有什么我遗漏的吗?
问题是试图在每次传递时反转数组,因为基数排序保留了相等值的顺序。第三遍之后,0705 在 0099 (7 > 0) 之前结束。在最后一遍中,最高有效位为 0,因此顺序保持不变,因此 b[0] = 0705, b[1] = 0099,然后反转为 a[] = {..., 0099, 0705}。
不是在每次通过后都反转,而是使用 9 位反转用于存储桶的索引。更改评论:
void RadixSort (int a[], int n){
int i, m=0, exp=1, b[MAX];
for (i=0; i<n; i++)
if (a[i]>m)
m=a[i];
while (m/exp>0)
{
int bucket[10]={0};
for (i=0; i<n; i++)
bucket[9-a[i]/exp%10]++; // changed this line
for (i=1; i<10; i++)
bucket[i]+=bucket[i-1];
for (i=n-1; i>=0; i--)
b[--bucket[9-a[i]/exp%10]]=a[i]; // changed this line
for (i=0; i<n;i++){
a[i]=b[i]; // changed this line
}
exp*=10;
}
}