數組排序有效

對於作業分配，我需要編寫可對數組進行排序的方法，排序方法應儘可能高效。數組排序有效

數組的開頭將顯示除以4而不餘數的所有數字。
之後，將所有的4具有1
之後，將所有的4具有2
剩餘劃分在陣列端部的數量剩餘劃分號碼將所有其他的數字（與其餘三個相除的那些）。

我嘗試這樣設定4個指針：
2指針在0第一剩餘部分和1個
2指針在最後陣列的對的2其餘部分和3

這是我可以找到迄今（當然有問題），我感謝你的幫助！

public static void sortByFour (int[] arr) 
{ 
    int temp; 
    int noRemainderIndex = 0; 
    int remainder1Index = 1; 
    int remainder2Index = arr.length - 2; 
    int remainder3Index = arr.length - 1; 

    for (int i = 0; i < arr.length; i++) 
    { 
     if (arr[i] % 4 == 0) 
     { 
      temp = arr[noRemainderIndex]; 
      arr[noRemainderIndex] = arr[i]; 
      arr[i] = temp; 
      noRemainderIndex++; 
      remainder1Index++; 
     } 
     else if (arr[i] % 4 == 1) 
     { 
      temp = arr[remainder1Index]; 
      arr[remainder1Index] = arr[i]; 
      arr[i] = temp; 
      remainder1Index++; 
     } 
     else if (arr[i] % 4 == 2) 
     { 
      temp = arr[remainder2Index]; 
      arr[remainder2Index] = arr[i]; 
      arr[i] = temp; 
      remainder2Index--; 
     } 
     else if (arr[i] % 4 == 3) 
     { 
      temp = arr[remainder3Index]; 
      arr[remainder3Index] = temp = arr[i]; 
      arr[i] = temp; 
      remainder3Index--; 
      remainder2Index--; 
     } 
    }

來源

2012-05-26 Dana Yeger

數字之間的順序除了4之外還有相同的餘數？ – nhahtdh

你被允許使用'Array.sort'方法嗎？ –

不需要組織它們 –

我想你想類似於分區快速排序算法使用的東西。

4個指針是一個好的開始，但是讓我改變它們的功能：
1）指向剩餘部分的端部= 0
2）指向剩餘部分的端部= 1
3）指向端餘數= 2
4）指向未分類的開始

該數組分爲5個部分：餘數= 0,1,2,3和未分類。

如果餘數= 3，則只增加指針4.如果餘數= 3組，則包含數字。
如果餘數= 2，則增加指針3並將當前值與指針3處的值交換。增量指針4.
如果餘數= 1，則增加指針2，與當前值交換;增加指針3，交換當前值。增量指針4.
如果餘數= 0，那麼交換3次。

來源

2012-05-26 16:20:04 nhahtdh

我認爲一個更好的方法來做到這一點將有4個數組，每個案件一個。將每個數組視爲一個隊列。遍歷數組並推入相應的數組。一旦完成，只需將數組附加到對方。非常乾淨的解決方案。

來源

2012-05-26 16:03:28

如果我想使用更多的數組我需要計算的複雜性，因爲它應該是有效的 –

空間或時間複雜性？ –

提示您的功課。

如果你被允許使用現有的庫方法，看看Array.sort(...)和Comparator接口。（注意到排序基本類型的陣列，當使用自定義的比較器，必須轉換到包裝型的第一;例如轉換int[]到Integer[]，排序和轉換回。）
如果不允許要使用Array.sort(...)（或類似），找出這是排序問題還是整理問題。換句話說，如果有任何要求重新排序（或保留）4個類別中的數字的順序。
您可以通過使用4個臨時數組來簡化問題，但還有其他（更棘手的）解決方案涉及在數組中進行多次傳遞並交換元素對。
需要解決的問題之一是，您事先並不知道4個類別中每個類別有多少個數字。所以你事先不知道移動號碼的目的地。但也有解決這個...

...排序方法應該是儘可能高效。

這是作業要求，還是您的要求？

如果這是你自己加入的東西 - 當心 - 您的標記可能給分數高的比（據說）更有效，但過於複雜的解決方案的簡單解決方案。

一位優秀的軟件工程師並不追求每個程序的最終效率。相反，他平衡了各種各樣的事情：

功能要求，性能
要求，對軟件的可維護性
要求，並
項目的最後期限，

提的是，其中的一些要求可能是暗示的，和/或管理層沒有正確理解。

（或換句話說，一個程序很快......但是不能可靠地工作，或者不可維護，或者沒有及時準備好...是一個失敗。）

另一方面，如果性能是此作業練習的要求，那麼您的講師應該已經解釋瞭如何使用Java測量小程序的性能。（請相信我......這不是一件簡單的事情。）您需要將此應用於您的作業問題，以確定哪種替代解決方案最快。

來源

2012-05-26 16:03:54

但請注意，比較器只能比較對象。 int []數組必須轉換爲Integer []，排序並轉換回int []。 –

爲什麼不創建一個自定義類，它包含兩個值，即數字和其餘部分。創建一個這個迷你班的數組，傳遞數值並預先計算出你的餘數。這將幫助您在每次通過列表元素時不必重新計算餘數。您必須根據剩餘屬性移動和排序元素。

然後，你有一個經典的排序列表只有幾個獨特的元素的問題。您選擇的排序算法的性能取決於初始條件。我可能會說最好的選擇是Shell排序算法或Quick3。

http://www.sorting-algorithms.com/few-unique-keys

來源

2012-05-26 16:15:24

不確定是否僅實例化一個類才能避免少數模計算會更高效。 –

數組排序有效

回答

相關問題