基數按降序排序

Question

我可以按升序對數組排序，但我不知道如何按降序排序。

void radixSort(int *a, int arraySize) 
{ 

    int i, bucket[arraySize]; 

    int maxVal = 0; 

    int digitPosition =1; 

    for(i = 0; i < arraySize; i++) 
    { 
     if(a[i] > maxVal) 
     maxVal = a[i]; 
    } 

    int pass = 1; 

    while(maxVal/digitPosition > 0) 
    { 

     int digitCount[10] = {0}; 

     for(i = 0; i < arraySize; i++) 
      digitCount[a[i]/digitPosition%10]++; 

     for(i = 1; i < 10; i++) 
      digitCount[i] += digitCount[i-1]; 

     for(i = arraySize - 1; i >= 0; i--) 
      bucket[--digitCount[a[i]/digitPosition%10]] = a[i]; 


     for(i = 0; i < arraySize; i++) 
      a[i] = bucket[i]; 

     digitPosition *= 10; 
    } 
} 

Answer 1

void radixSort(int *a, int arraySize){ 
    vector<int> mybucket[10]; 
    int i,j,maxVal = 0,digitPosition=1; 
    for(i = 0; i < arraySize; i++){ 
     if(a[i] > maxVal) 
      maxVal = a[i]; 
    } 
    int p =1; 
    char str[20]; 
    sprintf(str,"%d",maxVal); 
    while(p <= strlen(str)){ 
     for(i = 0; i < arraySize; i++) 
      mybucket[(a[i]/digitPosition)%10].push_back(a[i]); 
     int k = 0; 
     for(i = 9;i>=0;i--){ 
      for(j=0;j<mybucket[i].size();j++){ 
       a[k++] = mybucket[i][j]; 
      } 
      mybucket[i].clear(); 
     } 
     digitPosition *= 10; 
     p+=1; 
    } 
} 

EDIT1：

在這裏，我們有10個mybuckets向量他們每個人將持有基於十進制的第K至少顯著輸入數字號碼。其中k將從1到N（給定輸入中的最大位數）變化。

e.g. 
for k = 2 
and a = [1,23,45,127,345,1] 
mybucket[0] = [1,1] 
mybucket[2] = [23,127] 
mybucket[4] = [45,345] 

以上代碼的作用是從輸入中提取第K個最低有效位，並在每次迭代中放入相應的桶中。處理完所有數字後，我們從mybuckets中取出這些數字，並將其放回到輸入數組中，並以（K + 1）個最小有效數字開始處理。我們繼續這樣做，直到給定輸入數字中沒有剩餘的最少有效數字。

注：此過程將在給定的輸入號碼

e.g. a = [83,86,77,15,93,35,86,92,49,21,62,27,90,59,63,26,40,26,72,36,93] 
Iteration1 
Bucket9[49,59,] 
Bucket8[] 
Bucket7[77,27,] 
Bucket6[86,86,26,26,36,] 
Bucket5[15,35,] 
Bucket4[] 
Bucket3[83,93,63,] 
Bucket2[92,62,72,] 
Bucket1[21,] 
Bucket0[90,40,] 

Iteration2 
Bucket9[93,92,90,] 
Bucket8[86,86,83,] 
Bucket7[77,72,] 
Bucket6[63,62,] 
Bucket5[59,] 
Bucket4[49,40,] 
Bucket3[36,35,] 
Bucket2[27,26,26,21,] 
Bucket1[15,] 
Bucket0[] 
O/P: 
[93,92,90,86,86,83,77,72,63,62,59,49,40,36,35,27,26,26,21,15] 

數字時間最大數量運行正如我們的最大位數爲2所以這個運行了2次迭代。

檢查Radix sort in descending order的工作代碼。

編輯2/3：
您只能使用任何數據結構，我們必須關心的是插入相應的存儲區並從存儲區中檢索。在這裏，我們需要遵循一個嚴格的規則來插入和刪除桶中的其他內容，否則，您可能會以隨機順序獲得o/p。

Algorithm: (Assuming only positive number(s) is/are as given input) 
k <- 1 
maxVal <- 0 
foreach number from inputs: 
    maxVal = max(number , maxVal) 

/*Collection of bucket, which will hold all 
the numbers whose kth significant digit is d[0-9].*/ 
buckets[ ] 
1. foreach number from inputs: 
    d <- k_th_least_significant(number, k) 
    buckets[ d ] .insert (number) 
2. count <- 1 
    for indx = maximum bucket index to lowest bucket index: 
     for j = 1 to j <= buckets[ indx ].size(): 
      inputs[ count ] = buckets[ indx ][ j ] 
      count <- count + 1 
3. k <- k + 1 
4. if number_of_digit(maxVal) <= k : 
    go to step 1 
5. Print inputs 

其他方式來實現這一點。

1. 鏈表
   一個）2維鏈表
   b）中的1維鏈表陣列
   

2. 陣列動態大小1-d陣列
   B的
   一個）陣列）2- D）動態陣列（我們必須處理陣列的大小調整）
   c）使用最大尺寸陣列（1-D或2-D）
   d）來自標準庫的陣列
   

3. 從STL地圖或實現自己的使用[0-9]作爲鍵和值作爲
   一）鏈表
   B）向量或數組指針（你可能要應對插入）
   

4. 散列使用桶概念（其中關鍵將是整數[0-9]，你必須多值映射到相同的散列密鑰）

5. 隊列（2- d隊列或1-d隊列）

等等