partition与荷兰国旗问题

partition问题：

partition问题是快速排序重要的一环，其仅要求将小于等于部分移动到pivot左边，大于的部分移动到pivot右边，

基本思想是：

设置小于等于区域，然后从low遍历到high，当遍历的值小于等于pivot，则将小于等于区域增1，然后和遍历值交换。

def partition(nums, low, high):
            i = low - 1
            pivot = nums[high]
            for j in range(low, high+1):
                if nums[j] <= pivot:
                    i += 1
                    nums[i], nums[j] = nums[j], nums[i]
            return i
           

荷兰国旗问题：

与partition问题不同的是，荷兰国旗问题额外要求等于基准值的都处于中间位置，所以相对于partition问题，荷兰国旗问题需要同时设置一个小于区域和一个大于区域，当遍历指针i在大于区域左侧时遍历，若遍历到的数小于pivot，则小于区域增1交换然后遍历指针增1，若相等，则什么也不干，增1，若大于，则大于区域减1，交换，此时i不增。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        len_nums = len(nums)
        low = -1
        high = len_nums
        h = 0
        while h < high:
            if nums[h] < 1:
                low += 1
                nums[low], nums[h] = nums[h], nums[low]
                h += 1
            elif nums[h] == 1:
                h += 1
            else:
                high -= 1
                nums[h], nums[high] = nums[high], nums[h]