[LeetCode][Golang]|[LeetCode][Golang] 75. 颜色分类 [LeetCode][Golang]75.颜色分类

题目：
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
【[LeetCode][Golang]|[LeetCode][Golang] 75. 颜色分类】我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例：

输入： nums = [2,0,2,1,1,0] 输出： [0,0,1,1,2,2]

n == nums.length
1 <= n <= 300
nums[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，这样才能保证数组中的每个元素均被处理过，且最终三个区间均满足不变式，算法成立。