首页 > 文章列表 > 使用Java对一个由0、1和2组成的数组进行排序

使用Java对一个由0、1和2组成的数组进行排序

java 数组 排序
347 2023-08-25

给定一个由 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