Условие

Дан массив из n объектов разных цветов, красный, белый и голубой. Необходимо отсортировать этот массив таким образом, что бы объекты одного цвета были рядом, а цвета были в поряке красные, белый и голубой.

Для обозначения цветом будет использоваться числа 0,1 и 2 соответствующе для цветом красный, белый и голобуй.

Note: Нельзя использовать встроенные аглоритмы сортировки

пример 1

1
2

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

• Очевидное решение использует два прохода по массиву: в первом подсчитать количество единиц, нулей и двоек. Во втором проходе – записать соответствующее количетсво элементов;
• Попробуйте решить используя всего один проход по массиву.

Решение

Два указателя

Идея – использовать два указателя: конец последовательности нулей и конец последовательности единиц.

Идем по массиву :

• если текущий элемент равен нуля – обмениваем его и следующей за концом последовательности нулей
• если текущий элемент равен двум – обмениваем его и следующий элемент за концом последовательности двоек

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func sortColors(nums []int)  {
    ez:=-1
    eo:=-1
    
    for idx:=range nums {
        if nums[idx] == 0 && ez != idx {
            ez++
            nums[idx], nums[ez] = nums[ez], nums[idx]
        }
        if nums[idx] == 1 && eo != idx {
            if eo == -1 {
                eo = ez
            }
            eo++
            nums[idx], nums[eo] = nums[eo], nums[idx]
        }
    }
}