这道题断断续续想了好长时间。今天看说这个要用two points做。所以尝试做了一下。
我的想法是先把0都移到数组的前面。然后再把1都移到2的前面。
首先用一个指针first，我们要做到的是first之前的元素都是0. 还有一个扫描指针end，用来扫描数组并交换元素。
在first到end之间不会有0出现，因为在end扫描的时候已经把0元素交换到first之前了。。。
1 public static void sortColors(int[] A) { 2 int first = 0, end = 0; 3 for (; end<A.length;) { 4 if (A[end] == 0 && A[first] != 0) { 5 //there is A[first] is not 0 and A[end] is 0, so exchange with each other 6 int tmp = A[first]; 7 A[first++] = 0; 8 A[end++] = tmp; 9 } 10 else if (A[first] == 0) { 11 //this condition only happens when that first several elements are 0.(end == first) 12 //because if end > first the element between first and end cannot be 0; 13 //this can be proved by induction or it is easy to see. 14 first++; 15 end++; 16 } 17 else { 18 //A[first] is not 0 and we need to change it with a 0. But A[end] is not 0 19 //so we need to move end to find a 0; 20 end++; 21 } 22 } 23 for (end = first;end<A.length;) { 24 if (A[end] == 1 && A[first] != 1) { 25 int tmp = A[first]; 26 A[first++] = 1; 27 A[end++] = tmp; 28 } 29 else if (A[first] == 1) { 30 first++; 31 end++; 32 } 33 else { 34 end++; 35 } 36 } 37 }
后来一种更好的方法是用三个指针。一个指针i，一个指针j，一个current。在i之前的都是0，在j之后的都是2，current是扫描指针。
如果A[cur]为0 就和A[i]交换。因为在i和current之间只能有1，所以这个时候A[i]一定是1，所以交换后i、current都移向下一个位置。
如果A[cur]为2，就和A[j]交换，但是我们只能移动j，不能移动cur，因为我们无法确认A[cur]现在的值。可能是0,1,2，如果是1可以继续进行，如果是0就要和A[i]交换，如果是2要和A[j]交换。。。
1 public static void swap(int[] A, int i, int j) { 2 int tmp = A[i]; 3 A[i] = A[j]; 4 A[j] = tmp; 5 } 6 7 public static void sortColors1(int[] A) { 8 int i=0, j=A.length-1, cur=0; 9 while(cur<=j) { 10 if (A[cur] == 0) { 11 swap(A, i, cur); 12 i++; 13 cur++; 14 } 15 else if (A[cur] == 2) { 16 swap(A, cur, j); 17 j--; 18 } 19 else cur++; 20 } 21 }