Эта задачка применялась, как минимум, на собеседованиях в Sun Microsystems. Задачка миленькая, несложная, на сообразительность.
Задача
Отсортировать массив, состоящий только из единиц и двоек.
Решения
Решений, как у большинства задачек много. Приведем некоторые.
- Сложить все элементы массива и вычесть из суммы длину массива. Результатом будет количество двоек в массиве. Далее массив заливается нужным количеством последовательных двоек и единиц.
- Посчитать количество единиц и двоек, пройдя по массиву. Далее опять заливаем массив нужным количеством двоек и единиц.
- Запускаем в цикле два счетчика, сближающихся с противоположных концов массива. Меняем местами соответствующие значения, по необходимости.
В третьем варианте что-то вроде:
public void sort12(int []array) {
int i = 0;
int j = array.length-1;
for (; i<j; i++) {
// Сортируем по возрастанию
if (array[i] == 2) {
for (; array[j] == 2; j--);
array[i] = 1;
array[j] = 2;
j--;
}
}
}
Первый вариант представляется самым оптимальным, с точки зрения производительности: сравнений нет, все действия с массивом последовательные. В нём как раз проявляется сообразительность 
Второй вариант похуже, но тоже ничего.
Третий вариант видится близким ко второму, на достаточно небольших массивах (влезающих в кэш) и похуже на больших массивах.
При этом предлагается считать, что кандидат, пишущий какую-нибудь классическую сравнивающую сортировку, получает EPIC FAIL.
P.S. В коде есть опечатки: в сигнатуре метода должно быть int[]. Да и int i = 0; можно внести в for.
Да, epic fail однозначный.
P.S. Сигнатуру метода поправил, спасибо. Про i думал, решил оставить в одном месте с j, т.к. на скорость не влияет.
Первый да, но немного измененный — в процессе складывания заливаем массив 1. потом доливаем необходимое кол-во двоек.(или наоборот)
А как мы узнаем количество единиц, на котором надо остановиться? Или заливаем ими весь массив?
да весь — потом доливаем двойки
однако можно заливать и двойками вначале а единицами потом — хотя это абсолютно идентично по количеству операций (у меня как раз кто-то из знакомых считал число элементарных операций и там и там — и что странно получилось одинаково
)
Есть у меня ощущение, что, при некоторых раскладах, специализированные функции по заливке памяти значениями, вроде memset, должны работать пободрее, чем проход в цикле и присваивание значений.
Вы что, хотите сказать, что залить _весь_ массив единичками, а потом залить хвост двойками настолько же быстро, что и залить голову единичками, а хвост двойками?
В первом варианте на каждую ячейку, содержащую в итоге «2», будут производиться две записи! Как бы Вы не старались. Расчёт «элементарных» операций разбивается таким вот простым рассуждением — как удалось уравнять их количество?
Ага, давайте скажем, что в массиве лежат int'ы =) Тогда memset'ом не обойдёшься.
+1