快排优化(荷兰国旗问题)

前言

在快速排序中，一个比较核心的操作是partition，就是选中一个元素作为枢轴pivot，然后执行partition操作将数组元素分为三个部分<= pivot、=pivot和>=pivot,partition返回pivot的最终下标，然后再递归pivot左右两部分数组。
问题：传统的partition每次只能确定一个元素的位置。这样存在的问题是，如果有很多重复的元素，显然是做了很多重复的比较工作。
解决：荷兰国旗问题就是用于解决这个问题的，它的partition操作将数组分成三个部分<pivot、=pivot和>pivot。每次partition返回=pivot部分的边界，然后递归<pivot和>pivot部分即可。这样一次就可以确定多个元素的位置。

荷兰国旗问题

问题描述

荷兰国旗问题是计算机科学中的一个程序难题，它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。

现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。

具体操作

对应到我们的数组partition就是将红白蓝类比为< pivot、=pivot和> pivot。
假设给定一个数组，arr = [3,3,3,2,6,8,3,9,2,4,3]

• 初始状态下，定义变量L表示< pivot区域的最右位置，变量R表示> pivot区域的第一个位置，cur遍历数组，直到cur遇到R。(如下图)
  
  选择数组的最后一个元素作为枢轴pivot，因此最后一个位置可以当它不存在，因为初始时R = arr.length - 1。
• cur遍历数组，遇到的元素分为三种情况
  • arr[cur] == pivot，此时只需要跳过，L和R都不需要更新。
  • arr[cur] < pivot，此时情况如下图
    
    此时需要将L的边界向右扩充1，具体操作是将L + 1位置的元素和cur位置的元素交换，然后L++，cur++

  if (arr[cur] < pivot) {
      swap(arr, ++L, cur++);
  

  • arr[cur] > pivot，此时情况如下图
    
    此时需要将R的边界向左扩充1，具体操作是将R - 1位置的元素和cur位置的元素交换，然后R--，cur不变(因为交换后cur位置的元素原本是cur之后的元素，是没有遍历过的)

    } else if (arr[cur] > pivot) {
        swap(arr, --R, cur);
  

• 遍历结束后，如下图

  
  

cur == R，遍历结束，处理一下枢轴pivot，很简单就是将R位置的元素和pivot位置的元素交换。
至此，可以知道= pivot区域的左右边界，然后只需要递归< pivot和> pivot部分即可完成快速排序。

代码

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(arr, l, r);
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }
    public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        swap(arr, more, r);
        return new int[] { less + 1, more };
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }