题目描述:
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
代码:
思路分析:
其实这题最暴力的算法就是直接用api排序QAQ。不过真的太简单粗暴了。
这题主要是想考察快排的思想。比某个数小的在左边,等于某个数的在中间,大于某个数的在右边。还主要考察了“循环不变量”的思想。
1、要划分为三个区间
[0,zero)对应0
[zero,i)对应1
[two,len-1]对应2
所以需要定义三个指针zero,i(也就是one),two分别对应着0区间的右边界、1区间的右边界、2区间的左边界。可见从这个区间定义知道当i==two的时候循环停止。
2、为了保证初始化的时候 [0, zero) 为空,设置 zero = 0,所以要先交换再加加
3、为了保证初始化的时候 [two, len - 1] 为空,设置 two = len,所以要先减减再交换
class Solution {
public void sortColors(int[] nums) {
int len = nums.length;
if(len < 2){
return;
}
int zero = 0;
int i = 0;
int two = len;
while(i < two){
if(nums[i] == 0){
swap(nums,i,zero);
i++;
zero++;
}else if(nums[i] == 1){
i++;
}else{
two--;
swap(nums,i,two);
}
}
}
public void swap(int[] nums,int index1,int index2){
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
}