Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

    Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

    Note: You are not suppose to use the library’s sort function for this problem.

    Example:

    1. Input: [2,0,2,1,1,0]
    2. Output: [0,0,1,1,2,2]

    Follow up:

    • A rather straight forward solution is a two-pass algorithm using counting sort.
      First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
    • Could you come up with a one-pass algorithm using only constant space?

    题意

    将一个只包含0、1、2的数组排序，不允许使用内置的排序函数。

    思路

    经典的“荷兰旗🇳🇱”问题。

    最简单的做法是先遍历一遍统计0、1、2的个数，再遍历一遍逐个按个数输出0、1、2。

    只遍历一遍的方法，实际上是对最基础的快速排序方法进行重复元素优化：将数组分为三个区间，左区间存放比目标值小的元素，右区间存放比目标值大的元素，中部区间存放与目标值相同的元素，每次递归只递归左区间和右区间。

    代码实现 - 快排优化

    1. class Solution {
    2.     public void sortColors(int[] nums) {
    3.         sort(nums, 0, nums.length - 1);
    4.     }
    6.     private void sort(int[] nums, int start, int end) {
    7.         if (start >= end) {
    8.             return;
    9.         }
    11.         int i = start;                        // 当前遍历元素
    12.         int left = start, right = end;        // left左侧元素小于目标值，right右侧元素大于目标值
    13.         int temp = nums[start];                // 目标值
    15.         while (i <= right) {
    16.             if (nums[i] < temp) {
    17.                 swap(nums, i++, left++);    // 当前元素小于目标值，移到左侧区间
    18.             } else if (nums[i] > temp) {
    19.                 swap(nums, i, right--);        // 当前元素大于目标值，移到右侧区间
    20.             } else {
    21.                 i++;                        // 当前元素等于目标值，保留在中间区间中不移动
    22.             }
    23.         }
    25.         sort(nums, start, left - 1);
    26.         sort(nums, right + 1, end);
    27.     }
    30.     private void swap(int[] nums, int i, int j) {
    31.         int temp = nums[i];
    32.         nums[i] = nums[j];
    33.         nums[j] = temp;
    34.     }
    35. }

    代码实现 - 统计排序

    1. class Solution {
    2.     public void sortColors(int[] nums) {
    3.         // 统计个数
    4.         int[] count = new int[3];
    5.         for (int i = 0; i < nums.length; i++) {
    6.             count[nums[i]]++;
    7.         }
    8.         // 重新填充数组
    9.         int i = 0;
    10.         for (int j = 0; j < 3; j++) {
    11.             while (count[j]-- != 0) {
    12.                 nums[i++] = j;
    13.             }
    14.         }
    15.     }
    16. }