題目說明：給一個陣列，陣列中數字0代表紅色、數字1代表白色、數字2代表藍色，要依照數字的大小(也就是顏色要依照紅白藍的規則)進行排序，並且排序要就地(in place)排序且不能使用程式語言中的函示庫

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

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

解題思路：原本的題目敘述落落長，其實就是要你排序而已。排序有非常多種方式，這次解題時都是比較簡單的排序方式。以下會逐一介紹常見的三種排序方式
1.Bubble sort
運用陣列中相鄰元素之間兩兩交換的方式進行排序，這樣講可能有些抽象，我們直接舉一個例子來說明:
有一個矩陣{5,1,4,2,8}
1st iteration:
(1)從頭開始(第0個)，5>1，兩個交換，於是陣列變成了{1,5,4,2,8}
(2)由於5又>4，因此再次交換，陣列變成了{1,4,5,2,8}
(3)5>2，再次交換，陣列變成了{1,4,2,5,8}
(4)因為5<8，不用交換，陣列維持不變，{1,4,2,5,8}

2nd iteration
(1)從矩陣的第一個開始(4)，4>2，交換，陣列變成{1,2,4,5,8}，由於已經從小排到大，結束排序

時間複雜度:O(n^2)，當資料很大時不適合使用，因為不斷地交換十分耗時

Pseudo code

bubbleSort(array){
for(int i=0;i<array.length;i++){
    for(int j=i+1;j<array.length-i;j++){
        if(array[j]<array[i]){
            swap(array[j],array[i])
        }
    }
}
}

附上一張gif來幫助了解bubble sort的機制

2.Selection sort
重複在尚未排序的數列當中找到最小值並進行交換，同樣以{5,1,4,2,8}為例
1st iteration
從頭(5)開始，剛好剩下四個最小的就是在5旁邊的1，直接進行交換，陣列變成{1,5,4,2,8}

2nd iteration
從陣列的第一個(5)開始，剩下三個中最小的是2，進行交換後陣列變成{1,2,4,5,8}，已經由小排到大，無需排序

Pseudo code

selectionSort(array){
    for(int i=0;i<array.length;i++){
        min=i
        for(int j=i+1;j<array.length;j++){
            if(array[min]>array[j]){
                min=j
            }
        }
        if(min!=i){
            swap(array[min],array[i])
        }
    }
}

時間複雜度:O(n^2)

同樣附上一張gif幫助理解

3.insertion sort
就跟我們打牌很像，將拿到的新牌插入到已經排序好的牌組。同樣以{5,1,4,2,8}為例
1st iteration
5

2nd iteration
1<5，因此插入到5前面，變成{1,5}

3rd iteration
4要插入到{1,5}的陣列裡面，變成{1,4,5}

4th iteration
2要插入到{1,4,5}的陣列裡面，變成{1,2,4,5}

5th iteration
8要插入到{1,2,4,5}的陣列裡面，變成{1,2,4,5,8}

Pseudo code

insertionSort(array){
    for(int i=1;i<array.length;i++){
        x=array[i]
        j=i-1
        while (j>=0&&array[j]>x){
            array[j+1]=array[j]
            j-=1
        }
        array[j+1]=x
    }
}

時間複雜度:O(n^2)

同樣附上一張gif幫助理解

這題可以從這三種隨便挑一個進行排序即可，附上程式碼

Java

class Solution {
    public void sortColors(int[] nums) {
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]>nums[j]){
                    int temp=nums[j];
                    nums[j]=nums[i];
                    nums[i]=temp;
                }
            }
        }
    }
}//使用bubble sort

Python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)):
            min_idx = i
            for j in range(i+1, len(nums)):
                if nums[j] < nums[min_idx]:
                    min_idx = j
            if min_idx != i:
                nums[i], nums[min_idx] = nums[min_idx], nums[i]
        #使用selection sort