本文共 1706 字，大约阅读时间需要 5 分钟。

一. 题目描述

给定一个包含红色、白色和蓝色元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。其中，0 represents红色，1 represents白色，2 represents蓝色。

示例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]

二. 问题分析

1）统计法：首先遍历数组，统计每个数字出现的次数，然后根据顺序重新赋值。这是一种常用的解法，适用于需要排序的多个元素场景。

2. 双指针法：使用两个指针分别指向数组的首尾，用i遍历数组。当遇到0，与首指针交换，同时首指针向右移动；遇到2，与尾指针交换，尾指针向左移动；遇到1，直接向后移动i。这是一种高效的排列算法，特别适合需要在原地排序且空间因素有限的情况。

---

三. 代码

方法1：统计法

public class Solution {
    public void sortColors(int[] nums) {
        int[] counts = new int[3];
        for (int i : nums) {
            counts[i]++;
        }
        int count0 = counts[0];
        int count1 = counts[1];
        int count2 = counts[2];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (index < count0) {
                nums[i] = 0;
                index++;
            } else if (index < count0 + count1) {
                nums[i] = 1;
                index++;
            } else {
                nums[i] = 2;
            }
        }
    }
}

方法2：双指针法

public class Solution {
    public void sortColors(int[] nums) {
        int left = -1, right = nums.length;
        int i = 0;
        while (i < nums.length) {
            if (nums[i] == 0) {
                swap(nums, left, i);
                left++;
            } else if (nums[i] == 2) {
                swap(nums, right, i);
                right--;
            } else {
                i++;
            }
        }
    }
    private void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

---

四. 总结

本题要求原地对数组进行排序，确保相同颜色的元素相邻，按照颜色顺序排列。统计法简单易实现，适合需要额外空间的场景；而双指针法能在原地完成排序，适合资源有限的应用场景。