题目对应LeetCode官网地址：75. 颜色分类
Java实现代码：
package array;
import java.util.Arrays;
/**
* @ClassName LeetCode 75.颜色分类
* @Description https://leetcode.cn/problems/sort-colors/
* @Author Jiangnan Cui
* @Date 2022/10/30 19:58
* @Version 1.0
*/
public class LeetCode75 {
/**
* @MethodName sortColors
* @Description 方法1：双层for循环
* 时间复杂度：O(n)
* 空间复杂度：O(k)，其中k为元素范围，此题中k=3，可看做O(1)
* 满足题目要求，但需要进行两次循环
* @Author Jiangnan Cui
* @Date 21:12 2022/10/30
*/
public void sortColors(int[] nums){
// 新建数组分别对0、1、2计数，初始每个元素个数为0
int[] count = {0,0,0};
// 遍历数组
for (int i = 0; i < nums.length; i++) {
// 避免出现0、1、2以为的数字，导致数组下标越界
assert nums[i]>=0 && nums[i]<=2;
// 对nums[i]分别计数，例：num[i]=0、count[nums[i]]++ =count[0]++，即对count[0]进行累加操作
count[nums[i]]++;
}
// 将0、1、2分别放回原数组
int index = 0;
for (int i = 0; i < count[0]; i++) {
nums[index++] = 0;
}
for (int i = 0; i < count[1]; i++) {
nums[index++] = 1;
}
for (int i = 0; i < count[2]; i++) {
nums[index++] = 2;
}
}
/**
* @MethodName sortColors2
* @Description 方法2：三路快速排序
* 时间复杂度：O(n)
* 空间复杂度：O(1)
* 满足题目要求
* @Author Jiangnan Cui
* @Date 21:20 2022/10/30
*/
public void sortColors2(int[] nums){
// -1, [0,...,zero,...,two,...,nums.length-1], nums.length
// -1 [ 0元素区间 ] [ 1元素区间 ] [ 带遍历元素区间 ] [ 2元素区间 ] nums.length
// nums[0,...,zero]==0
int zero = -1;
// nums[two,...,nums.length-1]==2
int two = nums.length;
for (int i = 0; i < two;) {
if(nums[i] == 1){
// 遍历的元素==1时，i直接加1向右移动即可
i++;
}else if(nums[i] == 0){
// 遍历的元素==0时，与数组0区间范围对应的下一个元素作交换，即zero区间长度向右移动一位长度+1，同时zero的大小也要加1，因此用++zero，由于交换过来的0占据了1元素的位置，此时交换后的元素1不需要再判断，所以需要i++，注意zero++与++two的区别
swap(nums, ++zero, i++);
}else if(nums[i] == 2){
// 遍历的元素==2时，与数组2区间范围对应的前一个元素作交换，即two区间长度向左移动一位长度+1，同时two的大小也要减1，因此用--two，交换后的元素还需要再进行判断，所以此处不用改变位置，即不用i++，注意two--与--two的区别
swap(nums, --two, i);
}
}
}
/**
* @MethodName swap
* @Description 交换数组中两个元素的位置
* @param: nums
* @param: i
* @param: j
* @Author Jiangnan Cui
* @Date 21:20 2022/10/30
*/
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] nums = {2,2,2,1,1,0};
new LeetCode75().sortColors(nums);
System.out.println(Arrays.toString(nums));
int[] nums2 = {2,2,2,1,1,0};
new LeetCode75().sortColors2(nums2);
System.out.println(Arrays.toString(nums2));
}
}
输出结果：
[0, 1, 1, 2, 2, 2] [0, 1, 1, 2, 2, 2]