给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

这个问题是经典的荷兰国旗问题，可以使用三指针的方法来解决。

定义三个指针：left、right、cur，分别表示当前处理到的数组左侧区间、右侧区间和当前元素。

初始时，left指向数组头部，right指向数组尾部，cur指向数组头部。

从头到尾遍历数组，如果当前元素为红色，则将其和left指向的元素交换，并将left指针右移一位；如果当前元素为白色，则将cur指针右移一位；如果当前元素为蓝色，则将其和right指向的元素交换，并将right指针左移一位。

遍历结束后，数组就会按照红色、白色、蓝色的顺序排列。

下面是示例代码：

def sortColors(nums):
    left, right, cur = 0, len(nums) - 1, 0
    while cur <= right:
        if nums[cur] == 0:
            nums[left], nums[cur] = nums[cur], nums[left]
            left += 1
            cur += 1
        elif nums[cur] == 2:
            nums[right], nums[cur] = nums[cur], nums[right]
            right -= 1
        else:
            cur += 1

时间复杂度为O(n)，空间复杂度为O(1)。

相关问题

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

这个问题可以使用荷兰国旗问题的解法来解决。荷兰国旗问题是由计算机科学家 Edsger Dijkstra 提出的，它的思路是维护三个指针，分别指向当前已经排序好的红色区域的右边界、当前已经排序好的白色区域的右边界和当前已经排序好的蓝色区域的左边界。初始时，红色区域和蓝色区域都是空的，白色区域包含整个数组。

具体的实现步骤如下：

1. 初始化红色区域的右边界为-1，白色区域的右边界为0，蓝色区域的左边界为n-1。
2. 当前元素为白色时，将白色区域的右边界向右移动一位。
3. 当前元素为红色时，将红色区域的右边界向右移动一位，并将当前元素与红色区域的下一个元素交换。
4. 当前元素为蓝色时，将蓝色区域的左边界向左移动一位，并将当前元素与蓝色区域的前一个元素交换。
5. 当白色区域的右边界与蓝色区域的左边界相遇时，排序完成。

代码实现如下：

def sortColors(nums):
    red, white, blue = -1, 0, len(nums)
    while white < blue:
        if nums[white] == 0:
            red += 1
            nums[red], nums[white] = nums[white], nums[red]
            white += 1
        elif nums[white] == 1:
            white += 1
        else:
            blue -= 1
            nums[blue], nums[white] = nums[white], nums[blue]
    return nums

时间复杂度为O(n)，空间复杂度为O(1)。

算法课指针] 颜色分类 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 输入 第一行输入一个整数 � ( 1 ≤ � ≤ 3 0 0 ) n (1≤n≤300) 代表数组的长度。 第二行输入一行数字代表数组 � � � � [ � ] nums[i] 为0，1，2，数字与数字之间用空格间开。

这是一道典型的荷兰国旗问题，可以使用三指针的方法解决。具体步骤如下：

1. 定义三个指针，分别指向数组的开始、当前位置和末尾。
2. 遍历数组，如果当前位置为0，则将其与开始指针所指位置交换，并将开始指针后移一位；如果当前位置为2，则将其与末尾指针所指位置交换，并将末尾指针前移一位；如果当前位置为1，则继续遍历。
3. 遍历完成后，数组就被分为了三段，分别为0、1和2。

以下是示例代码实现：

n = int(input())
nums = list(map(int, input().split()))

start, curr, end = 0, 0, n - 1

while curr <= end:
    if nums[curr] == 0:
        nums[start], nums[curr] = nums[curr], nums[start]
        start += 1
        curr += 1
    elif nums[curr] == 2:
        nums[curr], nums[end] = nums[end], nums[curr]
        end -= 1
    else:
        curr += 1

print(nums)