基數排序：降序

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