前言
新的一年，好好学习
正文
问题来源
本问题来自leetcode上的75题。
问题描述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 （空间使用最少）
示例 1:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？
分析：
func sortColors(nums []int) {
count := make([]int,3)
for i := 0; i < len(nums); i++ {
count[nums[i]]++
}
for i := 0; i < count[0]; i++ {
nums[i] = 0
}
count[1] += count[0]
for i := count[0]; i < count[1]; i++ {
nums[i] = 1
}
count[2] += count[1]
for i := count[1]; i < count[2]; i++ {
nums[i] = 2
}
}
借助于快速排序的partition思想，以1为枢纽元对数组进行划分，使0在数组的左边，2在数组的右边，1在数组的中间。
class Solution {
public:
void sortColors(int A[], int n) {
//zeroEnd是放0那部分的尾部索引，twoEnd是放2那部分的首部索引
//碰到0放到zeroEnd+1处，碰到2放到twoEnd-1处，碰到1指针后移
int zeroEnd = -1, twoBegin = n, i = 0;
while(i < twoBegin)
{
if(A[i] == 0 && i != ++zeroEnd)
swap(A[zeroEnd], A[i]);
else if(A[i] == 2 && i != --twoBegin)
swap(A[twoBegin], A[i]);
else
i++;
}
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
