アルゴリズムカラーソート

色のソート

本を解く

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        mid = 1
        i, j = 0, 0
        k = len(nums)
        while j < k:
            if nums[j] < mid:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j += 1
            elif nums[j] > mid:
                k -= 1
                nums[k], nums[j] = nums[j], nums[k]
            else:
                j += 1

この問題はダエストラが1976年に提起したオランダ国旗問題と同じ問題であり、迅速なソートの改善策にも大きく関係している.

i,kは2つのポインタとして,j移動時にmid値を基準として交換する.