来源Leetcode第75题颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
库函数
直接调用库函数Arrays.sort(nums);就完事了
2次遍历
一次遍历先统计3个球的总数，二次遍历重写数组
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public void sortColors(int[] nums) {
if (nums.length == 0)
return;
int nums0 = 0,nums1 = 0,nums2 = 0;
for(int i = 0 ; i < nums.length ; i ++){
if(nums[i] == 0)
nums0++;
else if(nums[i] == 1)
nums1++;
else if(nums[i] == 2)
nums2++;
}
nums1 += nums0;
nums2 += nums1;
for(int i = 0 ; i < nums.length ; i++){
if(i < nums0)
nums[i] = 0;
else if(i < nums1)
nums[i] = 1;
else
nums[i] = 2;
}
}
双指针
用三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。
沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。
- 初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
- 初始化2的最左边界 ：p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.
- 初始化当前考虑的元素序号 ：curr = 0.
- While curr <= p2 :
- 若 nums[curr] = 0 ：交换第 curr个 和 第p0个 元素，并将指针都向右移。
- 若 nums[curr] = 2 ：交换第 curr个和第 p2个元素，并将 p2指针左移 。
- 若 nums[curr] = 1 ：将指针curr右移。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 public void sortColors(int[] nums) {
if (nums.length == 0)
return;
int p0 = 0;
//0的边界指针
int p2 = nums.length-1;
//2的边界指针
int cur = 0;
//当前数组指针
while(cur <= p2){
//3种交换情况
if(nums[cur] == 0){
int tmp = nums[p0];
nums[p0++] = nums[cur];
nums[cur++] = tmp;
}else if(nums[cur] == 2){
int tmp = nums[p2];
nums[p2--] = nums[cur];
nums[cur] = tmp;
}else{
cur++;
}
}
}