三色旗问题详解(两种高效优雅的 实现方式)

leetcode 75 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

对这道题进一步的进行推广，在数组中任意选择一个数pivot，将比pivot小的数在左边，比pivot大的数在右边，等于pivot载中间，举例：[3,4,4,2,7,9] 将pivot = 4,排序之后的结果就是[3,2,4,4,7,9]

第一种方式解决方式

代码的思路：(注意是开区间，还是闭区间) 初始情况：front = -1, rear = n, 分别是小于pivot，和大于pivot的区间分界点的指针，cur = 0 待处理的元素指针 数组空间划分成四部分 [0,front] 小于pivot , [rear,n-1]区间大于pivot，在（cur，rear）这个区间待处理的数据,(front,cur)等于pivot区间；

操作： 情况一：nums[cur] == pivot，直接cur++; 情况二：nums[cur] < pivot, 交换数组front+1和cur的位置，front++,cur++ 情况三：nums[cur] > pivot 交换数组rear-1和cur的位置，rear–(注意cur此时是不变了的，这是因为 交换过来的元素还没有判断过)

判断的结束条件：cur和rear指针相遇

private void sortArrayByKey (int[] nums,int key) {
          
   
        int front = -1,rear = nums.length;
        int cur = 0;
        while(cur < rear){
          
   
            if(nums[cur] < key) {
          
   
                swap(nums,++front,cur++);
            } else if(nums[cur] > key) {
          
   
                swap(nums,--rear,cur);
            } else {
          
   
                cur++;   
            }
        }
    }

第二种方式 其实实现逻辑也是通过指针划分区间的方式实现（弄清指针的含义，问题就解决一半了）

1. 指针p1小于最右pivot的位置
2. 指针p2指向小于等于最右pivot的位置
3. 指针指向cur的大于pivot最右侧的一个指针

初始化 p1 = -1,p2 = -1,cur = 0，其实区间都是没有元素的 情况一：nums[cur] > pivot时，cur++; 情况二 ：nums[cur] <= pivot, 将p2 + 1的位置和cur交换位置，p2++; 接着判断 nums[p2] < pivot成立，继续交换p1 + 1 和p2的位置，然后更新p1++；

private void sortArrayByPivotV2(int[] nums,int pivot) {
          
   
        int p1 = -1,p2 = -1;
        int cur = 0;
        while(cur < nums.length) {
          
   
            if(nums[cur] <= pivot){
          
   
                swap(nums,++p2,cur);
                if(nums[p2] < pivot) {
          
   
                    swap(nums,++p1,p2);
                }
            }
            //当前元素大于pivot的时候如何处理呢？ 什么也不做，只是更新cur下表
            cur++;
        }
    }

欢迎小伙伴 评论区交流！！！