一次遍历
思路:
由于排序后数组左侧0开始，右侧2结尾，可以使用两个指针p0记录左侧中0的位置，和p2记录右侧中2的位置。对数组进行遍历，如果遇到0，则与p0指向的元素值互换，p0指向下一位置，继续遍历下一元素。如果遇到2，则与p2指向的元素值互换，p2指向前一位置，继续遍历当前元素。遇到1，继续遍历下一元素。（这里p0继续遍历下一元素，p2还要遍历当前元素，是因为数组是从左向右遍历，p0在左边，也就意味着在遇到0进行交换的时候p0指向的只可能是当前位置0或者1，交换后可以直接遍历下一个元素，而p2指向的元素未知，交换后的当前值如果是2，则需要进行下一次交换）
代码：
class Solution: def sortColors(self, nums: List[int]) -> None: p0 = curr = 0 p2 = len(nums) - 1 while curr <= p2: if nums[curr] == 0: nums[p0], nums[curr] = nums[curr], nums[p0] p0 += 1 curr += 1 elif nums[curr] == 2: nums[curr], nums[p2] = nums[p2], nums[curr] p2 -= 1 else: curr += 1
原文：https://www.cnblogs.com/nilhxzcode/p/13097387.html