云购网站建设/网站关键词优化排名怎么做

输入一个整数列表，每个元素在0~2之间，其中0，1，2分别代表红、白、蓝。现要求对列表进行排序，相同颜色的在一起，而且按红白蓝顺序先后排列。要求时间复杂度为O(n)，只能在原列表中交互位置，不能使用辅助空间

如果可以使用辅助空间，那直接遍历一次列表，将0放到一个列表，1放到1个列表，2放到一个列表，然后3个列表相加就可以了

如果复杂度没有要求，可以使用多种排序方式，将整个列表进行进行排序，但时间复杂度不符合要求

如果只能排序一次，可以使用类似快速排序的方法，设立指针

第一个指针，为，起始指针，

第二个指针，为，末尾指针

第三个指针，为，遍历指针

当遍历指针，遍历到0的时候，就交换，起始指针和遍历指针的元素，并且把两个指针数字加1

当遍历指针，遍历到2的时候，就交换，末尾指针和遍历指针的元素，并且末尾指针数字-1

当遍历指针，遍历到1的时候，就只把遍历指针数字+1

def pai(l, q, z):#传入列表，起始下标，终止下标

q1 = q

z1 = z

i = q

while q1 < z1 and i <= z1:

while l[i] == 0 and i <= z1:

l[i], l[q1] = l[q1], l[i]

q1 += 1

i += 1

while l[i] == 2 and i <= z1:

l[i], l[z1] = l[z1], l[i]

z1 -= 1

while l[i] == 1 and i <= z1:

i += 1

return l