对 0s、1s 和 2s 的数组进行排序

Question

给定一个只包含零、一和二的数组。编写一个函数来按O(n)时间复杂度对给定数组进行排序。

Input :
[1, 2, 2, 0, 0, 1, 2, 2, 1]
Output :
[0, 0, 1, 1, 1, 2, 2, 2, 2]
[0, 0, 1, 1, 1, 2, 2, 2, 2]

Answer 1

方法 – I ：
解决这个问题的一个非常基本的方法是保持给定数组中零、一和二的数量的计数，然后根据每个数字的频率操作给定的数组。这种方法有点受计数排序的启发。无论该特定索引的初始值是什么，我们首先将数组中的所有零从索引零开始放入，然后放入所有的 1，然后放入所有的 2。

步骤：
1.) 遍历给定数组一次并不断增加遇到的数字的计数。
2.) 现在再次从索引零开始遍历数组，并不断更改当前索引上元素的值，首先耗尽所有零，然后是 1，最后是所有 2。

这样我们就有了一个排序的数组，其中所有的零都在开始，然后是所有的 1，然后在最后一节中，我们在时间复杂度为. O(n)

但这种方法的主要缺点是，我们必须遍历给定数组两次以计算零、一和二的数量，第二次遍历数组以对其进行排序，这只能在一次通过中完成。

  package Arrays;

    public class sort012 {

    public static void main(String[] args) {

        int[]a = {1,0,2,0,0,1,2,2,1};
        sort(a);
        for(int val : a)
        {
            System.out.println(val + " ");
        }

    }
    /*Function to sort the given array*/
    public static void sort(int[]a)
    {
        /* array to keep the count of 0s, 1s, 2s*/
        int[]freq = new int[3];

        /* traverse the given array for filling the
         * frequency array*/
        for(int val : a)
        {
            freq[val]++;
        }
        /*pointer to traverse the given array again*/
        int pointer = 0;
        for(int i=0;i<freq.length;i++)
        {
            /* loop to exhaust the number of 0s, 1s, 2s*/
            while(freq[i]-->0)
            {
                /*at the current pointer plot the current number*/ 
                a[pointer]=i;
                /*increment the pointer*/
                pointer++;
            }
        }
    }

方法 – II ：
这种算法被称为Dutch national flag algorithm 或 Three way partitioning其中相似类型的元素被分组在一起，并且它们的集合组也以正确的顺序排序。
现在我们有三种类型的元素要排序，因此，我们将给定的数组分为四个部分，其中 3 个部分被指定为zeroes，Ones和twos分别有一个部分是unknown或留下待探索的部分。现在为了遍历这些部分，我们还需要 3 个指针，它们实际上将给定的数组分成四段。
让我们将这些指针命名为低、中和高。
现在我们可以分辨出这些段的起点和终点。

Segment-1 : zeroes
这将是一个已知部分，仅zeroes包含范围为[0, low-1].
Segment-2: Ones
这也是一个知道部分，只包含范围为 的部分[low, mid-1]。
Segment-3 : Unexplored
这将是一个未知部分，因为该部分中的元素尚待探索，因此它可以包含所有类型的元素，即零、一和二。该段的范围将是[mid, high]
Segment-4：Twos
这将是最后一个已知区域，只包含范围为[high+1, N]N 是给定数组的长度或基本上给定数组的最后一个有效索引的二进制数。
此算法中用于在单次传递中对给定数组进行排序的步骤：

（I）初始化低，中，高指针，low = 0，mid = 0，high = N
（II）现在，运行一个循环并执行以下操作，直到mid指针最终满足highpointer.As的mid指针向前移动，我们一直把该元素的mid指针，它的正确位置通过将该元素与相应部分的指针处的元素交换。
（ⅲ）CASE - I：如果在所述元素mid，也就是A[mid] ==0，此装置该元件的正确位置在上述范围内[0,low-1]，因此，我们交换A[mid]与A[low] 和增量低确保元件与指数大于低较小是零。
(iv) CASE – II：如果元素在mid，即，A[mid]==2，此手段该元件的正确位置在上述范围内[hi+1, N]，因此，我们交换A[mid]与A[hi]和递减高确保具有指数大于高元件是一个两决策。
(v) CASE – III ：如果元素在中间，即A[mid]=1，这意味着该元素已经在它的正确段中，因为它[low, mid-1]是它需要的范围。因此，我们什么都不做，只是简单地增加中间指针。

所以，总共有三种情况，让我们花点时间强调一个事实，即中指针仅在元素A[mid] == 1.
让我们单独讨论每个案例，

对于情况-我 ：在这种情况下，我们增加mid以及随着增量low指针，因为我们相信，在交换前低指针元素可以肯定只有一个因为它当时两个，就已经得到了交换与high指针，当mid指针探索它作为中指针离开它的唯一原因，因为它是一个。

对于情况- II：现在，在这种情况下，我们交换位置的元素mid和high，但与案例-我，在这种情况下，我们不知道它会在元素mid在交换的元素之后指数high索引之前交换可以是任何零，一或两个，因此，我们需要探索这个交换的元素，因此mid在这种情况下我们不增加指针。

对于情况 – III：mid在这种情况下，正如已经讨论过的那样，关于递增没有混淆，因为我们知道元素 atmid是 1，因此我们肯定需要在这里递增 mid。

该算法的时间复杂度也是O(n)，但它只需一次遍历即可对数组进行排序，并且与以前的方法不同，没有任何额外的空间。

  package Arrays;

    public class sort012 {

    public static void main(String[] args) {

        int[]a = {1,2,2,0,0,1,2,2,1};
        sort(a);
        for(int val : a)
        {
            System.out.print(val + " ");
        }

    }

    public static void sort(int[]a)
    {
        /* Three pointers to divide the array in designated segments
         * as discussed in the post*/
        int low=0,mid=0,high=a.length-1;
        while(mid<=high)
        {
            /* Case - 1, when element at mid pointer is zero,
             * swap with element at low*/
            if(a[mid]==0)
            {
                a[low]=swap(a[mid], a[mid]=a[low]);
                /* Increment low as well as mid, as we know
                 * the swapped element at mid is a one*/
                low++;
                mid++;
            }
            /* Case - 1, when element at mid pointer is two,
             * swap with element at high*/
            else if(a[mid]==2)
            {
                /* decrement only high and keep mid unchanged, as
                 * we do not know anything about the swapped element
                 * at mid*/
                a[high]=swap(a[mid],a[mid]=a[high]);
                high--;
            }
            else {
                /*Case - 3, when element at mid pointer is one*/
                /*do nothing, and increment mid pointer*/
                mid++;
            }

        }
    }

    /* utility swap function*/
    public static int swap(int i, int j)
    {
        return i;
    }
}

那是关于对 0、1 和 2 的数组进行排序。