通过交换，对0，1，2排序
使用三个标记［循环不变式］
i从前向后，记录最后一个0的位置
j从后向前，记录第一个2的位置
k从前向后，是遍历用的游标
[0..i-1]是0
[i..k-1]是1
[k,j-1]是未探测
[j..n-1]是2
初始k=0时，0，1，2的区域都是空，所有区域都是未探测，循环k=0..n-1
如果a[k] = 0=>swap(a[i++], a[k])
如果a[k] = 1=>无操作
如果a[k] = 2=>swap(a[--j], a[k--])
复杂度O(n)
1 class Solution{ 2 public: 3 /** 4 * @param nums: A list of integer which is 0, 1 or 2 5 * @return: nothing 6 */ 7 void sortColors(vector<int> &nums) { 8 // write your code here 9 int i = 0, j = nums.size(); 10 for (int k = 0; k < j; ++k) { 11 if (nums[k] == 0) { 12 swap(nums[i++], nums[k]); 13 } else if (nums[k] == 2) { 14 swap(nums[--j], nums[k--]); 15 } 16 } 17 } 18 };
转载于:https://www.cnblogs.com/CheeseZH/p/5009541.html
相关资源：数据结构—成绩单生成器