基数排序：降序

Question

这里是我的基数排序功能（升序）：

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]

的最后一个值永远是错的。有什么我错过了吗？

Answer 1

问题是试图在每次传递时都颠倒数组，因为基数排序保留了相同值的顺序。第三次过后，0705在0099（7> 0）之前结束。在最后一遍中，最高有效位是0，所以顺序保持不变，因此b [0] = 0705，b [1] = 0099，然后反转为[] = {...，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; 
    } 
}