史上最清晰的三路快速排序

“ 温馨提示，阅读本文可能需要 6 分钟。”

本文主要介绍一下三路快排，并以微软的一道面试题 leetcode 75. 颜色分类作为例题来讲解，供大家参考，希望对大家有所帮助。

三路快排

使用快速排序的思想给带有大量的重复键值的数组进行排序，一种经典的实现方式就是三路快排（Quick Sort 3 Ways）。

主要思想：将整个数组分成三部分，即小于 v、等于 v 和大于 v。分割后在递归的过程中，只需要递归地对小于 v 和大于 v 的部分进行快速排序，不关心等于 v 的部分。如下图示。

1、将数组分为三部分，索引 lt 指向小于 v 的最后一个元素的位置，所以 nums[l+1...lt] < v，即区间 [l+1, lt] 中的元素均小于 v。同理索引 gt 指向大于 v 的第一个元素的位置 ，所以 nums[gt...r] > v，lt 和 gt 分别是 less than 和 greater than 的缩写。

2、当前需要处理的元素为 i 位置的元素 k，保证 nums[lt+1...i-1] == v。如果 k == v，将 k 纳入等于 v 的部分，i 右移继续遍历。

3、如果 k < v，只需要将该元素与等于 v 的第一个元素交换位置，此时元素 k 处于小于 v 的最后一个元素，相应地 lt 向右移动一位，i 继续右移，查看下一个元素。

4、如果此时 k > v，只需要将该元素与 gt - 1 对应的元素交换位置，此时元素 k 处于数组大于 v 的第一个元素，相应地 gt 向左移动一位，指向大于 v 的第一个位置。

5、排序完成之后，数组如下图示意，lt 和 gt 分别指向小于 v 的最后一个位置和大于 v 的第一个位置，最后交换 l 位置的元素跟 lt 位置的元素，之后只需要对小于 v 和大于 v 的部分进行递归快速排序，等于 v 的部分已经放在数组中合适的位置。

优点：不需要对大量等于 v 的元素进行重复操作，可以少考虑很多元素，特别是对于等于 v 的元素特别多的话，这一步优化变得非常明显。

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

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

输出：[0,0,1,1,2,2]

示例 2：

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

输出：[0,1,2]

解题思路

由于排序后的数组主要依次分成三部分，即等于 0 的部分、等于 1 的部分和等于 2 的部分，这不是很像上面讲的三路快速排序吗？

每次选取一个标定点，由于数组中有很多个与标定点相等的元素，所以将数组分成三部分，即小于 v、等于 v 和大于 v，然后递归地对小于 v 和大于 v 的地方进行三路快排。

由于当前数组只有三个元素，所以只需要对整个数组执行一次三路快排即可。如下图示。

保证在遍历整个数组的过程中，0 处在整个数组的开始位置、1 处在紧接着 0 后面的位置，2 处在整个数组的末尾位置。

1、设置索引 zero 和 two，使得数组 nums[0...zero] == 0 和 nums[two...n-1] == 2，设置遍历索引 i 用于遍历数组元素，保证了 nums[zero+1...i-1] == 1。

2、当遍历到元素 m 时，如果 m == 1，此时只需将 m 纳入到属于 1 的部分，同时 i 右移。

3、如果 m == 2，只要取出索引 two 指向的元素的前一个元素 k（当前不等于 2 的第一个元素），与 m 进行交换位置，并将索引 two 左移一位，相当于将此时的 m 纳入到属于 2 的部分。

4、如果 m == 0，只需要找到索引 zero + 1 对应的元素（当前值为 1的第一个元素），将其与当前的 m 交换位置，并将 zero 右移，相当于将此时的 m 纳入到属于 0 的部分，将索引 i 右移查看下一元素的值。

Show me the Code

// c++
void sortColors(vector<int>& nums) {
  int zero = -1; // 保证下标0到zero对应的元素都为0 
  int two = nums.size(); // 保证下标two到numsSize-1对应的元素都为 2
  for (int i = 0; i < two;) {
    // 直接将遍历到的元素1纳入到属于1的部分，i右移继续遍历
    if (nums[i] == 1) {
      i++;
    }
    // 交换下标为two前一下标对应的元素与遍历到的元素
    // 并将遍历到的元素2纳入到属于2的部分，two左移
    else if (nums[i] == 2) {

        swap(nums[i], nums[--two]);
    }
    // 交换下标为zero后一下标对应的元素与遍历到的元素
    // 并将遍历到的元素0纳入到属于0的部分，zero和i右移
    else {
      swap(nums[++zero], nums[i++]);
    }
  }
}

// go
func sortColors(nums []int)  {
    zero, two := -1, len(nums)
    for i := 0; i < two; {
        if nums[i] == 1 {
            i++
        } else if nums[i] == 2 {
            two -= 1
            nums[i], nums[two] = nums[two], nums[i] 
        } else {
                zero += 1
                nums[i], nums[zero] = nums[zero], nums[i]
                i++ 
        }
    }
}