基数排序:降序 [英] Radix Sort: Descending
问题描述
这是我的RadixSort函数(升序):
Here is my RadixSort function (ascending):
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;
}
}
我尝试通过替换将其更改为降序排列
I'm try to change this to a descending sort by replacing
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]
But it didn't work. I tried with: [705, 1725, 99, 9170, 7013]
但是结果是:[9170,7013,1725,99,705]
But the result is: [9170, 7013, 1725, 99, 705]
最后一个值总是错误的.我有什么想念的吗?
The last value is always wrong. Is there anything I missed?
推荐答案
该问题试图在每次通过时反转数组,因为基数排序将顺序保留为相等值.第三遍之后,0705在0099之前结束(7> 0).在最后一遍,最高有效数字为0,因此保留了顺序,因此b [0] = 0705,b [1] = 0099,然后取反为a [] = {...,0099,0705}.
The issue is trying to reverse the array on each pass, since radix sort preserves the order on equal values. After the third pass, 0705 ends up before 0099 (7 > 0). On the last pass, the most significant digits are 0, so the order kept, so b[0] = 0705, b[1] = 0099, then gets reversed to a[] = {..., 0099, 0705}.
与其在每次通过后都进行反转,不如使用9位数字反转用于存储区的索引.对更改进行评论:
Instead of reversing after each pass, reverse the indexes used for bucket by using 9 - digit. The changes are commented:
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;
}
}
这篇关于基数排序:降序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!