[Java][LeetCode][Sort] Sort Color #75

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Example 1:

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

原本用雙指針同向一個一個比較，依0->1->2順序排序，但這樣跑出來是O(n²)，於是換用雙指針反向。如果把陣列分成三個區塊(0,1,2)，因為要把0放在最左邊，所以當nums[index]=0的時候，將nums[left]與nums[index]交換，就能將0移到前面。因為要把1放在中間區塊，所以當nums[index]=1的時候，只把指針指到下一個位置就好。因為要把2放到後面的區塊，所以當nums[index]=2，則把當前這個數字放到右指針的地方。直到當前位置與右指針交錯之後。

I used the same direction of two pointers first (bubble sort). The order is 0->1->2. but that method’s time complicate is O(n²). Then I change my method to reverse two pointers. I separated arrays for three blocks. The left is 0, the middle is 1, and the right is 2. When nums[index]=0, it’s mean, I need to fill out to the left block When nums[index]=2, I need to fill out the right block. When nums[index]=1, just only move the index pointer to the next. Until the index pointer cross with the right pointer.