使用Java對一個由0、1和2組成的陣列進行排序

給定一個由 0、1 和 2 組成的數組，依序對元素進行排序，使所有 0 排在 1 之前，所有 2 排在最後。我們必須對數組的所有元素進行就地排序。

我們可以使用 DNF（荷蘭國旗）排序演算法來解決這個問題。例如，

Input-1 -

arr[ ]= {2,0,0,1,2,1 }

#輸出 -

0 0 1 1 2 2

Explanation − 使用DNF排序演算法對給定的包含0、1和2的陣列進行排序，它將輸出為{0,0,1,1,2,2}。

Input-2 −

arr[ ] = {0,1,1,2,1,1,0}

輸出 -

0 0 1 1 1 1 2

Explanation − 使用DNF排序演算法對給定的包含0、1和2的元素數組進行排序，它將輸出為{0,0,1,1,1,1,2}。

解決這個問題的方法

在給定的0、1和2的陣列中，我們可以使用DNF排序演算法。

DNF排序演算法 − 此演算法需要3個指標來遍歷整個數組，並交換必要的元素。

• 在數組的開頭建立一個低指針，並建立一個指向數組末尾的高指針。

• 找到數組的中點，並建立一個中指針，它從數組的開頭迭代到末尾。

• 如果陣列的中指標為'0'，則交換指向低指標的元素。增加低指針和中指針。

• 如果陣列的中指標為'2'，則將其與指向高指標的元素交換。增加中指針並減少高指針。

• 如果陣列的中指標為'1'，則增加中指標。

範例

 示範

public class Solution {
   public static void binarySorting(int arr[], int n){
      int low=0;
      int high= n-1;
      int mid=0;
      while(mid<=high){
         if(arr[mid]==0){
            int temp= arr[mid];
            arr[mid]= arr[low];
            arr[low]= temp;
            mid++;
            low++;
         }
         if(arr[mid]==1){
            mid++;
         }
         if(arr[mid]==2){
            int temp= arr[mid];
            arr[mid]= arr[high];
            arr[high]= temp;
            high--;
         }
      }
   }
   public static void print(int arr[], int n){
      for (int i = 0; i < n; i++)
         System.out.print(arr[i] +" ");
   }
   public static void main(String[] args){
      int arr[] ={ 0,0,1,0,1,0,1,2,2};
      int n = arr.length;
      binarySorting(arr, n);
      print(arr, n);
   }
}

#輸出

執行上述程式碼將產生下列輸出：

0 0 0 0 1 1 1 1 2

以上是使用Java對一個由0、1和2組成的陣列進行排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！