Radix Sort: Descending

问题:

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];
}

with

for (i=0; i<n;i++) {
    a[i]=b[n-i-1];
}

But it didn't work. I tried with: [705, 1725, 99, 9170, 7013]

But the result is: [9170, 7013, 1725, 99, 705]

The last value is always wrong. Is there anything I missed?

回答1:

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}.

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;
    }
}