题目：
给定一个蕴含红色、红色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得雷同色彩的元素相邻，并依照红色、红色、蓝色顺序排列。
咱们应用整数 0、 1 和 2 别离示意红色、红色和蓝色。
必须在不应用库的sort函数的状况下解决这个问题。
示例：
输出： nums = [2,0,2,1,1,0]输入： [0,0,1,1,2,2]n == nums.length1 <= n <= 300nums[i]为0、1或2
进阶：
- 你能够不应用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅应用常数空间的一趟扫描算法吗？
先贴代码：（GO语言）
func sortColors(nums []int) { left, i, right := 0, 0, len(nums)-1 // 不变量： left之前（不蕴含nums[left]）均为0，right之后（不蕴含nums[right]）均为2 // all in [0,left) == 0 // all in [left,i) == 1 // all in (right,len) == 2 for i <= right { if nums[i] == 0 { nums[left], nums[i] = nums[i], nums[left] left++ i++ } else if nums[i] == 2 { nums[right], nums[i] = nums[i], nums[right] right-- } else { i++ } }}咱们能够借鉴疾速排序的思维对问题进行剖析。首先设置循环不变量如下：
[0,left) == 0，即left之前（不包含nums[left]）不蕴含元素0之外的元素。[left,i) == 1，即left和目前循环到的i之间不蕴含元素1之外的元素。(right,len) == 2，即right之后（不包含nums[right]）不蕴含元素2之外的元素。
算法解决步骤如下：
- 初始
left设为0，i设为0，right设为len-1，则为0的区间是[0,0)，不蕴含元素。为1的区间是[0,0)，不蕴含元素。为2的区间是(len-1,len)，不蕴含元素。所以初始状态满足不变式要求。 接下来的循环中，依据
nums[i]的值进行保护不变式的操作。分为以下三种状况- 当
nums[i]为0时，替换nums[i]和nums[left]，并使left和i后移，满足不变式。 - 当
nums[i]为1时，后移i，满足不变式。 - 当
nums[i]为2时，替换nums[i]和nums[right]，并使right前移，满足不变式。留神替换后是nums[right]的值承受了本次循环的值判断，而替换后的nums[i]的值并没有承受值判断，所以不执行i的后移操作，须要在下一次循环中依据其值解决。
- 当
- 因为后两个区间中
i和right均为开区间，若当i == right循环进行，则元素nums[i]也能够说是元素nums[right]没有通过分类解决，因而最终循环终止条件为i <= right，这样能力保障数组中的每个元素均被解决过，且最终三个区间均满足不变式，算法成立。
复杂度剖析：
- 工夫复杂度：
O(n)，其中n是数组nums的长度。 - 空间复杂度：
O(1)。咱们只须要常数的空间存储若干变量。