三向切分的快速排序

在遍历的过程中把待排序的部分分成 3 个区间
快速排序（三分天下） - 图1
「三向切分的快速排序」其实是之前的两个快速排序版本的结合。在变量 i 遍历的过程中，设置两个变量 lt 和 gt，保持下面的循环不变量的性质。

在循环的过程中，总有 [left + 1, lt] < pivot 、[lt + 1, i) = pivot 并且 [gt, right] >= pivot 成立。

请注意，这么设置是有具体原因的：

首先，把与 pivot 的元素的关系分得更细了，等于 pivot 的元素被单独分到了一组；
除了 i 之外的区间都使用闭区间，这是因为 i 是循环变量，表义为「遍历之前的元素」性质更好掌握。
根据这样的设定：

初始化的时候：

i = left + 1,lt = left ，gt = right + 1 大家可以验证一下，上面的这三个区间都为空；
遍历到一个元素的时候：

如果等于 pivot ，我们什么都不用做，i 向右移动一格即可 ；
如果严格小于 pivot ，我们先把 lt 向右移动一格，然后交换 lt 与 i，然后 i 再向右移动一格；
如果严格大于 pivot ，我们先把 gt 向左移动一格，然后交换 gt 与 i，此时 i 无须移动，因为交换过来的是一个我们还没有看到的元素，我们可以在下一轮循环中再根据它的大小执行相应的步骤。
循环终止的时候：

i = gt。因为 [lt + 1, i) 不包括 i。因此，这三个区间正好铺满了整个除了基准元素的那个区间，最后，我们交换一下 left 和 lt 的位置就好了。
接下来，我们对区间 [left, lt - 1] （注意这里是 lt - 1）和区间 [gt, right] 分别递归执行下去即可。

三向切分的快速排序能加速排序的原因是：如果执行 partition 的子区间当中，有很多元素都和基准元素相等，那么这些元素都能够在这一轮 partition 中被排定。请大家体会一下：由于和 pivot 相等的元素都被挤到了中间，它们前面的元素都比 pivot 小，它们后面的元素都比 pivot 大，因此它们就位于排序以后最终应该在的位置。

参考代码 1：

  2. private static final Random RANDOM = new Random();
  4. public int[] sortArray(int[] nums) {
  5.     int len = nums.length;
  6.     quickSort(nums, 0, len - 1);
  7.     return nums;
  8. }
  10. private void quickSort(int[] nums, int left, int right) {
  11.     if (left >= right) {
  12.         return;
  13.     }
  14.     int randomIndex = left + RANDOM.nextInt(right - left + 1);
  15.     swap(nums, randomIndex, left);
  17.     // all in [left + 1, lt] < pivot
  18.     // all in [lt + 1, i) = pivot
  19.     // all in [gt, right] > pivot
  20.     int pivot = nums[left];
  21.     int lt = left;
  22.     int gt = right + 1;
  24.     int i = left + 1;
  25.     while (i < gt) {
  26.         if (nums[i] < pivot) {
  27.             lt++;
  28.             swap(nums, i, lt);
  29.             i++;
  30.         } else if (nums[i] == pivot) {
  31.             i++;
  32.         } else {
  33.             gt--;
  34.             swap(nums, i, gt);
  35.         }
  36.     }
  37.     swap(nums, left, lt);
  38.     // 注意这里，大大减少了分治的区间，区间 [lt, gt - 1] 不必递归求解
  39.     quickSort(nums, left, lt - 1);
  40.     quickSort(nums, gt, right);
  41. }
  44. /**
  45. * @param nums
  46. * @param left
  47. * @param right
  48. */
  49. private void insertSort(int[] nums, int left, int right) {
  50.     for (int i = left + 1; i <= right; i++) {
  51.         if (nums[i - 1] <= nums[i]) {
  52.             continue;
  53.         }
  54.         int temp = nums[i];
  55.         int j = i;
  56.         while (j > left && nums[j - 1] > temp) {
  57.             // 后移一位
  58.             nums[j] = nums[j - 1];
  59.             j--;
  60.         }
  61.         nums[j] = temp;
  62.     }
  63. }
  65. private void swap(int[] nums, int index1, int index2) {
  66.     int temp = nums[index1];
  67.     nums[index1] = nums[index2];
  68.     nums[index2] = temp;
  69. }

}

练习
自行编写测试用例，完成下面的实验：在输入数据有大量重复元素的时候，这一节介绍的三向切分的快速排序能起到优化的效果；
完成「力扣」第 75 题：颜色分类（简单）；
说明：这是著名的荷兰国旗问题。
完成「力扣」第 451 题：根据字符出现频率排序（中等）。
总结
写好一个快速排序不是一件简单的事情，希望大家通过这 3 个小节的内容，进行相关的编码练习和调试，掌握写对一个程序的技巧：「循环不变量」。
快速排序是面试过程中经常被考察的知识点，请大家一定结合循环不变量来理解，特别是掌握避免出现最坏的时间复杂度的编写技巧。到此为止，基于比较的排序方法我们已经介绍完了，下一章我们会介绍基于关键字的三种排序方法。感谢大家。