用4個選項對數組進行排序的算法

Question

我被賦予了一個任務來排序填充（非負）整數的數組。

他們應該被排序，使得輸出是按以下順序：

• 編號，其中它們中的除以4的餘數是0
• 編號，其中它們中的除以4的餘數是1
• 號碼，其中它們中的除以4的餘數是2個
• 編號，其中它們中的除以4的餘數是3

我試圖寫一個簡單的算法，應該在O（n）工作（任務是有效地編寫代碼）。

但我認爲這是一團糟，有幾個案例不起作用（例如，當我嘗試一個數組，其中前幾個數字剩餘3）。

任何有關如何解決這個問題的建議或更好的方法？

public static void sortByFour(int[] arr) 
{ 
    int zeroR = -1, oneR = 0, twoR = arr.length-1, threeR = arr.length; 

    do 
    { 
     if (arr[oneR]%4==1) 
     oneR++; 
     else if (arr[oneR]%4==0) 
     { 
      zeroR++; 
      int temp = arr[oneR]; 
      arr[oneR] = arr[zeroR]; 
      arr[zeroR] = temp; 
      oneR++; 
     } 
     else if (arr[oneR]%4==2) 
     { 
      twoR--; 
      int temp = arr[oneR]; 
      arr[oneR] = arr[twoR]; 
      arr[twoR] = temp; 
     } 
     else if (arr[oneR]%4==3) 
     { 
      threeR--; 
      int temp = arr[oneR]; 
      arr[oneR] = arr[threeR]; 
      arr[threeR] = temp; 
     } 
    } while (oneR < threeR && oneR < twoR); 
} 

Answer 1

A bucket sort可以爲你做詭計。請注意，您可以通過（每個提醒一次）循環4次，像（類似Java的僞代碼）克服桶排序的O(n)額外的空間因素：

final int REMINDER = 4; //4 because you use %4 
int curr = -1; 
for (int r = 0; r < REMINDER ; r++) { 
    for (int i = curr + 1; i < arr.length; i++) { 
     if (arr[i] % REMINDER == r) { 
      //swap elements: 
      int temp = arr[i];; 
      arr[i] = arr[++curr]; 
      arr[curr] = temp; 
     } 
    } 
} 

的想法是「記住」在這裏你有最後一個元素，迭代數組4次，並將具有匹配提醒的元素交換到期望的位置（您記得）。

複雜性仍然是O(n)與O(1)額外的空間。

一種替代方法是O(n)（但好得多的常量）的時間與O(n)空間是根據所期望的提醒在4名不同的列表來使用經典桶排序，以單道次存儲中的所有元素，並以第2次 - 上這4個列表，按照所需順序填充原始數組。