Javaを使用して0、1、2の配列をソートする

0、1、2 で構成される配列が与えられた場合、すべての 0 が 1 の前に来て、すべての 2 が最後に来るように要素を並べ替えます。配列のすべての要素をその場で並べ替える必要があります。

DNF (オランダ国旗) 並べ替えアルゴリズムを使用して、この問題を解決できます。たとえば、

Input-1 -

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

Output -

0 0 1 1 2 2

説明 - 使用しますDNF ソート アルゴリズムは、0、1、2 を含む指定された配列をソートし、{0,0,1,1,2,2} として出力します。

Input-2 −

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

Output -

0 0 1 1 1 1 2

説明 − 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 中国語 Web サイトの他の関連記事を参照してください。