leetCode #75 Sort Colors

大家好，我是小鸭酱，博客地址为：http://www.cnblogs.com/xiaoyajiang

这个题目超简单是不，用计数排序就搞定了~

代码如下：

 1 class Solution {
 2 public:
 3     void sortColors(vector<int>& nums) {
 4         if (nums.size() == 0)
 5         {
 6             return;
 7         }
 8         int count1 = 0, count0 = 0;
 9         for (int num : nums)
10         {
11             if (num == 0)
12             {
13                 ++count0;
14             }
15             if (num == 1)
16             {
17                 ++count1;
18             }
19         }
20         int i = 0;
21         for (; i < count0; ++i)
22         {
23             nums[i] = 0;
24         }
25         for (; i < count0 + count1; ++i)
26         {
27             nums[i] = 1;
28         }
29         for (; i < nums.size(); ++i)
30         {
31             nums[i] = 2;
32         }
33             
34     }
35 };

可是可是，这不是遍历了两遍吗？下面介绍遍历一遍就能完成的算法，三路快排来啦：

 1 class Solution {
 2 public:
 3     void sortColors(vector<int>& nums) {
 4         int zero = -1;  // [0..zero] == 0
 5         int i = 0;  // [i..two] == 1
 6         int two = nums.size();  // [two..nums.size()] == 2
 7         while (i < two)
 8         {
 9             if (nums[i] == 1)
10             {
11                 nums[i++] = 1;
12             }
13             else if (nums[i] == 0)
14             {
15                 swap(nums[i++], nums[++zero]);
16             }
17             else
18             {
19                 assert(nums[i] == 2);
20                 swap(nums[i], nums[--two]);
21             }
22         }
23     }
24 };