每日算法 — 使用java实现荷兰国旗：三向切分双指针与快速排序优化

算法背景

荷兰国旗问题由计算机科学家Edsger Dijkstra提出，问题描述如下：给定一个只包含0、1、2的数组，要求原地排序使得所有0在前、1在中、2在后。该问题之所以经典，是因为它是快速排序三向切分（3-way partitioning）的核心思想来源，在含有大量重复元素的数组排序时，能将时间复杂度从O(n log n)优化到接近O(n)。

核心思路

采用三指针策略：
– left 指针：指向已排好序的0区域的右边界（下一个0应放入的位置）
– right 指针：指向已排好序的2区域的左边界（下一个2应放入的位置）
– i 指针：当前遍历的元素

遍历规则：
– 当 nums[i] == 0 时，与 left 位置交换，left++，i++
– 当 nums[i] == 1 时，i++（1已经在中间区域）
– 当 nums[i] == 2 时，与 right 位置交换，right–（交换后i不++，需要重新检查交换过来的元素）

完整Java实现

import java.util.Arrays;

/**
 * 荷兰国旗问题 - 三向切分双指针算法
 * 将只包含0、1、2的数组原地排序
 */
public class DutchNationalFlag {

    /**
     * 核心算法：三指针原地排序
     * 时间复杂度: O(n)  空间复杂度: O(1)
     */
    public void sortColors(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int left = 0;           // 0区域的右边界（下一个0应放的位置）
        int right = nums.length - 1;  // 2区域的左边界（下一个2应放的位置）
        int i = 0;              // 当前遍历指针

        while (i <= right) {
            if (nums[i] == 0) {
                // 当前是0，放到left位置，left和i都右移
                swap(nums, i, left);
                left++;
                i++;
            } else if (nums[i] == 1) {
                // 当前是1，已经在中间区域，直接右移
                i++;
            } else { // nums[i] == 2
                // 当前是2，放到right位置，right左移
                // i不移动，因为交换过来的元素需要重新判断
                swap(nums, i, right);
                right--;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 三向切分快速排序 - 荷兰国旗思想的应用
     * 适用于含有大量重复元素的数组排序
     */
    public void quickSort3Way(int[] nums, int lo, int hi) {
        if (lo >= hi) return;

        // 三向切分：将数组分为 < pivot, == pivot, > pivot 三部分
        int lt = lo;      // nums[lo..lt-1] < pivot
        int gt = hi;      // nums[gt+1..hi] > pivot
        int i = lo + 1;   // 当前遍历指针
        int pivot = nums[lo];

        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums, i++, lt++);
            } else if (nums[i] > pivot) {
                swap(nums, i, gt--);
            } else {
                i++; // nums[i] == pivot
            }
        }

        // 递归排序小于pivot和大于pivot的部分
        quickSort3Way(nums, lo, lt - 1);
        quickSort3Way(nums, gt + 1, hi);
    }

    /**
     * 通用版本：按给定target值进行三向分区
     * 将数组分为 < target, == target, > target 三部分
     */
    public int[] partition3Way(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int i = 0;

        while (i <= right) {
            if (nums[i] < target) {
                swap(nums, i++, left++);
            } else if (nums[i] > target) {
                swap(nums, i, right--);
            } else {
                i++;
            }
        }
        // 返回等于target区域的边界
        return new int[]{left, right};
    }

    public static void main(String[] args) {
        DutchNationalFlag solution = new DutchNationalFlag();

        // 测试用例1：基本排序
        int[] nums1 = {2, 0, 2, 1, 1, 0};
        System.out.println("原数组: " + Arrays.toString(nums1));
        solution.sortColors(nums1);
        System.out.println("排序后: " + Arrays.toString(nums1));

        // 测试用例2：含有大量重复元素的快速排序
        int[] nums2 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        System.out.println("\n原数组: " + Arrays.toString(nums2));
        solution.quickSort3Way(nums2, 0, nums2.length - 1);
        System.out.println("三向快排后: " + Arrays.toString(nums2));

        // 测试用例3：通用三向分区
        int[] nums3 = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
        System.out.println("\n原数组: " + Arrays.toString(nums3));
        int[] bounds = solution.partition3Way(nums3, 5);
        System.out.println("按5分区后: " + Arrays.toString(nums3));
        System.out.println("等于5的范围: [" + bounds[0] + ", " + bounds[1] + "]");
    }
}

复杂度分析

关键洞察：当数组中有大量重复元素时，三向切分能将比较次数减少约一半，这是因为等于pivot的元素不需要再参与递归排序。

扩展思考

1. K色排序：如果数组中包含k种不同的值，能否用类似方法？可以使用计数排序，时间O(n+k)，空间O(k)。
2. 按奇偶排序：能否用双指针法将数组分为奇数和偶数两部分？可以，但不需要三指针。
3. 快速选择优化：在三向切分后，如果目标位置落在等于pivot的区域，可以直接返回结果，无需继续递归。