颜色分类

描述

力扣第 75 题。给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

示例3:

输入：nums = [0]
输出：[0]

示例4:

输入：nums = [1]
输出：[1]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

思路

该题虽然是一个场景题目，实际上抛开该场景，就是对一个数组进行排序。数组里面的元素为 0，1，2。它们的顺序是乱的，需要按照 0，1，2 的方式输出。我们可以考虑使用冒泡排序法来将数组数据排序,冒泡排序的基本思路是将数组中的两个相邻的数据进行比较，如果两个元素反序，就将两个元素换位置，直到遍历到最后没有反序为止。它就像鱼吐泡泡一样，每次得到最大值。

我们以示例1为实例来进行判断，如下：

第一轮排序的时候顺序如下：

1. 2 和 0 比较，2 比 0 大，需要和 0 换位置。

2. 2 和 2 比较，2 和 2 相等，所以不需要换位置。

3. 2 和 1 比较，由于 2 比 1 大，需要将 2 和 1 换位置

4. 2 继续和 1 比较，2 比 1 大，将 2 和 1 交换位置

5. 将 2 和 0 比较，2 比 0 大，所以将 2 和 0 交换位置

第一轮遍历全部完成，得到如下结果：

剩下的元素按照上面的流程进行比较，得到如下结果：

代码具体实现

Java语言版本

class Solution {
    public void sortColors(int[] nums) {
        for(int i = 0;i< nums.length - 1 ;i++){
            boolean isSorted = true;
            for(int j =0;j<nums.length - i - 1;j++){
                int tmp = 0;
                if(nums[j] > nums[j + 1]){
                    tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j+1] = tmp;
                    isSorted = false;
                }
            }
            if(isSorted){
                break;
            }
        }
    }
}

Go语言版本

func sortColors(nums []int)  {
    for i := 0;i< len(nums) - 1 ;i++ {
            isSorted := true;
            for j := 0;j<len(nums) - i - 1;j++ {
                tmp := 0
                if nums[j] > nums[j + 1] {
                    tmp = nums[j]
                    nums[j] = nums[j + 1]
                    nums[j+1] = tmp
                    isSorted = false
                }
            }
            if(isSorted){
                break
            }
        }
}