1. /**
    2.  * @Description 三路快排，核心思想在于循环不变量的设计
    3.  * @Date 2022/1/9 4:35 下午
    4.  * @Author wuqichuan@zuoyebang.com
    5.  **/
    6. class Solution {
    7.     //循环不变量设计如下，定义出三个区间
    8.     //nums[0.....zero] = 0
    9.     //nums[zero + 1 .....two-1] = 1
    10.     //nums[two ... nums.length - 1] = 2
    12.     public void sortColors(int[] nums) {
    13.         //先定义好zero 和 two 两个索引位置，先把两个索引放到无效值，确保第一次循环中
    14.         //循环不变量初始值是空的，是无效的
    15.         int zero = -1;
    16.         int two = nums.length;
    17.         int i = 0;
    18.         while(i < two){
    19.             if(nums[i] == 1){
    20.                 i ++;
    21.             }else if(nums[i] == 2){
    22.                 two--;
    23.                 swap(nums,i,two);
    24.             }else if (nums[i] == 0) {
    25.                 zero++;
    26.                 swap(nums,zero,i);
    27.                 i++;
    28.             }
    29.         }
    30.     }
    31.     public void swap(int[] nums, int index1, int index2) {
    32.         int temp = nums[index1];
    33.         nums[index1] = nums[index2];
    34.         nums[index2] = temp;
    35.     }
    36. }