九章算法：

class Solution {
public:
    /**
     * @param nums: A list of integer which is 0, 1 or 2
     * @return: nothing
     */
    void sortColors(vector<int> &nums) {
        // write your code here

        int index = 0;
        int one = 0;
        int two = nums.size()-1;
        while (index <= two) {
            if (nums[index] == 0) {
                swap(nums[one], nums[index]);
                ++index;
                ++one;
            } else if (nums[index] == 2) {
                swap(nums[index], nums[two]);
                --two;
            } else {
                ++index;
            }
        }
    }
};

九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

题解：力扣
一句话题解：做对这道题需要熟悉快速排序的 partition 过程。

说明：使用库函数排序和手写计数排序都可以完成这道问题，这里省略。

什么是 partition ？
我们在学习 快速排序 的时候知道，可以选择一个标定元素（称为 pivot ，一般而言随机选择），然后通过一次扫描，把数组分成三个部分：

第 1 部分严格小于 pivot 元素的值；
第 2 部分恰好等于 pivot 元素的值；
第 3 部分严格大于 pivot 元素的值。
第 2 部分元素就是排好序以后它们应该在的位置，接下来只需要递归处理第 1 部分和第 3 部分的元素。

经过一次扫描把整个数组分成 33 个部分，正好符合当前问题的场景。写对这道题的方法是：把循环不变量的定义作为注释写出来，然后再编码。

复习 partition
说明：这部分与本题解法无直接关系，直接跳过不影响后续内容的阅读。

下面的动画，从一个中间的状态开始演示，通过循环变量 i 以及设置两个边界变量 lt 和 gt 把一个数组分成 33 个部分。

1 / 13

以下给出不同的写法，循环不变量的定义写在了注释中。使用「循环不变量」编码是为了便于我们处理细节，也方便他人阅读代码。

循环不变量定义 1
循环不变量：声明的变量在遍历的过程中需要保持定义不变。

设计循环不变量的原则
说明：设计循环不变量的原则是 不重不漏。

len 是数组的长度；
变量 zero 是前两个子区间的分界点，一个是闭区间，另一个就必须是开区间；
变量 i 是循环变量，一般设置为开区间，表示 i 之前的元素是遍历过的；
two 是另一个分界线，我设计成闭区间。
如果循环不变量定义如下：

所有在子区间 [0, zero) 的元素都等于 0；
所有在子区间 [zero, i) 的元素都等于 1；
所有在子区间 [two, len - 1] 的元素都等于 2。
于是编码要解决以下三个问题：

变量初始化应该如何定义；
在遍历的时候，是先加减还是先交换；
什么时候循环终止。
处理这三个问题，完全看循环不变量的定义。

编码的时候，zero 和 two 初始化的值就应该保证上面的三个子区间全为空；
在遍历的过程中，「下标先加减再交换」、还是「先交换再加减」就看初始化的时候变量在哪里；
退出循环的条件也看上面定义的循环不变量，在 i == two 成立的时候，上面的三个子区间就正好 不重不漏 地覆盖了整个数组，并且给出的性质成立，题目的任务也就完成了。
参考代码 1：

import java.util.Arrays;


public class Solution {

    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }

        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, len - 1] = 2
        
        // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
        // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
        // 所以下面遍历到 0 的时候，先交换，再加
        int zero = 0;

        // 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
        // 所以下面遍历到 2 的时候，先减，再交换
        int two = len;
        int i = 0;
        // 当 i == two 上面的三个子区间正好覆盖了全部数组
        // 因此，循环可以继续的条件是 i < two
        while (i < two) {
            if (nums[i] == 0) {
                swap(nums, i, zero);
                zero++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                two--;
                swap(nums, i, two);
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

复杂度分析：

时间复杂度：O(N)O(N)，这里 NN 是输入数组的长度；
空间复杂度：O(1)O(1)。
循环不变量定义 2
参考代码 2：

JavaPythonC++

public class Solution {

    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }
        // all in [0, zero] = 0
        // all in (zero, i) = 1
        // all in (two, len - 1] = 2

        // 为了保证初始化的时候 [0, zero] 为空，设置 zero = -1，
        // 所以下面遍历到 0 的时候，先加，再交换
        int zero = -1;

        // 为了保证初始化的时候 (two, len - 1] 为空，设置 two = len - 1
        // 所以下面遍历到 2 的时候，先交换，再减
        int two = len - 1;
        int i = 0;
        // 当 i == two 的时候，还有一个元素还没有看，
        // 因此，循环可以继续的条件是 i <= two
        while (i <= two) {
            if (nums[i] == 0) {
                zero++;
                swap(nums, i, zero);
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                swap(nums, i, two);
                two--;
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
复杂度分析：（同参考代码 1）

说明：这种做法是我在 Java 的 JDK 的源码中 Arrays.sort() 中学到的。

我的体会是：

编码者应该在代码中使用注释表达这段代码编写的算法思想，提醒自己也方便他人。
但是源代码中类似 ++k <= great 和 a[++left] >= a[left - 1] 这样的代码建议不要写，会给阅读者带来理解上的障碍，这种做法也是《阿里巴巴 Java 开发手册》中不推荐的，理由是：变量的值发生变化是一个很重要的逻辑，应该单独成为一行，否则不利于调试和以后定位问题，这种语法糖我个人认为应该禁止使用。

相关问题
下面这两个问题可以用于复习 partition 的过程。

「力扣」第 215 题：数组中的第 K 个最大元素（中等）
「力扣」第 451 题：根据字符出现频率排序（中等）
说明：这一题参与比较的是字符，题目中虽然没有给出字符的范围，但是通过测试可以知道，测试数据的字符不超过 128128 个，符合有大量重复元素出现的情况，可以使用 partition 的过程对输入数据进行排序。

「力扣」第 451 题参考代码：

手写快速排序，如果很熟悉 partition，代码只需要稍作修改即可。

Java

import java.util.Random;

public class Solution {

    private int[] freq;

    private static final Random RANDOM = new Random();

    public String frequencySort(String s) {
        // 先转换为字符数组，以避免 charAt() 方法每次都检查下标有效性
        char[] charArray = s.toCharArray();
        // 用 128 是测试出来的，说明题目中的字符只有 a-zA-Z
        freq = new int[128];
        for (char c : charArray) {
            freq[c]++;
        }

        int len = charArray.length;
        quickSort(charArray, 0, len - 1);
        return new String(charArray);
    }

    private void quickSort(char[] charArray, int left, int right) {
        if (left >= right) {
            return;
        }
        int randomIndex = left + RANDOM.nextInt(right - left + 1);
        swap(charArray, randomIndex, left);

        // 循环不变量定义
        // all in [left + 1, lt] 的频数 > pivot 的频数
        // all in [lt + 1, i) 的频数 = pivot 的频数
        // all in [gt, right] 的频数 < pivot 的频数
        int pivot = charArray[left];
        int lt = left;
        int gt = right + 1;

        int i = left + 1;
        while (i < gt) {
            // 只需要在这句话外面套一层 freq [] ，其它逻辑和快速排序一样
            if (freq[charArray[i]] > freq[pivot]) {
                lt++;
                swap(charArray, i, lt);
                i++;
            } else if (charArray[i] == pivot) {
                i++;
            } else {
                gt--;
                swap(charArray, i, gt);
            }
        }
        swap(charArray, left, lt);
        // 注意这里，大大减少了分治的区间
        quickSort(charArray, left, lt - 1);
        quickSort(charArray, gt, right);
    }

    private void swap(char[] charArray, int index1, int index2) {
        char temp = charArray[index1];
        charArray[index1] = charArray[index2];
        charArray[index2] = temp;
    }
}
下面的问题用于复习循环不变量。

「力扣」第 26 题：删除排序数组中的重复项（简单）
「力扣」第 27 题：移除元素（简单）
「力扣」第 283 题：移动零（简单）
参考资料
在《算法导论》里大量使用了「循环不变量」这个概念说明和证明问题。但「循环不变量」并不是一个很高深的概念，其实我们很多时候，在编写代码的过程中都在不自觉地维护了变量的定义。「循环不变量」只是一个学术化的名字而已，设计清楚「循环不变量」，可以帮助我们写出正确的代码。

《算法导论》第 2.1 节 插入排序
《算法导论》第 2.3.1 节 分治法
《算法导论》第 6.3 节 建堆
《算法导论》第 7.1 节 快速排序的描述
事实上，一个广泛应用「循环不变量」概念的算法就是 二分查找，二分查找有些时候不能写对，与不能维持循环不变量的定义有很大的关系。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/sort-colors/solution/kuai-su-pai-xu-partition-guo-cheng-she-ji-xun-huan/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = partition(nums, 0, nums.size()-1, 0);
        if (nums[nums.size()-1] == 0) {
            return ;
        }
        partition(nums, left, nums.size()-1, 1);
    }
private:
    int partition(vector<int>& nums, int left, int right, int val) {
        if (left >= right) {
            return left;
        }
        int start = left;
        int end = right;
        while (start <= end) {
            while (start <= end && nums[start] <= val) {
                ++start;
            }
            while (start <= end && nums[end] > val) {
                --end;
            }
            
            if (start <= end) {
                swap(nums[start], nums[end]);
                ++start;
                --end;
            }
        }
        return end + 1;
    }
};

下面这种方法，和螺丝&螺母的那个题目一样

1.先找0的位置，然后和最左边的元素交互，然后最后将0的位置插入正确位置

2.然后在重新找到1的位置，同理做交换，然后最后将1的位置插入正确位置

class Solution {
public:
    /**
     * @param nums: A list of integer which is 0, 1 or 2
     * @return: nothing
     */
    void sortColors(vector<int> &nums) {
        // write your code here
	int len = nums.size();
	if (len <= 0) {
	    return ;
	}
	int i = 0;
	for (i = 0; i < nums.size(); ++i) {
	    if (nums[i] == 0) {
		break;
	    }
	}
	swap(nums[0], nums[i]);
	int left = 1;
	int right = len -1;
	while(left <= right) {
	    while (left <= right && nums[left] == 0) {
		++left;
	    }
	    while (left <= right && nums[right] != 0) {
		--right;
	    }
	    if (left <= right) {
		swap(nums[left], nums[right]);
		++left;
		--right;
	    }
	}
	swap(nums[right], nums[0]);
	for (i = right + 1;i < len; ++i) {
	    if (nums[i] == 1) {
		break;
	    }
	}
	int bj = right+1;
	swap(nums[right+1], nums[i]);
	left = right+2;
	right = len-1;
	while(left <= right) {
	    while (left <= right && nums[left] == 1) {
		++left;
	    }
	    while (left <= right && nums[right] != 1) {
		--right;
	    }
	    if (left <= right) {
		swap(nums[left], nums[right]);
		++left;
		--right;
	    }
	}
	swap(nums[right], nums[bj]);
    }
};